Информатика

15 732 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Сливаемся!#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
Задача на реализациюРекурсия
✓ 23✗ 24900средняяВойти и решать
Организация конференции (С, B')#23368
Недавно в солнечный весенний день директору Летней Флатландской Компьютерной Школы (ЛФКШ) Сергею Александровичу пришла в голову идея организовать первую флатландскую конференцию для школьников по программированию. Теперь перед ним стоит задача выбрать место проведения. 

Флатландия представляет собой прямоугольник из m строк и n столбцов, в каждой из клеток которого расположен один город? Сергей Александрович уже посчитал для каждого города количество желающих принять участие в конференции. Известно, что флатландцы не любят далеко ездить, так что в каком бы городе она проводилась,  в конференции смогут принять участие только школьники из самого города и соседних с ним по стороне городов. Формально говоря, если конференция проводится в городе, находящемся в i-ой строке и j-ом столбце, то в этой конференции будут участвовать школьники из городов (i, j), (i − 1, j) ( при условии, что i > 1) ,  (i + 1, j) (при условии, что i < m), (i, j − 1) (при условии, что j > 1) , и (i, j + 1) , (при условии, что j < n).
Сейчас Сергей Александрович хочет понять,  в каких городах возможно поселить всех приезжих участников.  Пока он выясняет количество доступных мест в гостиницах Флатландии, вам предстоит посчитать для каждого из возможных городов проведения, скольким школьникам потребуется предоставить жиль на время конференции.
Обратите внимание на то, что школьникам, живущим в том же городе, в котором проводится конференция, поселение не нужно.

Формат входных данных
В первой строке записаны два числа m и n (1 <= m, n <= 350) - размеры Флатландии. В каждой из последующих m строк содержатся по n чисел.
В i-ой стоке и j-ом столбце содержится число ai,j ( 0<=  ai,j  <=10000)  -  количество школьников из города (i, j),  желающих принять участие в конференции.
Формат выходных данных
Выведите m строк по n чисел в каждой. Число в строке с номером i и стобце с номером j должно равняться количеству приезжих участников конференции, если местом проведения будет
выбран город, с координатами (i, j).
 
Ввод Вывод
3 4
1 0 3 2
5 6 1 2
1 1 0 11		 5 10 3 5
8 7 11 14
6 7 13 2
1 1
5		 0
Двумерные массивыЗадача на реализацию
✓ 20✗ 21900средняяВойти и решать
Совсем другие штурмовики#23366
Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — dt , здоровье — h единиц.

Бой происходит в пошаговом режиме, пока с обеих сторон есть живые солдаты. Каждый шаг боя представляет собой одновременный выстрел всех живых солдат с обеих сторон. Каждый солдат может атаковать любого противника, но только одного. Несколько солдат с одной стороны могут атаковать одного и того же вражеского солдата. Здоровье солдата уменьшается на суммарную силу атаки солдат, атакующих его в течение этого хода. Если здоровье солдата в конце хода стало меньше или равно нулю, он погибает.

Ваша задача — уничтожить армию неприятеля, задействовав минимальное число штурмовиков, вне зависимости от действий противника, либо определить, что уничтожить вражескую армию не получится.

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*105),  de, dt , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( de, dt , h <= 109). В следующей строке задано n натуральных чисел ai — число единиц здоровья i-го солдата армии противника (ai <= 109).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.
 
Ввод Вывод
3 3 1 1 2
1 2 3		 3
4 10 2 1 2
1 2 1 2		 5
3 1 1 2 5
1 2 3		 -1
Бинарный поискБинарный поиск по ответу
✓ 1✗ 31 200средняяВойти и решать
Коды Грея#23365
На занятиях по дискретной математике Сереже рассказали про двоичные коды Грея — это такое упорядочение всех 2n различных двоичных векторов длины n, что любые два соседних, а также первый и последний, вектора различаются ровно в одном разряде.

