Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Алгоритм#27014
Реализуйте на одном из языков программирования алгоритм, представленный на схеме. Выражение S mod K означает вычисление остатка от деления S на K.
В первой строке ввода содержится целое число N (1 ≤ N ≤ 100). Далее следует N строк, содержащих по одному целому числу в диапазоне от 1 до 1000.
Вывести сообщение Yes или No как указано в алгоритме.


 
Ввод Вывод
3
2
1
3
 Yes
3
1
2
3
 No
Линейные алгоритмыУсловный операторЦикл for
✓ 40✗ 79800средняяВойти и решать
*Лапта#25963

При игре в лапту одна команда ловит мяч и пытается осалить им бегущего. Игрок другой команды должен, перед тем как бежать, ударить мяч в поле. Известно, на какое максимальное расстояние он может ударить, а также скорости и начальные координаты игроков другой команды. Требуется выбрать направление и силу удара так, чтобы минимальное время, которое потребуется другой команде, чтобы поднять мяч с земли, было наибольшим. (Пока мяч летит, игроки стоят на местах.)


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

- в первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, \(D <= 1000\), \(N <= 200\)); 
- в следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, \(–1000 <= x_i <= 1000\), \(0 <= y_i <= 1000\), \(0 < v_i <= 1000\)).
Никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (\(y >=  0\)).


Выходные данные: выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью \(10^{–3}\).
 

Примеры
№ Входные данные Выходные данные
1
10 2
1 1 1
-1 1 1
9.05539
0.00000 10.00000
Бинарный поиск по ответуКвадродеревоЭлементарная геометрия
✓ 7✗ 781 400средняяВойти и решать
Дело в шляпах#25919
Как-то раз в город Шляп заехал известный парикмахер. До его приезда парикмахеры были явно не очень, так как все жители города предпочитали ходить в шляпах. Но наконец-то настало время снять шляпы! 

Парикмахер открыл свою временную парикмахерскую и работает без остановок, пока есть посетители. Жители приходят к нему в тот момент времени, когда им это удобно, и становятся в очередь. Каждому из них требуется своё время на создание индивидуальной стрижки. Парикмахер зовёт первого человека в порядке очереди, стрижёт его, и после ухода посетителя сразу зовёт следующего.
Стоять в очереди скучно, поэтому если подряд приходят двое или более людей в шляпах одинакового фасона  они начинают между собой активно общаться и необычайно гордиться своими шляпами (но всё равно заходят на стрижку, если уж их очередь подошла). Однако, если следом за ними в очередь встаёт человек в шляпе другого фасона, то вся группа подряд стоящих людей в одинаковых шляпах подозрительно смотрит на только что пришедшего "чужого" и совсем уходит из очереди. При этом очередь сдвигается и может появиться новая группа общающихся людей.
 
Так как обсуждение одинаковых шляп  это очень интересная тема, появление "чужого" человека в очереди привлекает внимание группы сильнее, чем парикмахер. Поэтому если одновременно пришёл человек в другой шляпе и парикмахер зовёт следующего  вся группа уходит, даже если один из них должен был сейчас зайти на стрижку. К парикмахеру при этом зайдёт следующий из оставшейся очереди, возможно даже только что пришедший "чужой".
Местного шляпника теперь интересует, каким жителям ему больше не нужно будет делать шляпы, так как они будут ходить с новыми стильными стрижками?
 
Формат входных данных
В первой строке содержится число N (1 <= N <= 105)  количество людей, которые придут к парикмахеру.
Каждая из следующих N строк обозначает пришедшего к парикмахеру жителя и содержит по три числа: фасон шляпы (все фасоны местного шляпника пронумерованы от 1 до 109 ), момент времени прихода s (1 <= s <= 109), и время на стрижку t (1 <= t <= 109). Строки упорядочены по времени прихода жителей. Гарантируется, что все приходят в разное время. Так как парикмахер очень крут, гарантируется, что он успеет постричь всех жителей до момента времени 2 · 109, даже если бы из очереди никто не уходил.
 
Формат выходных данных
В единственной строке выведите через пробел номера людей в очереди в порядке возрастания, которых парикмахер всё-таки пострижёт. Люди нумеруются в порядке прихода в очередь, начиная с 1.

