主页 / 问题

问题[олимпиада]

Martin Hope
Kirill
Asked: 2024-11-25 02:25:25 +0000 UTC
  • 5

问题的本质：输入是：

  1. 每个输入的行数
  2. 字符串（0 和 1）
  3. 对字符串的操作次数（按数字替换元素）
  4. 操作（格式：“数字”“字符”）

原文：https ://codeforces.com/problemset/problem/2036/C

困难在于时间限制，但是这段代码在测试2中的550代币上是错误的，我不明白问题是什么，请提示逻辑中的漏洞，提前感谢

int n = Convert.ToInt32(Console.ReadLine());
List<int> list1100 = new List<int>();
List<string> list = new List<string>();
bool result;
for (int i = 0; i < n; i++)
{
    char[] arr = Console.ReadLine().ToCharArray();
    Func(arr);
    int q = Convert.ToInt32(Console.ReadLine());
    for (int k = 0; k < q; k++)
    {
        string x = Console.ReadLine();
        if (arr.Length < 4)
        {
            list.Add("NO");
            continue;
        }

        string[] str = x.Split(' ');
        int index = Convert.ToInt32(str[0]);
        char value = Convert.ToChar(str[1]);

        result = list1100.Count > 0;
        if (value == arr[index - 1])
        {
            list.Add(result ? "YES" : "NO");
            continue;
        }

        arr[index - 1] = value;

        if (value == '1')
        {
            if (arr.Length > index + 2) // {input}100
            {
                if (arr[index] == '1' && arr[index + 1] == '0' && arr[index + 2] == '0') { if (!list1100.Contains(index - 1)) { list1100.Add(index - 1); } list.Add("YES"); continue; }
            }
            if (arr.Length >= index + 2 && index != 1) // 1{input}00
            {
                if (arr[index - 2] == '1' && arr[index] == '0' && arr[index + 1] == '0') { if (!list1100.Contains(index - 2)) { list1100.Add(index - 2); } list.Add("YES"); continue; }
            }
        }
        else // value == 0
        {
            if (arr.Length >= index + 1 && index >= 3) // 11{input}0
            {
                if (arr[index - 3] == '1' && arr[index - 2] == '1' && arr[index] == '0') { if (!list1100.Contains(index - 3)) { list1100.Add(index - 3); } list.Add("YES"); continue; }
            }
            if (arr.Length >= index && index >= 4) // 110{input}
            {
                if (arr[index - 4] == '1' && arr[index - 3] == '1' && arr[index - 2] == '0') { if (!list1100.Contains(index - 4)) { list1100.Add(index - 4); } list.Add("YES"); continue; }
            }
        }
        foreach (int ex in list1100)
        {
            if (ex <= index - 1 && index - 1 <= ex + 3)
            {
                list1100.Remove(ex);
                break;
            }
        }
        result = list1100.Count > 0;
        list.Add(result ? "YES" : "NO");
    }
}
for (int i = 0; i < list.Count; i++)
{
    Console.WriteLine(list[i]);
}

void Func(char[] arr)
{
    list1100.Clear();
    for (int j = 0; j < arr.Length - 3; j++)
    {
        if (arr[j] == '1' && arr[j + 1] == '1' && arr[j + 2] == '0' && arr[j + 3] == '0') { list1100.Add(j); }
    }
    return;
}
олимпиада
Martin Hope
Curtisol
Asked: 2023-11-18 04:00:02 +0000 UTC
  • 6

请帮我解决问题。在我看来，这项任务很艰巨。说实话，我不知道如何解决。虽然有一个想法可以简单地遍历所有战士的组合，但是数量太多了，所以我必须寻求帮助）给我一个解决方案的想法））

问题

你是贝尔兰繁荣首都的快乐市长，但运气不好 - 一个可怕的怪物定居在郊区，并正在攻击在首都和邻近城市之间行驶的贸易商队。为了摆脱怪物，你决定从城市的冒险家公会雇佣一支英雄团队。公会提供 n 个战士，第 i 个战士拥有高生命值单位和低攻击单位。需要杀死的怪物有一定的生命值。

只要怪物还剩下正数的生命值，并且至少一名英雄还剩下正数的生命值，就会发生以下情况：

首先，每个活着的英雄都会对怪物造成相当于其攻击值的伤害。如果怪物的生命值降到零，则战斗结束；然后，如果怪物还活着，它会对每个英雄造成 1 点伤害。每个生命值降至零的英雄都会死亡。由于金库有限，你需要雇佣最少数量的英雄来杀死怪物。但你也不希望队伍中至少有一名英雄死亡，所以你需要招募最少数量的英雄，这样他们才能不损失地击杀怪物。