Для закрепления материала преподаватель задал им следующее задание: в коде Грея в каждом двоичном векторе ровно один бит заменен на знак вопроса «?». Требуется заменить обратно все знаки вопроса «?» на «0» или «1», чтобы получился код Грея.

Преподаватель обещал бонус на экзамене тому из студентов, кто первым справится с заданием. Помогите Сереже решить задачу или скажите, что это невозможно, и преподаватель задал нераз- решимое задание.

Формат входных данных
В первой строке содержится целое число n — длина двоичных векторов. Следующие 2n строк содержат двоичные вектора длины n, в каждом из которых ровно один символ заменен на знак вопроса «?».
Формат выходных данных
В первой строке выведите «YES», если решение существует, и «NO» — в противном случае. В случае положительного ответа выведите исходный код Грея, если возможных вариантов ответа несколько, выведите любой.
 
Ввод Вывод
2
0?
0?
1?
1?		 YES
00
01
11
10
3
?00
0?1
01?
0?0
?10
1?1
10?
1?1		 NO

Система оценки
 
Номер подзадачи Баллы Ограничения Комментарии
1 37 1<=n<=4 Баллы начисляются, если все тесты пройдены.
2 63 1<=n<=12 Баллы начисляются, если все тесты этой и предыду- щих подзадач пройдены.

 
КонструктивРекурсия
✓ 2✗ 261 100средняяВойти и решать
Билеты в театр#23364
Не так давно в городе будущего Иннополис достроили первый театр. После тяжелой рабочей недели студенты университета решили сходить в театр. Утром они приехали к открытию кассы театра, чтобы успеть купить билеты. Билет в театр стоит 100 рублей.

Оказалось, что у каждой девочки есть ровно одна банкнота номиналом 100 рублей, а у каждого мальчика — номиналом 1000 рублей. До ребят еще никто не успел купить билет, поэтому касса пуста. Это значит, что кассир выдает сдачу только теми банкнотами, которые получил от других ребят, стоявших раньше в очереди. Кассир обслуживает всех по очереди и не начинает обслуживать следующего человека, если еще не продал билет или не выдал требуемую сдачу предыдущему.

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

Способы считаются различными, если существует такое место в очереди, что в одном из них на этом месте стоит девочка, а в другом — мальчик.

Формат входных данных
В первой строке задано два целых неотрицательных числа n и m, где n — количество девочек, m — количество мальчиков (1<= n + m < 104).

Формат выходных данных
Выведите остаток от деления числа способов расставить студентов в очередь, чтобы все смогли купить билет, на 109 + 7.
 
Ввод Вывод
18 2 10
8 1 0
12 1 4
Динамическое программированиеДинамическое программирование: два параметра
✓ 3✗ 651 100средняяВойти и решать
Сенсор#23362
Артем создает интерактивный сенсор для игры в кости. Сенсор встроен в стол и может считать суммарное число точек на гранях всех брошенных костей, прилегающих к сенсору (то есть, на нижних гранях). Позже Артем понял, что для игры нужно считать сумму не на нижних, а на верхних гранях. Артем хочет написать программу, которая по сумме на нижних гранях сможет находить количество различных возможных сумм на верхних гранях. Но так как Артем не силен в программировании, он поручает эту задачу вам.

Сенсор выдает число s равное суммарному числу точек на нижних гранях игральных костей.
Все бросаемые кости шестигранные и удовлетворяют условию правильной игральной кости, то есть сумма точек на противоположных гранях кубика равна семи (1 и 6, 2 и 5, 3 и 4). Вам необходимо найти количество возможных сумм на верхних гранях кубиков.
 
Формат входных данных
В первой строке входного файла задано число s  сумма на нижних гранях костей (s <= 105).
 
Формат выходных данных
Выведите одно число: количество различных всевозможных сумм на верхних гранях костей.
 
Ввод Вывод
2 2
4 4
 