Ввод Вывод
5
1 2 7
2 4 3
2 6 2
1 7 3
3 8 2		 1 4 5

Задачи на моделированиеОчередьРазбор случаев
✓ 5✗ 22900средняяВойти и решать
Orders#24733
Блейз отправляет приказы на перемещение своим войскам, собранным из жителей одной из теней. К сожалению, они не понимают амберский язык, поэтому Блейзу приходится отправлять им сообщения на их родном языке.
В этом и заключается проблема: Амберийский принц плохо знает орфографию этого языка, поэтому иногда он делает ошибки в словах, но не более одной ошибки в слове.
В языке очень много слов, поэтому если в слове изменится хотя бы одна буква, то его смысл может кардинально измениться. Если армия не правильно поймет приказ, то вся военная кампания может провалиться. Поэтому Блейзу очень важно проверять правильность в написании слов. Он решил попросить вас помочь ему.
Вы должны создать программу, которая будет выводить в лексикографическом порядке все возможные слова, которые Блейз мог пытаться написать с учетом того, что он мог ошибиться 1 раз.
 
Входные данные
В первой строке на вход подается числа n и m - количество приказов, которые отдал Блейз, и количество команд, которые понимают его войска соответственно. (1 <= n, m <= 5000)
В следующей строке на вход подаются m слов - команды, которые понимают войска Блейза.
В следующих n строках на вход подаются слова - приказы, которые отдает Блейз.
Все строки длиной не превышают 100.
 
Выходные данные
Выведите n строк: в строке номер i содержится ответ на задачу для приказа Блейза номер i. Строки, являющиеся ответом на этот запрос, выводятся через пробел в одну строку.
 
Пример
Ввод
5 5
is in if on of
it
in
of
ij
op

Вывод
if in is
if in is on
if of on
if in is
of on

(с) Евгений Григорьев
БорОбход в глубинуПеребор
✓ 7✗ 241 100средняяВойти и решать
Златопольский 13.6#24662
Известны максимальные скорости 20-ти моделей автомобилей. Все значения выражены в км/ч.
Написать программу, которая организовывает ввод исходных данных в структуру и выводит названия моделей автомобилей с самой маленькой и самой большой максимальной скоростью

Входные данные: 
20 строк в формате <Марка автомобиля> <Максимальная скорость>


Выходные данные:
Необходимо вывести через пробел названия двух моделей автомобилей, сначала автомобиль с наибольшей максимальной скоростью, затем через пробел автомобиль с наименьшей максимальной скоростью
Алгоритмы обработкиИспользование сортировкиОдномерные массивы
✓ 41✗ 78400лёгкаяВойти и решать
Таймер#23405
Таймер - это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал.
 
Входные данные:
В первой строке записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60. 
Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0. 
А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.
 
Выходные данные:
В ответе выведите в формате ЧЧ:ММ:СС время, когда прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол-во> days. Например, если сигнал прозвучит на следующий день - то +1 days. 

Примеры
№ Входные данные Выходные данные
1
01:01:01 
48:0:0
 01:01:01+2 days
2
01:01:01
58:119
 02:01:00
3
23:59:59
1  
 00:00:00+1 days
Дата и времяСтрокиУсловный оператор
✓ 33✗ 115800средняяВойти и решать
Увеличение чисел - 2#23386

В первой строке входных данных записано число N (от 1 до 100). В каждой из последующих N строк записано сначала имя человека (не более 20 символов, без пробелов), а затем через пробел число (от 1 до 200) - его возраст.

Требуется вывести информацию в том же формате, увеличив число в каждой строке (кроме первой, где записано число N) на 1.

 
Примеры
№ Входные данные Выходные данные
1
2
Vasya 15
Emmanuil 137
2
Vasya 16
Emmanuil 138
 
