Информатика

15 732 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Отсутствующее число#21844

Вам даны n чисел a1, a2, ..., an. Найдите наименьшее целое положительное число x, не содержащееся в множестве {a1, ..., an}, то есть, такое, что не существует i, для которого верно ai = x.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество чисел. Во второй строке через пробел записаны n чисел: a1, ..., an (1 ≤ ai ≤ 109).

Выходные данные

Выведите наименьшее целое положительное x не содержащееся в множестве {a1, ..., an}.

Примеры тестов

Входные данные

5
1 2 3 4 5
Выходные данные
6
Входные данные
5
1 3 4 5 6
Выходные данные
2

 

Примечание

Тесты разделены на группы, но оцениваются отдельно

  • n = 1 — 10 баллов
  • n ≤ 100 — 20 баллов
  • ai ≤ 106 — 30 баллов
  • Без дополнительных ограничений.

Так, если вы решили задачу для n ≤ 100, то вы получите 30 баллов за первую и вторую группы, если вы решили задачу для ai ≤ 106, то вы получите 30 баллов за третью группу. Если ваша программа будет работать в обоих случаях, то вы получите 60 баллов. За полное решение вы получите 100 баллов.


Одномерные массивы
✓ 67✗ 520800средняяВойти и решать
Три числа#21843
Вам дано три числа a, b и c. Вы должны в таком порядке приписать эти числа друг к другу, чтобы в результате получилось минимальное число. Например, если a = 12, b = 5, c = 3, приписыванием можно получить числа 1253, 1235, 3125, 3512, 5123, 5312. Минимальным, среди этих чисел является 1235.

Входные данные

В первой строке через пробел записаны три целых числа a, b и c (1 ≤ a, b, c ≤ 100).

Выходные данные

Выведите минимальное число, которое можно получить, приписав a, b и c друг к другу в каком-нибудь порядке.

Примеры тестов

Входные данные

12 3 5
Выходные данные
1235
Входные данные
2 21 3
Выходные данные
2123
Перестановкиреализация
✓ 51✗ 49700средняяВойти и решать
Пифагоровы тройки#21840

У Фёдора есть массив различных натуральных чисел. Известно, что чисел N. Фёдор хочет найти в массиве количество троек x, y и z (x < y < z), таких, что x2 + y2 = z2. Помогите ему в этом.

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

В первой строке находится число N (3 ≤ N ≤ 3000). На следующей строке находятся N натуральных чисел, каждое из которых не превышает 3000.

Решения, корректно работающие при N ≤ 100, получат не менее 50 баллов.

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

В единственной строке нужно вывести одно число — ответ на задачу.

Ввод:

5
5 12 13 9 15

Вывод:
2
Вывод формулы
✓ 7✗ 971 100средняяВойти и решать
Числа#21838

У Артура есть два натуральных числа — x и y (x < y). Помогите ему найти натуральное число z такое, что:

  • z > x;
  • z > y;
  • z не делится на x;
  • z не делится на y;
  • z делится на y - x;
  • z минимально.

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

В первой строке находятся числа x и y (x, y ≤ 106)

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

Выведите число z или '0', если его не существует.

Ввод:
1 2

Вывод:
0

Разбор случаевреализация
✓ 56✗ 281700средняяВойти и решать
Друзья#21825
В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.
 
Входные данные
 
В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.
 
Выходные данные
 
В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

Ввод:
3 1
0 1 0
1 0 1
0 1 0

Вывод
2
графыПоиск компонент связности
✓ 0✗ 51 200средняяВойти и решать
Z-функция#21824
Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.

Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.

Выходные данные
Вывести k строк с ответами на запросы.

 

Примеры
№ Входные данные Выходные данные
1
2 ali balimali
3
0
 2
8
Z-функция. Префикс-функция
✓ 41✗ 148700средняяВойти и решать
Pref-функция#21823
Дана строка S. Найдите сумму значений префикс-функции для всех заданных позиций строки S. 

Входные данные
В первой строке входного файла записана строка S (\(1 <= |S| <= 150 000\)) и k (количество заданных позиций).
Далее идут k чисел - позиции, значения префикс-функции которых надо сложить.

Выходные данные
В выходной файл выведите одно число - сумму значений префикс-функции для всех заданных позиций строки S.
 

 

Примеры
№ Входные данные Выходные данные
1
abacaba 2
3
7
 4
Z-функция. Префикс-функция
✓ 68✗ 111400лёгкаяВойти и решать
HASH#21822
Программисту Васе не повезло - вместо отпуска его послали в командировку на научную конференцию. "Надо повышать уровень знаний", - сказал начальник, "Важная конференция по криптографии, проводится во Франции - а там шифровали еще во времена Ришелье и взламывали чужие шифры еще во времена Виета."
Вася быстро выяснил, что все луврские картины он уже где-то видел, вид Эйфелевой башни приелся ему еще раньше, чем мышка стерла его с коврика, а такие стеклянные пирамиды у нас делают надо всякими киосками и сомнительными забегаловками. Одним словом, смотреть в Париже оказалось просто не на что, рыбу половить негде, поэтому Васе пришлось посещать доклады на конференции.
Один из докладчиков, в очередной раз пытаясь разгадать шифры Бэкона, выдвинул гипотезу, что ключ к тайнам Бэкона можно подобрать, проанализировав все возможные подстроки произведений Бэкона. "Но их же слишком много!" - вслух удивился Вася. "Нет, не так уж и много!" - закричал докладчик, - "Подсчитайте, и вы сами убедитесь!"
Тем же вечером Вася нашел в интернете полное собрание сочинений Бэкона. Он написал программу, которая переработала тексты в одну длинную строку, выкинув из текстов все пробелы и знаки препинания. И вот теперь Вася весьма озадачен - а как же подсчитать количество различных подстрок этой строки? 

Входные данные
На входе дана непустая строка, полученная Васей. Строка состоит только из строчных латинских символов. Ее длина не превосходит 2000 символов. 

Выходные данные
Выведите количество различных подстрок этой строки.

 

Примеры
№ Входные данные Выходные данные
1 aaba 8
Хеш
✓ 40✗ 20700средняяВойти и решать
НОД и НОК#21815
Сережа очень любит математические задачи. Недавно на математическом кружке ему рассказали, что такое НОД и НОК. 
НОД двух натуральных чисел a и b — это их наибольший общий делитель, то есть такое максимальное число x, что a делится на x и b делится на x. Например, \(НОД(24, 18) = 6\). А НОК целых чисел a и b — это их наименьшее общее кратное, то есть такое минимальное число x, что x делится на a и x делится на b. Например, \(НОК(24, 18) = 72\).
Сережа сразу заметил, что может существовать несколько пар чисел с одинаковыми НОД и НОК. Теперь он заинтересовался вопросом: если заданы числа a и b, насколько близко друг к другу могут быть два числа, у которых такие же НОД и НОК.
Помогите ему по заданным двум числам a и b найти такие числа x и y, что \(НОД(a, b) = НОД(x, y)\), \(НОК(a, b) = НОК(x, y)\), а их разность \(y - x\) минимальна. 

Входные данные 
В первой строке входного файла находятся два натуральных числа a и b (\(1 <= a, b <= 10^9\)).
 
Выходные данные 
Выведите два натуральных числа x и y (\(1 <= x <= y\)), таких, что \(НОД(a, b) = НОД(x, y)\), \(НОК(a, b) = НОК(x, y)\), а их разность \(y - x\) минимальна.
 
Примеры
№ Входные данные Выходные данные
1 3 4 3 4
НОД и алгоритм Евклида
✓ 75✗ 1 0641 100средняяВойти и решать
Завоевание#21812
Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из n городов его королевства. Петир выяснил, что в i-м городе ищут работу ai воинов, которых он может завербовать в свою армию.
Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из i-го города, необходимо заплатить ему ci золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для i-го и j-го города выполнено ai < aj , то ci ≤ cj . Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.

Входные данные
В первой строке входного файла находится целое число n (1 ≤ n ≤ 1000) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа ai и ci (1 ≤ ai ≤ 100, 1 ≤ ci ≤ 10 000) — количество воинов в i-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар i и j выполнено условие, что если ai < aj , то ci ≤ cj .

Выходные данные
В выходной файл выведите одно целое число — минимальное количество монет, которые Лорду Петиру придется заплатить, чтобы все воины вошли в его армию.
 
Примеры
№ Входные данные Выходные данные
1
3
1 1
2 2
4 3
 5
 
В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились
к его армии. Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.
Динамическое программирование
✓ 6✗ 1021 200средняяВойти и решать
21804#21804
Если мы хотим сделать два одинаковых слова, то необходимо использовать операцию:

1. вырезать
2. копировать
3. размножить
4. удалить
Конечные автоматы
1 100труднаяВойти и решать
21803#21803
Работая с готовым текстом, мы не можем

1. изменить его начертание
2. изменить его цвет
3. изменить его язык
4. изменить его размер
Обработка текста
1 000средняяВойти и решать
21802#21802
Преобразование, изменяющее структуру текста называется

1. редактированием
2. форматированием
3. стилизацией
4. структуризацией
Конечные автоматы
1 300труднаяВойти и решать
21801#21801
Преобразование, изменяющее содержание текста называется

1. редактированием
2. форматированием
3. стилизацией
4. структуризацией
Обработка текста
1 000средняяВойти и решать
21800#21800
Представление текста в виде списка называется

1. проверкой правописания
2. форматированием
3. редактированием
4. стилизацией
Обработка текста
1 300труднаяВойти и решать
Поделиться
Класснуть