Пояснение к примеру
В первом примере на нижних гранях могло выпасть 1 + 1 или 2, суммы на верхних гранях 12 и
5, соответственно.
КомбинаторикаПеребор
✓ 1✗ 91 100средняяВойти и решать
Динамика - 03#23262
Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Прибавить 3
Программа для исполнителя Громозека – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 26 и при этом траектория вычислений содержит число 8? 
ЕГЭ_информатикаЕГЭ-13. Динамическое программирование
900средняяВойти и решать
Динамика - 02#23261
Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Программа для исполнителя Громозека – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 15 и при этом траектория вычислений содержит число 11? 
ЕГЭ_информатикаЕГЭ-13. Динамическое программирование
1 000средняяВойти и решать
Динамика - 01#23260
Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
3. Прибавить 5
Программа для исполнителя Громозека – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 7? 
ЕГЭ_информатикаЕГЭ-13. Динамическое программирование
900средняяВойти и решать
Первые одинаковые#23095
Дано предложение. Определить порядковые номера первой пары одинаковых соседних символов. Если таких символов нет, то вывести на экран слово NO.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.


Входные данные
В первой строке задается  предложение длиной не более 255 символов (в начале и конце предложения нет пробелов).

Выходные данные 
Необходимо вывести через пробел порядковые номера первой пары одинаковых соседних символов, или слово "NO" - если такой пары соседних символов нет (первый символ в предложении имеет порядковый номер 1).

 
Примеры
№ Входные данные Выходные данные
1 foresete NO
2 haah 2 3
СимволыСтроки
✓ 242✗ 676600лёгкаяВойти и решать
Сколько "n" перед запятой#23094
Дано предложение. Определить количество букв "n", предшествующих первой запятой предложения. Если запятой нет, то считать до конца предложения. 

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается исходное предложение.

Выходные данные: выведите одно число - ответ на задачу

Примеры
№ теста Входные данные Выходные данные
1 fore, sete. 0
2 hanah. 1
СимволыСтроки
✓ 262✗ 600500лёгкаяВойти и решать
Сколько "o"#23093
Дано предложение, в котором нет символа "-". Определить количество букв "o" (англ.) в первом слове. В начале предложения могут быть пробелы.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в единственной строке задается исходное предложение.

Выходные данные: необходимо вывести количество букв "о" (англ.) в первом слове.

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1    fore  sete. 1
2 hal ah. 0
СимволыСтроки
✓ 132✗ 322600лёгкаяВойти и решать
Префикс#23092
Дано два слово. Определить, сколько начальных букв первого слова совпадает с начальными буквами второго слова

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается два слова через пробел
Выходные данные: необходимо вывести количество совпадающих с начала букв

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 fore forest 4
2 forest torest 0
СимволыСтроки
✓ 126✗ 316600лёгкаяВойти и решать
Одинаковые в начале#23091
Дана последовательность символов, в начале которой имеется некоторое количество одинаковых символов. Определить это количество.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается последовательность символов.

Выходные данные: необходимо вывести количество одинаковых симвлов в начале строки.

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 foresete 0
2 ааав 3
СимволыСтроки
✓ 114✗ 442600лёгкаяВойти и решать
Сколько "i"#23090
Дана строка, разбитая на предложения. Все предложения заканчиваются знаком точка. Определить количество букв 'i' в первом предложении. 

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: программа получает на вход строку.

Выходные данные: необходимо вывести количество букв 'i' в первом предложении.

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 foresete. forest. 0
2 firist. forist 2
СимволыСтроки
✓ 177✗ 352500лёгкаяВойти и решать
Перевертыш#23089
Дано слово. Проверить, является ли оно "перевертышем", (то есть читается одинаково как сначала, так и с конца).

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается слово.

Выходные данные: необходимо вывести слово "YES", если слово является перевертышем, и слово "NO" - в противном случае

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 foresete NO
2 halah YES
СимволыСтроки
✓ 136✗ 231500лёгкаяВойти и решать
Поделиться
Класснуть