Ввод, вывод данныхЛинейные алгоритмыЦикл for
✓ 1 344✗ 1 174300лёгкаяВойти и решать
Интернет-магазин#23373
При покупке товаров в интернет-магазинах все выбранные товары складываются в корзину. При этом покупатели могут забыть добавить какой-нибудь из нужных им товаров.
Для того, чтобы покупатели остались довольны покупкой, а магазин получил больше прибыли существует механизм рекомендаций, который определяет, какие товары обычно покупают вместе с набором уже выбранных. Например, если покупатель положил в корзину ластик, то, наверняка, ему также понадобится карандаш.

Вам необходимо разработать сервис рекомендаций, который по истории предыдущих заказов разработает для покупателя рекомендации, основанные на текущем состоянии его заказа.
Рекомендации должны быть двух типов: "с этим товаром всегда берут следующие товары" и "с этим товаром часто берут следующие товары".  При этом "часто" понимается как 50% и более.
Например, если покупатель хочет купить два товара A и B, а предыдущие заказы были вида (A,
D), (B, C, E), (C, F), (C, E, F, G) и (A, B, C, E), то товары C и E надо рекомендовать как те, что
покупается всегда (вместе с товаром B), а D  как тот, что покупается часто (50% случаев заказов
с товаром A).

Если товар всегда покупался с одним из заказанных, то необходимо включить в число часто покупаемых и те, которые часто встречаются с этим товаром (не менее чем в 50% случаев) в ранее сделанных заказах. Таким образом, дополнительно к товарам покупаемым часто, добавится товар F, который часто покупается с товаром C. Товар G рекомендовать не нужно, т.к. он встречается меньше, чем в 50% заказов вместе с товаром C.

Не нужно рекомендовать товары, которые уже выбрал покупатель. Если товар можно рекомендовать как "часто" и "всегда", то следует рекомендовать его только как "всегда".

Входные данные
В первой строке входного файла записывается количество старых заказов N. Следующие N строк содержат названия товаров, сделанных в этом заказе. Каждое название состоит из одного слова, слова разделены пробелами. В следующей строке содержится описание текущего заказа: набор названий товаров, разделенных пробелами.

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

Слова следует разделять пробелами. Порядок вывода не важен.

Ввод Вывод
5
A D
B C E
C F
C E F G
A B C E
A B		 C E
D F

Задача на реализациюЗадачи на моделированиеПересечение множеств
1 200средняяВойти и решать
Мишина машина (В', В)#23371
Миша путешествует по стране на автомобиле. В стране есть несколько городов, соединенных дорогами, на каждой дороге может быть некоторое число ям.
Мише очень нравится ездить по дорогам на которых много ям, -  он участвует в популярном телешоу "Неперсистентные машинки" и за каждую посещенную яму ему платят по одной монете.

Он начинает путь в любом из городов страны и затем путешествует по дорогам между городами. По каждой дороге Миша может проехать сколько угодно раз но ему платят за посещение любой ямы только один раз.
Помогите Мише найти самый выгодный маршрут.

Формат входных данных
В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 105 , 0<= m <= 105)
В следующих m строках содержится по три целых числа, разделенных пробелами номера, -  городов, соединенных очередной дорогой и количество ям на этой дороге соответственно. Количество ям на каждой дороге неотрицательное число не превосходящее 106.
 
Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.
 
Формат выходных данных
Выведите одно число максимальное количество монет которое Миша сможет получить.
 
Ввод Вывод
4 4
1 2 1
2 3 1
1 4 1
4 3 0		 3
4 2
1 3 5
2 4 4		 5
 
