Помогите решить задачу по программированию на c++

Question

Помогите решить задачу по программированию на c++

Daniil Lipov Ученик (119), на голосовании 5 месяцев назад

Вам дано q запросов. Каждый запрос имеет вид:

op number.

op это символ, он может быть либо `i`, либо `m`

number это неотрицательное целое число. number не превосходит 10000

Изначально у вас есть пустое множество чисел.

Если к вам приходит запрос `i` number, то вы должны добавить число number в ваше множество. Если к вам приходит запрос `m` number , вы должны найти минимум X среди всех чисел, которые уже присутствуют в вашем множестве и сравнить его с числом number. Ответом на такой запрос является min(X, number). При этом, если на момент такого запроса в вашем множестве еще нет ни одного элемента, то будем считать, что минимальный элемент в нем это 0.

В этой задаче, кол-во запросов, а также сами запросы генерирует ваша программа.

Для удобства, вам уже дан код генератора запросов

void setNewSeed(unsigned int& seed) {

seed *= 123456;

seed %= 987;

seed += 123;

seed %= 10000;

}

std::pair<char, unsigned int> getQuery(unsigned int& seed) {

char op = "im"[seed % 2];

setNewSeed(seed);

unsigned int number = seed;

setNewSeed(seed);

return {op, number};

}

std::vector<std::pair<char, unsigned int>>

getTaskQueries(unsigned int seed) {

unsigned int q = seed;

setNewSeed(seed);

std::vector<std::pair<char, unsigned int>> queries;

for (int i = 0; i < q; ++i) {

queries.push_back(getQuery(seed));

}

return queries;

}

Для того, чтобы получить запросы в этой задаче, вы должны вызвать функцию getTaskQueries и передать ей параметр seed. В ответ эта функция вернет вектор размера q. Элементы этого вектора — пары. Они и являются запросами к задаче. Первый элемент пары это символ (либо `i`, либо `m`). Второй элемент пары это число number. Вы можете просто скопировать код генератора в вашу программу и пользоваться им, чтобы получить запросы.

Формат входных данных

На вход вашей программе подается число seed < 10000. С его помощью ваша программа будет генерировать исходные запросы.

Формат выходных данных

Выведите одно число — сумму ответов на все запросы типа `m` number.

Пример

Если запросы имели вид
i 5

m 6

i 11

m 3

То ответ на задачу будет min(5, 6) + min(5, 3) = 8

В поле краткого ответа введите результат выполнения вашей программы для seed = 9997

Answer 1

Unkdunk Мастер (1279) 6 месяцев назад

сложно

Answer 2

#include <iostream>
#include <vector>
using namespace std;

void setNewSeed(unsigned int& seed) {

seed *= 123456;

seed %= 987;

seed += 123;

seed %= 10000;

}

std::pair<char, unsigned int> getQuery(unsigned int& seed) {

char op = "im"[seed % 2];

setNewSeed(seed);

unsigned int number = seed;

setNewSeed(seed);

return { op, number };

}

std::vector<std::pair<char, unsigned int>>

getTaskQueries(unsigned int seed) {

unsigned int q = seed;

setNewSeed(seed);

std::vector<std::pair<char, unsigned int>> queries;

for (int i = 0; i < q; ++i) {

queries.push_back(getQuery(seed));

}

return queries;

}

int main() {
vector <pair<char, unsigned int>> mass;
vector <unsigned int> mnojestvo;
unsigned int seed;
cin >> seed;
unsigned int sum = 0;
mass = getTaskQueries(seed);
for (int i = 0; i < seed; i++) {
if (mass[i].first == 'i') {
mnojestvo.push_back(mass[i].second);
}
if (mass[i].first == 'm') {
bool flag = mnojestvo.empty();
if (flag) {
unsigned int null = 0;
sum += min(null,mass[i].second);
}
else {
unsigned int minn;
for (auto x : mnojestvo) {
minn=mnojestvo[0];
if (minn > x) {
minn = x;
}
}
sum += min(minn, mass[i].second);
}

}
}

cout << sum;

}