笔记

在第一组输入数据中，三个英雄就足以无损失地击杀怪物。例如，这些英雄可能是数字2、3、4。他们的总攻击力是6，并且两次攻击就能杀死怪物。

在第一次测试的第二组输入数据中，有一个英雄，他的实力足以立即杀死怪物。

输入格式

输入数据的第一行包含一个整数 t (1 ≤ t ≤ 1000) — 输入数据集的数量。以下是各组的说明。每组的第一行包含整数 a (1 ≤ a ≤ 109) — 怪物的生命值。每组的第二行包含一个整数 n (1 ≤ n ≤ 2⋅105) — 公会提供雇佣的战士总数。每组的第三行包含 n 个整数 h1,h2,…,hn (1 ≤ hi ≤ 109) — 每个英雄的生命值单位。每组第四行包含n个整数d1,d2,…,dn (1 ≤ di ≤ 109)——每个英雄的攻击单位。保证所有输入数据集的n之和不超过2⋅105

输出格式

对于每组输入，在单独的行上打印一个整数：必须雇佣才能无损失地杀死怪物的英雄的最小数量，如果这是不可能的，则为 -1。

例子

Входные данные: 
2
12
5
1 2 3 3 4
2 4 1 1 1
10
1
1
14
Выходные данные:
3
1

哦对了，时间限制是2秒。由于您需要显示所需的战士数量，而不是他们的索引，因此您可能不需要查看所有选项或类似的内容

以@StanislavVolodarskiy的想法为基础，我用python写了这个：

answer = list()
for _ in range(int(input())):
    a = int(input())
    n = int(input())
    hp_war = list(map(int, input().split()))
    d_war = list(map(int, input().split()))
    attack = dict()
    for i in range(n):
        attack[d_war[i]] = attack.get(d_war[i], list()) + [hp_war[i]]
    attack = {key: sorted(attack[key], reverse=True) for key in sorted(attack, reverse=True)}

    max_h_lvl, k = max(hp_war) + 1, n + 1
    h_left, h_level, h_right = 1, max_h_lvl // 2, max_h_lvl
    while True:
        sum_attack, flag, cnt = 0, 0, 0
        for a_w in attack:
            for h_w in attack[a_w]:
                if h_w >= h_level:
                    cnt += 1
                    sum_attack += a_w
                    if sum_attack * h_level >= a:
                        flag = 1
                        break
                    continue
                break
            if flag == 1:
                break
        if flag:
            k = min(k, cnt)
        if h_right - h_left <= 1:
            break
        if flag:
            h_right, h_level = h_level, (h_level + h_left) // 2
        else:
            h_left, h_level = h_level, (h_level + h_right) // 2

    if k == n + 1:
        answer.append(-1)
    else:
        answer.append(k)

for ans in answer:
    print(ans)

在我看来，这是一个有效的解决方案，但在测试系统看来却不是。尽管如此，我还是错过了一些东西。但什么？

олимпиада
Martin Hope
Thwrani
Asked: 2022-08-03 19:16:53 +0000 UTC
  • -3

一些银行希望实施支持以下操作的客户账户管理系统： -
为客户账户充值；
- 从账户中取款；
- 要求账户上的资金余额；
- 客户账户之间的汇款；
- 计算所有客户的利息。
有必要实施这样的系统。银行客户由其名称（不包含空格的唯一字符串）标识。最初，该银行没有一个客户。一旦客户进行存款、取款或转账，他就会获得一个余额为零的账户。所有进一步的操作都只用这个帐户进行。帐户上的金额可以是正数也可以是负数，但它始终是整数。

首先，输入要执行的操作数 n (n <= 50000)。接下来的 n 行包含操作本身：

DEPOSIT name sum — 将金额总和记入客户名称的账户。如果客户没有帐户，则创建一个帐户。
WITHDRAW name sum - 从客户名称的账户中提取金额。如果客户没有帐户，则创建一个帐户。
余额名称 - 找出客户帐户名称上的余额。
TRANSFER name1 name2 sum — 将金额 sum 从客户 name1 的账户转移到客户 name2 的账户。如果客户没有帐户，则会为他创建一个帐户。
INCOME p — 将账户金额的 p% 计入所有已开立账户的客户。只有账户余额为正的客户才会产生利息，如果客户的余额为负，那么他的账户不会改变。计息后，账户上的金额保持不变，即只计提整数个货币单位。应计利息的小数部分被丢弃。

对于每个 BALANCE 请求，必须显示该客户帐户的余额。如果具有请求名称的客户没有银行帐户，则打印 ERROR。
示例：
输入：
7
存款 Ivanov 100
收入 5
余额 Ivanov
转账 Ivanov Petrov 50
取款 Petrov 100
余额 Petrov
余额 Sidorov
输出：
105
-50
错误