Замечание
Все дороги двусторонние; проехав в любую сторону по дороге, Миша посещает все ямы на этой дороге. Обратите внимание, что между некоторыми парами городов может не существовать пути по имеющимся дорогам.
Кратчайшие пути в графеОбход в ширинуСпособы задания графа
✓ 22✗ 49900средняяВойти и решать
Интересные числа (С', C)#23334
Маленький Вася очень любит числа, а особенно сильно он любит интересные числа. Вася считает число x интересным,  если сумма квадратов его цифр делится на число 7. Например, число 123 -
интересное, потому что 12 + 22 + 32 = 14 делится на 7, а число 16 - нет, потому что 12 + 62 = 37 не делится на 7. Однажды Вася увидел на доске число x, он сразу же захотел узнать величину минимального интересного числа, которое строго больше чем x.  Так как Вася еще слишком юн, он обратился к вам за помощью в решение этой задачи.
 
Формат входных данных
Во входном файле содержится единственное целое число x - число, написанное на доске 0<= x <= 105
 
Формат выходных данных
В единственную строку выходного файла выведите минимальное интересное число, которое строго больше чем x.
Ввод Вывод
1 7
0 7
35 70


 
Арифметические алгоритмы (Теория чисел)Вывод формулыЦиклы
✓ 60✗ 108600лёгкаяВойти и решать
Число способов#22015
В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку 
либо вправо, либо вниз (влево и вверх перемещаться запрещено).
Посчитайте, сколько есть способов у игрока попасть в правую
нижнюю клетку.
 
Входные данные
Во входном файле задано два числа N и M - размеры таблицы (1<=N<=10,
1<=M<=10).
 
Выходные данные
В выходной файл запишите искомое число способов. 
 
Примечание
При указанных ограничениях, число способов входит в тип Longint.
 
Пример входного файла
2 3
 
Пример выходного файла
3
 
Пояснение
Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие 
способы попасть из левого верхнего угла в правый нижний:
1) вниз, вправо, вправо
2) вправо, вниз, вправо
3) вправо, вправо, вниз
 
Еще один пример входного файла
3 3
 
Пример выходного файла
6
 
Динамическое программирование на таблицахДинамическое программирование: один параметрКомбинаторика
✓ 21✗ 29800средняяВойти и решать
Кладовка из Простоквашино#21996
Сразу же после заселения в новый дом в Простоквашино кот Матроскин, Шарик и дядя Фёдор затеяли ремонт. Непосредственно перед его началом они обнаружили, что в доме отсутствует кла- довка для стройматериалов, и наспех пристроили её к дому. Как только вспомогательное строение было готово, встал вопрос о необходимости провести туда электричество и повесить лампочку.

Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узна- ли много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно C рублей. Правда, лампочки в магазине не самые качественные, и вклю- чить каждую из них можно только K раз, а на K + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в D рублей.

Узнав всё это, экономный Матроскин составил поминутный график из N предполагаемых посе- щений кладовки. Каждый визит в новое помещение задаётся моментом входа ai и моментом выхода bi . Таким образом, i-й визит продолжается ровно bi − ai минут.

Разумеется, во время посещения свет в кладовке должен быть включён. Если в начале очередного визита лампочка не горит, то посетитель сразу её включает, а вот уходя он может как выключить свет, так и оставить его включенным. Если во время очередного включения лампочка перегорает, то её приходится немедленно заменить. Теперь Матроскина интересует минимальное количество рублей, которое придётся потратить, чтобы выполнить все запланированные визиты в кладовку. Изначально в помещении уже висит новая лампочка в выключенном состоянии.

Формат входных данных
В первой строке входных данных записаны четыре целых числа N, K, C, D — количество пла- нируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (1 <= N, K <= 200 000, 1 <= C, D <= 109 ). В следующих N строках даны по два целых положительных числа ai и bi , описывающих пред- полагаемые визиты в кладовку (1 <= ai < bi <= 109 ). Посещения не пересекаются по времени и упорядочены, то есть bi < ai+1.

Формат выходных данных
Выведите одно целое число — минимальное количество рублей, которое придётся потратить жителям дома, чтобы выполнить все запланированные визиты в кладовку при свете.
 
Ввод Вывод
1 2 5 6
3 5		 12
3 1 15 10
1 3
4 5
30 35		 105


Замечание
Замечание В первом примере достаточно заплатить только за электроэнергию: лампочка должна быть включена на третьей минуте и выключена на пятой, стало быть, суммарные затраты составляют (5 − 3) × 6 = 12.
Во втором примере выгодно не выключать лампочку между первым и вторым посетителем, а для третьего использовать уже новую лампочку
Динамическое программированиеДинамическое программирование: один параметрПрефиксные суммы(минимумы, ...)
✓ 13✗ 1651 000средняяВойти и решать
Пожар в НИИЧАВО#21953
В научно-исследовательском институте чародейства и волшебства пожар! Во время опыта Кор- неева В. П. по превращению всей морской и океанской воды планеты в живую воду произошло короткое замыкание, и теперь его кабинет объят пламенем. Задача первостепенной важности — спасти из огня ценные лабораторные приборы, в особенности единственный в своём роде диван- транслятор µ-поля. Ваша задача — перенести диван-транслятор из кабинета Корнеева в запасную лабораторию изучения µ-поля.

