Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. Нато, чтобы довезти кружки от завода-изготовителя до ЛКШ,остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

Выведите одно число - максимальное количество кружек, которое можно привезти за первый рейс, потратив не более 24часов.

Алгоритм Дейкстры Бинарный поиск по ответу

✓ 112✗ 362900средняяВойти и решать

Little Difference#27120

Little Lidia likes playing with numbers. Today she has a positive integer n, and she wants to decompose it to the product of positive integers.

Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to n. She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.
Write a program that finds all decompositions, which little Lidia can play with today.

Input
The only line of the input contains a single integer n (1 ≤ n ≤ 10¹⁸).

Output
In first line output the number of decompositions of n, or −1 if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number ki of elements in decomposition. Then print ki integers in this decomposition in any order. Don’t forget that decompositions which are different only in order of elements are considered the same.

Input	Output
12	3 1 12 3 2 3 2 2 4 3
1	-1

In the second example 1 can be represented as product of any number of ones.

Динамическое программирование: последовательности Конструктив

1 300средняяВойти и решать

Все возрастающие последовательности длины k из чисел 1..n#27093

По данным числам N и K выведите все возрастающие последовательности длины K из чисел 1..N в лексикографическом порядке.

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

Заданы 2 числа: N и K (1 ≤ K,N ≤ 100). Для всех тестов верно, что число требуемых последовательностей не превышает 5000.

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

Необходимо вывести все возрастающие последовательности длины K из чисел 1..N в лексикографическом порядке. Последовательности выводятся по одной в строке, числа внутри последовательностей разделяются пробелами.

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

Рекурсивный перебор Сочетания

✓ 1✗ 18900средняяВойти и решать

Построить из строки следующую анаграмму#27091

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

Входные данные
В первой строке задается число N - количество слов. Далее идет последовательность из N слов, по одному слову в строке. Длина одного слова не превышает 50 символов.

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

Примеры

№	Входные данные	Выходные данные
1	4 aab aba baa aaa	aba baa aab aaa

Комбинаторика Перестановки

✓ 79✗ 189900средняяВойти и решать

Двоичные строки заданной длины в обратном порядке#27090

По данному числу N выведите все строки длины N из нулей и единиц в обратном лексикографическом порядке.

Входные данные
Задано единственное число N (\(1 <= N <= 10\)).

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

Примеры

№	Входные данные	Выходные данные
1	2	11 10 01 00

Простые задачи на перебор Размещения с повторениями

✓ 149✗ 83600лёгкаяВойти и решать

Опасные отходы#27085

При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.

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

Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).

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

Программа должна вывести одно число – количество способов составить безопасную стопку из N контейнеров.

Примеры

№	Входные данные	Выходные данные
1	3	7

Динамическое программирование: один параметр Рекуррентные последовательности

✓ 88✗ 156700средняяВойти и решать

Зоомагазин-2#27084