我用 C++ 编写了代码：

#include <iostream>
#include <map>
#include <string>
using namespace std;

void deposit(map<string, long long> &bank, string &name, long long &sum)
{
    if (bank.find(name) == bank.end())
        bank[name] = 0;
    bank[name] += sum;
}
void withdraw(map<string, long long> &bank, string &name, long long &sum)
{
    if (bank.find(name) == bank.end())
        bank[name] = 0;
    bank[name] -= sum;
}
string balance(map<string, long long> &bank, string &name)
{
    if (bank.find(name) == bank.end())
        return "ERROR";
    return to_string(bank[name]);
}
void income(map<string, long long> &bank, float percent)
{
    for (auto it = bank.begin(); it != bank.end(); ++it)
    {
        if (it->second > 0)
        {
            bank[it->first] = it->second * (100 + percent) / 100;
        }
    }
}
int main()
{
    map<string, long long> bank;
    long long n, val; cin >> n;
    string command, name, name2;
    for (long long i = 0; i < n; i++)
    {
        cin >> command;
        if (command == "DEPOSIT")
        {
            cin >> name >> val;
            deposit(bank, name, val);
        }
        else if (command == "WITHDRAW")
        {
            cin >> name >> val;
            withdraw(bank, name, val);
        }
        else if (command == "BALANCE")
        {
            cin >> name;
            cout << balance(bank, name) << endl;
        }
        else if (command == "TRANSFER")
        {
            cin >> name >> name2 >> val;
            withdraw(bank, name, val);
            deposit(bank, name2, val);
        }
        else if (command == "INCOME")
        {
            float value;
            cin >> value;
            income(bank, value);
        }
    }
}

在某些测试中，它显示错误的答案。我无法弄清楚错误在哪里。请告诉我它可以在哪里以及如何修复它？（我不知道测试数据...）

c++ олимпиада
Martin Hope
errormaker
Asked: 2022-07-18 23:41:32 +0000 UTC
  • -2

我的代码：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
  int n,mx1=-1000000000,mx2=-1000000000,mn1=1000000000,mn2=1000000000;
  vector <int> t(n);
  for (int i=0;i<n;i++){
    cin>>t[i];
  }
  for (int c=0;c<n;c++){
    if (t[c]>0&&t[c]>mx1){
      mx2=mx1;
      mx1=t[c];
    }else if (t[c]<0&&t[c]<mn1){
      mn2=mn1;
      mn1=t[c];
    }
  }
  if ((mx1*mx2)>(mn1*mn2)){
    cout<<mx2<<" "<<mx1;
  }else{
    cout<<mn1<<" "<<mn2;
  }
  return 0;
}

最大乘积 在一个填充了任意整数的数组中，找到两个乘积最大的数。不要使用嵌套循环。

输入数据

该程序首先被赋予值 n⩽50000——数组中元素的数量。输入的下一行包含数组元素本身 - 整数，模不超过 30000。

输出

按升序给出两个所需的数字。

c++ олимпиада
Martin Hope
Dedalus Morffino
Asked: 2022-08-23 03:44:58 +0000 UTC
  • 0

所以，这就是问题本身：https ://www.eolymp.com/ru/problems/3922

这是我在伪代码中的解决方案：

function solve(input: string) -> string {
    let lines = input.split("\n");
    let n = int(lines[0]);
    
    let l = lines.length();
    for(let j = 0; j < lines.length(); j += 1) {
        if(lines[j].length() == 0) { l -= 1; }   
    }
    
    let mes: int[] = [];
    let pos: int[] = [];
    let i = 1;
    while(i < l) {
        mes.push(int(lines[i]));
        pos.push(i);
        if(int(lines[i]) == 0) { i += 3;}
        else { i += 2;}
    }
    
    let rel: int[] = [];
    for(let j = 0; j < mes.length(); j += 1) {
        rel.push(0);
    }
    
    for(let j = 0; j < mes.length(); j += 1) {
        if(mes[j] != 0) {
            if(mes[mes[j] - 1] == 0) {
                rel[mes[j] - 1] += 1;
            }
        }
    }
    
    let index = 0;
    for(let j = 0; j < rel.length(); j += 1) {
        if(rel[j] > rel[index]) {
            index = j;
        }
    }
    
    
    return lines[pos[index] + 1];
}

这里的input是一串输入数据（自然是带有光标翻译字符\n），返回时显示答案。它适用于我的样品，但发送时我会抓住 WA。也许我在某个地方遗漏了一些东西。请告诉我在哪里？）

алгоритм олимпиада