НИИЧАВО состоит из N кабинетов, соединённых M коридорами. Кабинеты пронумерованы це- лыми числами от 1 до N, при этом кабинет Корнеева имеет номер A, а лаборатория изучения µ-поля расположена в кабинете номер B. Благодаря специальному искажению пространства внутри инсти- тута, все коридоры имеют одинаковую длину, которую можно пройти за 1 минуту, если двигаться быстрым шагом.

Ситуация усугубляется тем, что диван-транслятор — прибор, очень чувствительный к резким пе- репадам температуры. Внутри каждого коридора НИИЧАВО поддерживается свой температурный режим. Если абсолютная величина разности температур в двух последовательных коридорах на пути из кабинета Корнеева в лабораторию окажется больше D градусов, то диван-транслятор пе- рейдёт в нестабильное состояние, что может привести к катастрофическим последствиям. Обратите внимание, что на своём пути вы не заходите в сами кабинеты, а только переходите из коридора в коридор, поэтому климат внутри кабинетов не влияет на диван-транслятор. В силу причин магиче- ского характера, войдя в коридор, вы обязаны дойти до его конца, иными словами, останавливаться или разворачиваться посреди коридора запрещено. По каждому коридору можно перемещаться в обоих направлениях.

Определите, за какое минимальное время можно добраться из кабинета Корнеева до запасной лаборатории, не допуская резкого перепада температур. В рамках данной задачи вам предлагается ответить на поставленный вопрос для нескольких пар значений A и B.

Формат входных данных
В первой строке входных данных следуют три целых числа N, M и D (2 <= N <= 100 000, 1 <= M <= 200 000, 0 <= D <= 2 · 108 ), обозначающие количество кабинетов, количество коридоров в НИИЧАВО и максимальный допустимый перепад температур для дивана-транслятора в граду- сах. В последующих M строках находятся описания коридоров. Каждая строка содержит по три целых числа ui , vi , ti — номера двух кабинетов, соединённых i-м коридором, и значение температуры в этом коридоре, выраженное в градусах (1 <= ui , vi <= N, −109 <= ti <= 109 ). Как вы уже могли понять, НИИЧАВО — весьма необычное заведение, поэтому между двумя кабинетами может пролегать несколько коридоров, возможно с разными температурами, а некоторые коридоры могут соединять кабинет с самим собой. Гарантируется, что коридоры перечислены во входном файле в порядке неубывания ti . В следующей строке находится целое число Q (1 <= Q <= 50) — количество пар A и B, которые вам требуется обработать. В каждой из последующих Q строк находятся по два целых числа Ai , Bi , обозначающих номер кабинета Корнеева и номер кабинета, в котором расположена лаборатория (1 <= Ai , Bi <= N, Ai != Bi).

Формат выходных данных
Для каждого набора данных выведите в отдельной строке минимальное количество минут, ко- торое требуется потратить, чтобы добраться из кабинета Корнеева до лаборатории, либо выведите −1, если сделать это, используя допустимый для дивана-транслятора маршрут, невозможно.

Примеры
Ввод Вывод
6 9 5
6 6 -42
1 2 4
2 3 6
3 2 7
2 5 11
6 1 12
1 3 15
3 4 16
5 6 18
2
1 5
4 2		 4
-1
6 9 7
6 6 -42
1 2 4
2 3 6
3 2 7
2 5 11
6 1 12
1 3 15
3 4 16
5 6 18
1
4 2		 5

Замечание
Пояснение к тестам из условия. В обоих тестах план НИИЧАВО выглядит следующим образом:

Рассмотрим первый тест, в нём D = 5. В первом наборе A = 1, B = 5. В качестве воз- можного маршрута может выступить следующая последовательность переходов по коридорам:
Третьим шагом можно вернуться в кабинет 2 и по тому же коридору с t = 6 .
Во втором наборе A = 4, B = 2. Способа добраться из кабинета 4 в кабинет 2, ни разу не допустив перепад температуры больше, чем в 5 градусов, не существует.

