С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
5 / 5 / 1
Регистрация: 06.10.2020
Сообщений: 176

Добавить элемент в множество или вывести минимальный элемент множества, не меньший заданного

14.05.2021, 00:10. Показов 5077. Ответов 0
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Реализуйте структуру данных, которая поддерживает множество S целых чисел, с котором разрешается производить следующие операции:
add(i) — добавить в множество S число i (если он там уже есть, то множество не меняется);
next(i) — вывести минимальный элемент множества, не меньший i. Если искомый элемент в структуре отсутствует, необходимо вывести -1.

Входные данные
Исходно множество S пусто. Первая строка входного файла содержит n — количество операций (1≤n≤300000). Следующие n строк содержат операции. Каждая операция имеет вид либо «+ i», либо «? i». Операция «? i» задает запрос next(i).

Если операция «+ i» идет во входном файле в начале или после другой операции «+», то она задает операцию add(i). Если же она идет после запроса «?», и результат этого запроса был y, то выполняется операция add((i+y) mod 1000000000).

Во всех запросах и операциях добавления параметры лежат в интервале от 0 до 1000000000.

Выходные данные
Для каждого запроса выведите одно число — ответ на запрос.

Примеры

входные данные
Code
1
2
3
4
5
6
7
6
+ 1
+ 3
+ 3
? 2
+ 1
? 4
выходные данные
Code
1
2
3
4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
 
using namespace std;
 
#define int long long
 
class AAA {
    public:
        int S[350000];
        bool flag;
        int x;
    private:
        int counter;
        
    public: AAA() {
        flag = false;
        counter = 0;
        x = 0;
    }
    int Next(int n) {
        int min = -1;
        bool flag1 = false;
        for (int i=0; i<counter; i++) {
            if ((flag1 == false) && (S[i])>=n) {
                min = S[i];
                flag1 = true;
            } else if (S[i]<=min) min = S[i]; 
        }
        flag1 = true;
        x = min;
        return min;
    }
    void Add(int n) {
        if (flag == true) {
            S[counter] = n+x;
            flag = false;
        } else S[counter] = n;
        counter++;
    }
};
 
int32_t main() {
    AAA A;
    int k;
    cin >> k;
    char last = '+';
    int y = -1;
    while (k--) {
        int n;
        char ch;
        cin >> ch >> n;
        if (ch == '+') {
            if (last == '?') n = (n + y) % 1000000000;
            A.Add(n);
            //cout << "+ " << n << endl;
        } else {
            y = A.Next(n);
            //cout << "? " << y << endl;
            cout << y << endl;
        }
        last = ch;
    }
}
Проходит только первый тест, не понимаю, где ошибка.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
14.05.2021, 00:10
Ответы с готовыми решениями:

один элемент из множества А обменяли на элемент из множества В, вероятность, что множество А не изменилось?
одну букву из слова ВСЕЛЕННАЯ обменяли на букву из слова ВАСЯ найти вероятность того, что последовательность первого слова при этом не...

Найти первый элемент последовательности, меньший заданного ε
Помогите с решением, пожалуйста

Вывести минимальный и максимальный элемент массива заданного размера
ввести с клавиатуры размерность одномерного динамического массива, затем создать его с рандомными значениями и вывести минимальный и...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
14.05.2021, 00:10
Помогаю со студенческими работами здесь

Вывести новый массив, в который не входит минимальный элемент заданного
Не успеваю и не получаеться зделать последнее задание.Помогите пожалуйста.

Найти в массиве ближайший по значению элемент меньший заданного числа
Добрый день, господа. Помогите пожалуйста с решением задачи. Дано некоторое число А. Найти в целочисленном массиве В из N элементов...

для одномерного множества состоящей из целых n чисел 1.найти по модулю самый меньший элемент ;
для одномерного множества состоящей из целых n чисел .найти по модулю самый меньший элемент ;

Определить минимальный элемент в каждой строке и заменить каждый элемент в последнем столбце на этот минимальный элемент
Определить минимальный элемент в каждой строке и заменить каждый элемент в последнем столбце на этот минимальный элемент.

Двусвязный список - Добавить элемент после заданного, удалить заданный элемент
Реализуйте списочную структуру в виде класса. работа состоит из двух частей: из класса (структуры, алгоритма) и из тестирующего кода. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru