Информатика

16 015 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Assault#23586
В то время, пока обороняющиеся отвлеклись на Блейза, Корвин начал штурм города. Для того, чтобы его армия вошла в город, ему нужно пробить брешь в стене. В его распоряжении есть целый флот, из которого он собирается обстреливать стены города. Стена являются линией из n сегментов, пронумерованных от 1 до n. 
Корвин хорошо помнит, насколько укреплен каждый сегмент стены. К сожалению, с тех пор как Корвин последний раз был в Амбере, сегменты несколько раз перестраивали, поэтому их укрепленность могла измениться, поэтому Корвин владеет устаревшей информацией.
Но Джерард не только согласился отвести свой флот из бухты Амбера, благодаря чему флоту Корвина удалось добраться до Амбера с целым и невредимым флотом, но и предоставил ему журнал с m записями, в котором в i-ой записи указано, что были перестроены сегменты с li по ri, а также сказано, насколько изменилась укрепленность всех сегментов (укрепленность каждого сегмента на отрезке [li; ri] изменяется на одно и тоже значение ti).
Корвин m раз предлагает выстрелить по сегментам стены с l по r из p кораблей. Известно, что брешь будет пробита, если на отрезке [l; r] есть хотя бы один сегмент с укрепленностью меньше p. Вы должны ответить ему, будет ли пробита брешь (вывести "YES"), или нет (вывести "NO"). 

Входные данные
На первой строке находятся числа n, m и k (1 <= n, k <= 100000, 1 <= m <= 10000)  - количество сегментов, записей и запросов от Корвина соответственно.
На второй строке находятся числа a1,..., an (0 <= ai <= 10).
В следующих m строках содержатся числа l, r, t (1 <= l <= r <= n, -10 <= t <= 10).
В следующих k строках содержатся числа l, r, p (1 <= l <= r <= n, 1 <= p <= 1000).

Выходные данные
В i-ой строке выведите ответ на i-ый запрос Корвина.

 
Примеры
№ Входные данные Выходные данные
1
10 3 3
123 398 287 190 76 15 407 312 323 659 
4 9 -99
10 10 -82
4 10 76
9 10 32
5 6 283
4 4 983
NO
YES
YES
Дерево отрезков, RSQ, RMQПрефиксные суммы(минимумы, ...)
✓ 33✗ 111700средняяВойти и решать
Двоичное дерево поиска 1#23571
Реализуйте сбалансированное двоичное дерево поиска.
ВНИМАНИЕ! Пользоваться vector и set из STL СТРОГО ЗАПРЕЩЕНО, однако рекомендуется стрессить ваше решение с ними для поиска багов.

Формат входных данных:
В первой строке дано число n -  количество операций с деревом. 1 <= n <= 100000.
Далее дается n строк – операции с деревом. В каждой строке находится одна из следующих операций:
1) insert x – добавить в дерево ключ x. Если ключ x уже в дереве, то ничего делать не нужно.
2) delete x – удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не нужно.
3) exists x – если ключ х есть в дереве, то выведите “true”, иначе “false”.

Формат выходных данных:
Выведите последовательно результат выполнения всех операций exists. Каждый ответ нужно выводить в отдельной строке.
Пример:
Ввод Вывод
6
insert 2
insert 5
insert 3
exists 3
exists 4
delete 5
 
 true
false
 
(c) Курбатов Е., 2016
Двоичное дерево поискаДекартово дерево
✓ 18✗ 631 000средняяВойти и решать
Вывод переменной - 5#23465

Напишите программу, которая вводит с клавиатуры целое число и выводит текст, аналогичный приведенному в примере.

 
Пример
№ Входные данные Выходные данные
1 2007 The next number for the number 2007 is 2008.
The previous number for the number 2007 is 2006.
Ввод, вывод данныхЛинейные алгоритмы
✓ 546✗ 2 853400лёгкаяВойти и решать
Сумма цифр числа#23452
Используя предыдущую программу, измените ее таким образом, чтобы она находила сумму цифр числа n.
Программа должна запрашивать с клавиатуры одно число и выводить на экран фразу. Например, для числа 123:

The sum of the digits of number 123 is 6

 
СтрокиЦикл for
✓ 9 276✗ 35 103200лёгкаяВойти и решать
Декодирование сообщения#23418

По каналу связи передаётся последовательность слов в латинском алфавите {А, Е, Р}. Длина каждого слова не превосходит 10 букв, слова могут не быть осмысленными словами русского языка. Каждое слово передается в виде целого числа, полученного следующим образом:
1)      Сначала слово кодируется с помощью неравномерного двоичного кода с кодовыми словами: Е – 0; Р – 10; А – 11;
2)      К полученной двоичной последовательности справа приписывается цифра 1;
3)      Полученная двоичная цепочка переворачивается, то есть, из цепочки 01010111 получается 11101010;
4)      Искомое число N вычисляется в результате перевода двоичной цепочки, полученной на предыдущем шаге, в десятичную систему.
 

Например, символьная последовательность ААЕЕР будет преобразована в 11110010, затем (добавляем единицу в конец) в 111100101, а потом в число: 1 + 2 + 4 + 8 + 64 + 256 = 335. Отметим, что 335 = 1010011112.
Напишите программу, которая, получив на вход натуральное число, декодирует переданное сообщение и определяет, сколько раз в исходном слове встречаются гласные буквы. Считается, что входное число может быть представлено в виде значения целого типа в используемом языке программирования.

Пример входных данных
5483

Пример выходных данных
АЕРАЕРР
4

Примечание. В этом примере: исходное слово: АЕРАЕРР. Кодовая двоичная последовательность: 110101101010, после добавления 1 справа получим: 1101011010101.
ЕГЭ_информатикаЕГЭ-04. Кодирование и декодирование информации
✓ 57✗ 140800средняяВойти и решать
Уравнение с пропущенными цифрами#23416
Задано уравнение вида A+B=C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно. Найти только одно из  возможных решений.
 
Входные данные
Вводится строка, представляющая собой заданное уравнение без пробелов. Длина уравнения не превышает 80 символов. 
 
Выходные данные
Требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "No solution".
 

Примеры
№ Входные данные Выходные данные
1 ??2?4+9?=355 00264+91=355
 
Динамическое программированиеДинамическое программирование по подстрокам
✓ 2✗ 371 300средняяВойти и решать
Шаблон и слово#23413
Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая).
 
Входные данные 
В первых двух строках записаны шаблон и слово: в одной из них записан шаблон - последовательность больших  латинских букв, "?" и "*", в другой  - слово, состоящее только из больших латинских букв (строки короче 100 символов).

Выходные данные
Вывести YES, если слово подходит, NO, если не подходит.
 
Примеры
№ Входные данные Выходные данные
1
ABBCDA
A*CDA
 YES
2
AADAAVA
A*DA*AA*
 NO
 