Во втором тесте D = 7. В единственном наборе A = 4, B = 2 cтартовый и конечный кабинет те же, что и во втором наборе первого теста из условия, но допустимый перепад температур больше, благодаря чему подходит следующий маршрут: 
Алгоритмы на графахОбход в ширинуСтруктуры данных
✓ 12✗ 211 200средняяВойти и решать
Магические порталы#21903
В некотором королевстве есть n городов, соединенных магическими порталами. Каждая пара различных городов соединена ровно одним магическим порталом, позволяющим мгновенно перемещаться из одного города в другой.

Из-за свойств магии, определяющей работу порталов, каждый портал можно использовать только в одну сторону. Для каждой пары городов A и B известно, можно ли воспользоваться порталом для перемещения напрямую из A в B или из B в A.

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

Жители королевства называют город совершенным, если из него можно добраться до любого другого города в королевстве, используя только магические порталы. Пусть изначально количество совершенных городов в королевстве равно k.

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

Для получения этой информации король планирует запросить в министерстве транспорта соответствующий отчет. Король может запросить либо частичный, либо полный отчет. Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1, для полного отчета L = 1.

Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B, для которых выполняются следующие условия:
- исходно магический портал позволяет перемещаться напрямую из города A в город B;
- если изменить направление перемещения этого магического портала на противоположное, чтобы он позволял напрямую перемещаться из города B в город A, то количество совершенных городов в королевстве станет равным m.

Таким образом, частичный отчет содержит информацию только о тех способах перенастройки одного портала, которые строго увеличивают количество совершенных городов в королевстве. Полный отчет содержит информацию обо всех способах перенастройки одного портала.

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n — количество городов в королевстве (2 ≤ n ≤ 2000) и p, равное либо 0, если требуется вывести частичный отчет, либо 1, если требуется вывести полный отчет. Последующие n строк содержат по n символов, каждый из которых может быть «+», «–» или «.», и i-я из этих строк описывает магические порталы, соединяющие i-й город с другими городами.
В i-й строке j-й символ равен «+», если магический портал позволяет напрямую перемещаться из i-го города в j-й, равен «–», если магический портал позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.
Формат выходного файла
Первая строка выходного файла должна содержать одно целое число k — количество совершенных городов в королевстве.
Если требуется частичный отчет (p = 0), то вторая строка выходного файла должна содержать (n – k) целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным (k + i). Если при этом k = n, то вторая строка может отсутствовать, либо быть пустой.
Если требуется полный отчет (p = 1), то вторая строка должна содержать n целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным i.

Пример:
Ввод Вывод
5 0
.-+++
+.+++
--.+-
---.+
--+-.		 1
0 0 0 3
5 1
.-+++
+.+++
--.+-
---.+
--+-.		 1
7 0 0 0 3

Пояснение к примерам

В приведенных примерах изначально совершенным является только город 2.
Изменив направление порталов, соединяющих пары городов (2, 3), (2, 4) или (2, 5), можно сделать все города совершенными. Изменение направление любого другого портала делает совершенным один город.
Алгоритмы на графахЗадача на реализациюЦиклы
✓ 1✗ 101 300средняяВойти и решать
21883#21883
Введите с клавиатуры целое число X (|X| ≤ 109).
В первых трех строках выведите это число на экран в двоичной, восьмеричной, 16-ричной системах счисления.
В следующих двух строках выведите, поместится ли это число в ячейке типа byte и ячейке типа short ("YES"/"NO").
Запрещается использовать циклы и знания о том, сколько именно байт/бит памяти занимают переменные типа int, byte, short.
Пример ввода:
123
 
Пример вывода:
1111011
173
7B
YES
YES
 
Пример ввода:
40000
 
Пример вывода:
1001110001000000
116100
9C40
NO
NO

Разные системы счисленияСтрокиЦелые числа
✓ 102✗ 54400лёгкаяВойти и решать
Число с максимальной суммой делителей#21835
Напишите функцию, вычисляющую сумму делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным суммой делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором сумма делителей числа максимальна среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).
 