В зоомагазине нужно расставить в один ряд клетки с кошками и собаками. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить подряд три клетки с животными одного вида (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с кошками и собаками. Определите, сколькими безопасными способами можно расставить N клеток в ряд.

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

Входная строка содержит одно натуральное число – количество клеток в ряду N .

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

Программа должна вывести количество безопасных способов расстановки N клеток в ряд.

Ввод	Вывод
5	16

Динамическое программирование Динамическое программирование: два параметра

✓ 49✗ 23700средняяВойти и решать

Кузнечик и лягушки#27082

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

На некоторых столбиках сидят лягушки, которые едят кузнечиков (Кузнечик не должен попадать на эти столбики!). Определите, сколькими способами Кузнечик может безопасно добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 <= N, K <= 32 . Во второй строке записано число лягушек L ( 0 <= L <= N - 2 ). В третьей строка записано L натуральных чисел: номера столбиков, на которых сидят лягушки (среди них нет столбиков с номерами 1 и N ).

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

Программа должна вывести одно число: количество способов, которыми Кузнечик может безопасно добраться до столбика с номером N .

Примеры

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

Динамическое программирование Динамическое программирование: один параметр

✓ 36✗ 95900средняяВойти и решать

Площадь треугольника#27074

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

Шесть чисел – координаты трёх вершин треугольника.

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

Одно число – величина площади треугольника.

Примеры

№	Входные данные	Выходные данные
1	1 1 2 4 3 2	2.50000

Вычислительная геометрия Элементарная геометрия

✓ 660✗ 1 268300лёгкаяВойти и решать

Тяжелая, вариант-1#27064

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

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

С учетом этих требований найдите наибольшую длину автомобиля, который можно поставить на стоянку.

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

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

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

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

Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.

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

Ввод	Вывод
4 21 1 1 7 12 3 16	2
4 30 3 1 24 5 11 18	3
2 20 3 1 7 10	5

Задачи на моделирование Использование сортировки реализация

✓ 8✗ 21800средняяВойти и решать

Упорядочите шарики#27053

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

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

При засасывании шарика все шарики, которые находились правее засасываемого, сдвигаются влево. «Выплюнуть» шарик можно между любыми двумя шариками (а также перед первым шариком или после последнего), тогда выплевываемый шарик вставляется между этими шариками, и все шарики, которые находятся правее вставляемого, сдвигаются вправо.

В устройство может быть одновременно засосано больше одного шарика, при этом при выплевывании шарика первым выплевывается последний засосанный шарик, затем - предпоследний и т.д. (т.е. устройство работает по принципу стека). Шарики выплевываются по одному, т.е. можно выплюнуть только один шарик, остальные оставив внутри устройства (при этом дальше можно как продолжать «выплевывать» шарики в том же или в другом месте, так и засасывать новые шарики).

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

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

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

Во входном файле задано сначала число N — количество шариков (1<= N <= 1000). Далее идет N чисел, задающих номера шариков в порядке слева направо в их текущем расположении (каждое число — от 1 до N, и каждое из чисел встречается в последовательности ровно один раз).

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

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

Комментарии к примерам тестов

1.Можно засосать, например, шарик номер 2 и выплюнуть его между 1-м и 3-м шариком.

2. Можно действовать, например, так. Сначала засосем шарик номер 1, затем – шарик номер 2. Затем переместимся в начало и перед 4-м шариком выплюнем шарик (это будет шарик номер 2). Дальше засосем шарик номер 3, и выплюнем его между шариками 2 и 4. Дальше переместимся в начало и там выплюнем шарик номер 1. Впрочем, это не единственный возможный вариант упорядочения шариков в этом примере.

Примеры

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

Динамическое программирование Динамическое программирование: последовательности

✓ 70✗ 24500лёгкаяВойти и решать

S.L.O.T.#27023

Вчера знаменитый певец S.L.O.T. исполнил на концерте свой лучший трек "10 марта" и множество других. Дамир ОЧЕНЬ захотел на этот концерт и уже купил билеты, как вдруг понял, что до концерта всего час, а ему нужно доехать до места проведения концерта (естественно, на трамвае).

Трамвай необходимое расстояние преодолевает за 59 минут. Будем считать, что концерт проводится на трамвайной остановке, то есть Дамир вполне на него успевает, но ему подходит только ему подходят лишь трамваи, номера которых являются перестановками от 1 до n. При этом он только что увидел, как с его остановки уезжает трамвай с номером p. Однако Дамир - великий эстет, и он хочет сесть на трамвай, номер которого равен следующей перестановке после p. Поскольку трамваи подходят к его остановке мнгновенно, на концерт любимого исполнителя он успеет в любом случае.

Вам дана последовательность из номеров трамваев, которые в ближайшем времени подойдут к остановке Дамира и Ваша задача состоит в том, чтобы сообщить порядковый номер трамвая, который подойдёт Дамиру(все номера нумеруются с единицы. то есть если на вход вам даётся 6 номеров, то их порядковые номера идут в таком порядке: 1, 2, 3, 4, 5, 6)

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

В первой строке вводится число n - количество чисел в перестановке в номере трамвая

Во второй строке ЧЕРЕЗ ПРОБЕЛ!! вводится n чисел, которые задают p - номер трамвая, который только что отошёл от остановки Дамира

Третья строка содержит k - количество трамваев, которые скоро подъедут к остановке Дамира (гарантируется, что один из трамваев подходит Дамиру)

Далее идут k строк, которые содержат по n чисел через пробел - номера трамваев

(n <= 7, k <= 5)

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

выведите порядковый номер трамвая, который подходит Дамиру (если таких несколько, выведите наименьший из них, то есть порядковый номер того искомого трамвая, который подъедет к остановке Дамира раньше).

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

Комбинаторика Перестановки

✓ 7✗ 17900средняяВойти и решать

Сложные пароли#27022

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

Ввод:
в первой строке вводится n - количество слов и наборов цифр, в следующих n строках вводятся слова / наборы цифр. (n<20, длина строк не превышает 20).

Вывод:
Необходимо вывести все возможные перестановки слов и наборов цифр, если это невозможно, вывести "unreal".

Ввод	Вывод
3 cat 123 215	123cat215 215cat123

(с) Вероника Пеутина

Комбинаторика Простые задачи на перебор реализация

✓ 17✗ 105800средняяВойти и решать

"Гробы" из 43-го#27021

На уроке информатике Антон Витальевич задал придумать задачи на перестановки. Ребята в 43 кабинете очень обрадовались этому заданию и решили придумать n гробов для своего класса. Сложность каждой задачи – это число от 1 до n. Ребята хотят узнать насколько, они «загробили» контест, коэффициент «загробленности» (КЗ) считается, как номер перестановки, которую подали на ввод. Ребята радуются, если КЗ будет больше, чем сумма разниц между двумя подряд идущими элементами в данной перестановки по модулю умноженная на количество гробов в контесте.

Вывести “positumque loculum” (гроб), если ребята будут рады своей работе, иначе вывести наименьшую подходящую перестановку (элементы разделять пробелами), номер которой |КЗ – номер текущей| <= k, а если это невозможно, то вывести “easily”.

В первой строке вводится количество гробов в контесте n <= 7 и k, 0 <= k <= n!

Во второй строке вводится сама перестановка.

Ввод	Вывод
7 2518 7 5 2 4 1 6 3	positumque loculum
4 1 3 2 4 1	easily
4 2 3 2 4 1	3 4 2 1

Приятного решения ♥♥
(с) Елизавета Ястреба

Генерация по номеру Комбинаторика

✓ 1✗ 131 200средняяВойти и решать

Номер перестановки#27020

Вам даны две строки - S и одна из её перестановок - P. Требуется найти номер строки P среди всех перестановок строки S, отсортированных по убыванию в лексикографическом порядке.

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

На вход подаются две строки - S и P (1 =< |S| <= 9). В строках содержатся только строчные буквы латинского алфавита.

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

Выведите одно число - номер перестановки P.

Ввод	Вывод
abcd dcba	1
abc abc	6

(с) Ахмад Ибрахим

Комбинаторика Перестановки

✓ 30✗ 47500лёгкаяВойти и решать

Алгоритм#27018

Реализуйте алгоритм, представленный блок-схемой, на одном из языков программирования.

В первой строке ввода содержится одно целое число N (2 ≤ N ≤ 10⁹).

Каждое число, которое выводится в алгоритме, вывести на отдельной строке.

Ввод	Вывод
12	2 2 3

Задачи на моделирование Простые числа и разложение на множители

✓ 66✗ 75500лёгкаяВойти и решать

Курьер#26986

Курьеру Васе поручили доставить n посылок. Вася начинает работать в первый день и каждый день может доставить ровно одну посылку. Про каждую посылку известен последний день, когда ее можно доставить d_i, и штраф w_i, который придется заплатить, если посылка не будет доставлена в срок.

Помогите Васе решить, в каком порядке доставлять посылки, чтобы суммарный штраф был как можно меньше.

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

Формат ввода

В первой строке дано единственное натуральное число n (1 n 200 000) — количество посылок.

Затем следует n строк, в каждой из которых содержится по два числа d_i и w_i (1 d_i 200 000, 1 w_i 200 000) — последний день, когда можно доставить посылку без штрафа и стоимость опоздания для i-й посылки.

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

В первой строке выведите единственное число, равное минимально возможному суммарному штрафу. Во второй строке через пробел выведите n чисел, где i-е число — день, в который необходимо доставить i-ю посылку.

Если возможно несколько оптимальных расписаний, выведите любое из них.

Пример

Ввод	Вывод
3 1 2 1 3 3 1	2 3 1 2

Жадный алгоритм Использование сортировки

✓ 2✗ 101 300средняяВойти и решать

Максимальное число делителей#26984

Напишите программу, которая по заданному числу n находит такое число от 1 до n, включительно, что оно имеет максимальное число положительных целых делителей. Например, если n = 15, то ответом на задачу будет число — 12, так как у него 6 делителей: 1, 2, 3, 4, 6 и 12.

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

Дано одно натуральное число n (1 ≤ n ≤ 100 000).

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

В первой строке выведите число из диапазона от 1 до n, включительно, которое имеет максимальное число делителей. Во второй строке выведите число его делителей. Если в диапазоне от 1 до n существует несколько чисел с максимальным числом делителей, то выведите любое из них.

Простые задачи на перебор Простые числа и разложение на множители

✓ 9✗ 133900средняяВойти и решать

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

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

Выведите единственное натуральное число — количество различных путей наименьшей длины.

Пример

Ввод	Вывод
3	6

Динамическое программирование: один параметр Комбинаторика

✓ 22✗ 148900средняяВойти и решать

Числа Фибоначчи#25962

Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \text{ при}\ n \ge 2\)

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

В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).

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

Вывести одно n-е число Фибоначчи - F_n.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	7	21

Динамическое программирование Рекуррентные последовательности

✓ 104✗ 217400лёгкаяВойти и решать