Динамическое программирование: один параметрСтроки
✓ 5✗ 121 100средняяВойти и решать
Восстановление скобок#23412
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
 
Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.
 
Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109.
 
 
Примеры
№ Входные данные Выходные данные
1 ????(? 2
 
Динамическое программирование по подстрокамДинамическое программирование: два параметра
✓ 116✗ 190800средняяВойти и решать
*Удаление пробелов#23384
На вход подается одна строка текста (не больше 255 символов).
Нужно вывести эту же строку, удалив все парные пробелы (то есть, если где-то в строке идет подряд 2 или более пробелов, то в этом месте нужно оставить только один из них).
 
Примеры
№ Входные данные Выходные данные
1    My    name is    Vasya...  My name is Vasya...
Алгоритмы обработкиСтроки
✓ 4 047✗ 8 909500лёгкаяВойти и решать
Перестановка слов#23383
На вход подается одна строка, в которой записаны фамилия и имя человека (разделенные ровно одним пробелом).
 
Выведите эту же информацию, однако сначала имя, а потом фамилию.
 
Пример
№ Входные данные Выходные данные
1 Pupkin Vasya Vasya Pupkin
 
Ввод, вывод данныхСтроки
✓ 7 591✗ 7 695100лёгкаяВойти и решать
День рождения#23382
На день рождения пришли N человек. В некоторый момент именинник  решил, что пора устроить какую-нибудь игру. Он выяснил, что i-й человек  согласен вступить в игру, если в ней уже принимают участие не менее A[i] и не более B[i] человек. Единожды вступив в игру, никто из нее 
не выходит.

Требуется выяснить, может ли именинник установить такую 
последовательность вступления в игру, что в итоге все 
присутствующие станут ее участниками. (Сам именинник в игре участия 
не принимает.) 
 
Входные данные. 
Сначала вводится количество гостей N (1<=N<=100). Затем вводится 
N пар чисел A[i] и B[i] (все эти числа из диапазона от 0 до N-1).
 
Выходные данные. 
Если можно установить последовательность вступления гостей в игру, 
чтобы в итоге все стали ее участниками, то нужно вывести номера гостей 
в том порядке, в каком они могут вступать в игру. Если всех вовлечь 
в игру не удастся, выведите одно число - 0.
 
Пример 1
Пример входного файла
5
4 4
0 3
1 4
1 3
2 2
 
Пример выходного файла
2 3 5 4 1
 
Пример 2
Пример входного файла
3
1 1
1 1
1 1
 
Пример выходного файла
0
 
Пример 3
Пример входного файла
1
0 0
 
Пример выходного файла
1
Жадный алгоритмРазбор случаев
—Войти и решать
Список#23381
В фирме, выпускающей компьютерные комплектующие, все изделия получают последовательные номера от 1 до N. Каждое изделие после его изготовления поступает в отдел контроля качества, где оно проверяется, и либо уходит в продажу, либо заносится в список бракованных изделий и списывается. К сожалению, список бракованных изделий иногда оказывается чересчур длинным. Тогда для его сокращения подряд идущие числа заменяются интервалом: через тире указываются номера первого и последнего изделия интервала.
Например, вместо 
1,3,4,5,6,7,8,10,12,16,17,20,21,22,23,24
записывается
1,3-8,10,12,16-17,20-24
 
Напишите программу, которая по полному списку номеров бракованных изделий выдаст этот список в сокращенном виде.
 
Входные данные
В первой строке вводится сначала число N - общее количество изделий, затем число M - количество изделий, оказавшихся бракованными. Во второй строке вводятся в возрастающем порядке номера бракованных изделий. 
 
Выходные данные
Выведите в одной строке список номеров бракованных изделий в сокращенном виде. Интервалы должны разделяться запятой. В строке не должно быть пробелов.
 
Ограничения
1<=M<=N<=1000000.
 
Примеры
№ Входные данные Выходные данные
1
10 5 
1 3 5 7 9
 1,3,5,7,9
2
40 16
1 3 4 5 6 7 8 10 12 16 17 20 21 22 23 24
 1,3-8,10,12,16-17,20-24
3
11 11
1 2 3 4 5 6 7 8 9 10 11
 1-11
4
10000 1 
5
 5
Алгоритмы обработкиОдномерные массивы
✓ 1 506✗ 1 960600лёгкаяВойти и решать
Два массива#23379
Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.
 
Входные данные
В первой строке ввода записано число N - количество элементов в первом массиве. Во второй строке  - N чисел (элементы массива). В третьей строке записано число M - количество элементов во втором массиве. В четвертой строке  - элементы второго массива.
Количество элементов каждого массива не превышает 100. Сами элементы по модулю не превышают 1000. Все числа целые.
 
Выходные данные
Выведите те элементы первого массива, которых нет во втором.Элементы необходимо вывести в том порядке, в каком они идут в первом массиве.
 
Примеры
№ Входные данные Выходные данные
1
7
3 1 3 4 2 4 12
6
4 15 43 1 15 1
 3 3 2 12
 
Алгоритмы обработкиОдномерные массивы
✓ 4 171✗ 5 402300лёгкаяВойти и решать
Британские ученые (В, А', А)#23376
Согласно исследованиям британских ученых, люди способны воспринимать слова в тексте, если в каждом слове оставить на месте первую и последнюю буквы, а остальные перемешать произвольным образом; например, слово "программа" может быть прочитано даже если оно записано как
"пгрроммаа" или "пморгамра".
Вам дан словарь с несколькими словами, а также некоторый текст. Для каждого слова из текста определите, можно ли его прочитать как одно из слов словаря, руководствуясь правилами, описанными выше.
 
Формат входных данных
В первой строке записано одно целое число n (1 <=  n <= 105)  - количество слов в словаре.
В следующих n строках записаны слова из словаря, по одному на строку. Гарантируется, что все слова в словаре различны.
В следующей строке записано одно целое число m (1 <= m <= 105) - количество слов в тексте.
В следующих m строках записаны слова из текста, по одному на строку.
Каждое слово состоит только из строчных букв латинского алфавита; ни в какой строке ввода нет пробелов и других разделителей. Суммарная длина всех слов не превосходит 105.
 
Формат выходных данных
Для каждого слова из текста выведите "YES" если его можно прочесть как одно из слов словаря, и "NO" в противном случае. Ответы для слов из текста следует выводить в том же порядке, в
котором слова перечислены во вводе; следует выводить по одному ответу на строку.

 
Ввод Вывод
4
bird
sun
lksh
summer
4
brid
snu
sommer
sis		 YES
NO
NO
NO
Задача на реализациюСловари
✓ 18✗ 68900средняяВойти и решать
Сливаемся!#23375
Слияние двух упорядоченных последовательностей чисел в одну упорядоченную  основная идея сортировки слиянием. Эта сортировка работает быстро, а слияние двух упорядоченных после-
довательностей легко выполняется в том числе и человеком вручную.

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

Входные данные
В первой входного файла строке содержится число N  количество элементов в каждой из исходных последовательностей. Во второй и третьей строках записано по N чисел и знаков вопроса 
содержимое первой и второй последовательности соответственно. В четвертой строке записано 2хN чисел -  результат слияния.
Выходные данные
Вывод должен содержать 2 строки по N чисел в каждой: какой-нибудь из вариантов восстановления исходных последовательностей, которые при слиянии дадут тот же результат. Если
в исходных данных в последовательности стояло число, то в выходных данных на том же месте должно стоять то же число.

Ввод Вывод
2
? 4
3 ?
1 3 4 5		 1 4
3 5

Разбор случаевСортировка слиянием
—Войти и решать
Мобильный интернет#23374
Мобильный интернет прочно вошел в нашу жизнь. Операторы связи предлагают различные способы оплаты мобильного интернета и, зная свои потребности, можно выбрать наиболее дешевый
из подходящих тарифов.

Рассмотрим следующие тарифные планы:
1. Единовременно каждый месяц платится 350Р за 3000 мегабайт. Также можно докупать дополнительные пакеты по 300 мегабайт за 30Р каждый, которые действуют до конца месяца.
2. 500 мегабайт в день за 29Р в сутки. За дни, в которые интернет не используется (скачано 0 мегабайт), плата не взимается.
3. Оплата за использованный трафик  1, 2Р за 1 мегабайт.
4. Безлимитный интернет на месяц за 790Р.
5. Лимитированный тариф  16000 мегабайт на месяц за 590Р.
 
По известному количеству трафика в каждый из 31 дней одного месяца определите, сколько денег уйдет на оплату интернета при использовании каждого из тарифных планов или сообщите, что использование тарифа невозможно (недостаточно трафика). 

Входные данные
В единственной строке входных данных содержится тридцать одно целое неотрицательное чис-
ло  планируемый трафик по дням следующего месяца в мегабайтах.

Выходные данные
Выведите пять чисел в отдельных строках  стоимость трафика за месяц при использовании
соответствующего тарифа или −1, если требуемое использование интернета недопустимо в рамках
соответствующего тарифа (например, суммарный или суточный трафик превосходит ограничение
тарифа).
Стоимость требуется вывести в формате <рубли> <копейки>.

Ввод Вывод
3001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 380 0
-1
3601 20
790 0
590 0

Вычисление по заданной формулеЗадача на реализацию
✓ 0✗ 5—Войти и решать
Прямоугольное поле чудес (В, А',A)#23372
Коля попал на телеигру "Прямоугольное поле чудес". В финале этой игры Коле показали прямоугольное поле размера n х m клеток, в каждое клетке которого записано целое число.  Коля может
заменить числа в некоторых клетках на противоположные (т.е. вместо числа x записать в клетку число −x). Коля выиграет автомобиль, если сумма чисел в каждой строке и в каждом столбце будет равна нулю. Помогите Коле найти нужную расстановку чисел, либо определите, что ее не существует и Коля не сможет выиграть.
 
Формат входных данных
В первой строке записано два целых числа n и m (1 <= n, m <= 5)  - размеры поля.
В следующих n строках записано по m целых чисел, разделенных пробелами - числа, записанные в клетках поля. Все числа по модулю не превосходят 106.
 
Формат выходных данных
Если ответ существует, в первой строке выведите YES, в следующих n строках выведите по m чисел через пробел - числа в клетках поля после изменений/
Если ответа не существует, в первой строке выведите NO.
Ввод Вывод
3 3
1 1 2
2 2 4
3 3 6		 YES
1 1 -2
2 2 -4
-3 -3 6
Задача на реализациюРекурсия
✓ 13✗ 511 200средняяВойти и решать
Опять двойка (В, В')#23370
Пете нравится цифра 2. Он считает число красивым, если в его десятичной записи ровно две цифры 2. Петя хочет получить большой список красивых чисел и повесить его на стенку.
ПомогитеПете и выведите все красивые числа, не превосходищие n.
 
Формат входных данных
В первой и единственной строке записано одно целое число n (1 <= n <= 106).
 
Формат выходных данных
Выведите все целые положительные числа, не превосходящие n, в десятичной записи которых ровно две цифры 2.  Числа следует выводить в порядке возрастания, по одному на строке.
 
Ввод Вывод
179 22
122
1  
 
Замечание
Обратите внимание, что список может быть пустым, в этом случае ничего выводить не нужно.
Задача на реализациюСтроки
✓ 47✗ 77800средняяВойти и решать
Овечка Толя (C, B')#23369
Овечка Толя умеет клонироваться - тогда рядом с ней появляется такая же овечка с той же логикой и привычками.
Когда овечка встречает n стогов сена то происходит следующее:

-  Если n меньше 4 то овечка выкидывает эти n стогов сена в ближайший овраг. Иначе:

-  Если n делится на 5, то овечка сбрасывает n/5 стогов сена в ближайший овраг; клонируется;
    сама обрабатывает 3n/5 стогов сена с помощью этой же процедуры, а ее клон обрабатывает 
     оставшиеся n/5 стогов сена с помощью этой же процедуры. Иначе:
 
- Овечка съедает 4 стога сена и обрабатывает оставшиеся n-4 стогов с помощью этой же процедуры.

Овечка Толя однажды увидела n стогов сена - это число вам дано. Сколько стогов сена будет
съедено ей и всеми е клонами при описанном процессе ?
 
Формат входных данных
 В первой строке содержится натуральное число n <= 6 n <= 106
 
Формат выходных данных
Выведите количество, стогов съеденных в итоге Толей и клонами
 
Ввод Вывод
29 8
Задача на реализациюРекурсия
✓ 42✗ 44900средняяВойти и решать
Поделиться
Класснуть