Пример

Ввод

Вывод
5
2
5
59
72
34
 72
2
78
81		 78
 
Алгоритмы обработкиЗадачи на процедуры и функцииЛинейные алгоритмы
✓ 82✗ 242700средняяВойти и решать
Число с максимальным количеством делителей#21834
Напишите функцию, вычисляющую количество делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным количеством делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором количество делителей максимально среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод

Вывод
5
22790
94
66
18
18
 22790
2
21
46 
 21
 
Алгоритмы обработкиЗадачи на процедуры и функцииПростые числа и разложение на множители
✓ 112✗ 236700средняяВойти и решать
Крестики-нолики#21821
Пете и Васе стало очень скучно на уроке биологии, и они решили поиграть в любимую всеми школьниками игру в крестики-нолики до пяти в ряд на бесконечном поле.
Рассмотрим кратко правила игры. Игра происходит на бесконечном клетчатом поле, два игрока делают ходы по очереди, первый игрок ходит крестиками, а второй — ноликами. В свой ход игрок
выбирает свободную клетку поля и ставит туда свой символ. Если после хода очередного игрока на поле есть пять его символов подряд по вертикали, горизонтали или диагонали, то сделавший такой ход игрок объявляется победителем и игра заканчивается.
Петя и Вася уже довольно долго играют в игру. Сейчас должен ходить Петя, который играет крестиками. Петя надеется побыстрее завершить игру и хочет выиграть не более чем за два, а лучше
за один ход. Петя называет ход оптимальным, если для этого хода выполнено одно из двух:
• этот ход приводит к немедленной победе Пети;
• не существует хода, который приводит к немедленной победе Пети, но если Петя сделает этот ход, то Вася не выиграет следующим ходом и, вне зависимости от ответного хода Васи, у Пети
будет следующий ход, который приведет к его немедленной победе.
Помогите Пете найти количество оптимальных ходов.
Формат входных данных
В первой входного файла находятся два натуральных числа n, m (1 ≤ n,m ≤ 200) — размеры прямоугольника, содержащего все уже поставленные на поле крестики и нолики.
Следующие n строк содержат по m символов, каждый из которых равен одному из следующих:
«.» (точка), «X» (заглавная латинская буква «икс») или «0» (ноль). При этом «.» обозначает пустую клетку, «X» обозначает крестик, а «0» обозначает нолик. Гарантируется, что на поле находится
равное число крестиков и ноликов, и ни один игрок еще не одержал победу.
Формат выходных данных
Выведите одно число — количество оптимальных ходов Пети.
 
Примеры
№ Входные данные Выходные данные
1
5 3
...
000
XXX
...
...
 2
2
4 4
..0.
.XX0
.0X.
....
 0
3
5 6
......
.XXX..
.0000.
..X...
......
 0
 
Двумерные массивыЗадача на реализациюПростые игры
✓ 1✗ 21 300средняяВойти и решать
MTN DEW#21780
Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:

f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.

Также, известно, что

f(1) = 1 microCoinZ 
f(x) = 0 microCoinZ, при x < 1.

Помогите Bonkisilver сосчитать полученное количество microCoinZ.
 
Входные данные
На вход подается число n (0 <= n <= 70).
 
Выходные данные
Выведите одно число - полученный скилл. 
 
Примеры
№ Входные данные Выходные данные
1 1 1

PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo. 
Динамическое программированиеДинамическое программирование: один параметрРекуррентные последовательности
✓ 296✗ 741500лёгкаяВойти и решать
Веселый программист#18714
Записана последовательность чисел в странном формате:
у каждого числа сначала записано количество цифр в этом числе, а потом через пробел - сами цифры. Последовательность заканчивается числом 0. 
 
В выходной файл нужно вывести сначала количество чисел в последовательности, а потом - сами числа в столбик.
 
Количество чисел в последовательности не превышает 1000. В числах - не более 4-х знаков.
 
Одномерные массивыСтрокиЦикл while
✓ 93✗ 409700средняяВойти и решать
Поделиться
Класснуть