База знаний гимназии 1 им. Барсукова

Это старая версия документа.

---

1. Икебана

Ограничения: время – 2s/Java 2s, память – 256MiB

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

После долгих прений жюри утвердило регламент проведения соревнований. Соревнования длятся m дней. Всем участникам выдаются одинаковые грядки с n ростками бамбука. В момент начала соревнований — 5:00 первого дня — высота i-го ростка на грядке каждого участника равна a_i. Каждую полночь i-й росток вырастает на b_i. Утром каждого дня, начиная с первого, ровно в 6:00, каждый участник может один раз постричь бамбук на своей грядке. Происходит это так: участник выбирает i и j (1 ≤ i ≤ j ≤ n) — левую и правую границу отрезка ростков, которые он хочет постричь, затем выбирает высоту l (0 ≤ l ≤ 2·10⁹), и все ростки, с i-го по j-й включительно, высота которых больше l, обрезаются до высоты l. Сравнение работ происходит в полдень m-го дня. Победителями соревнований считаются те участники, которые, сделав минимальное количество стрижек, смогли получить грядку, все n ростков на которой имеют высоту h. Теперь жюри интересно, какое минимальное число раз победителю придется стричь бамбук.

Формат ввода. В первой строке входного файла находится три целых числа: n (1 ≤ n ≤ 10⁵) — количество ростков бамбука на грядке, m (1 ≤ m ≤ 10⁹) — длительность соревнований, и h (0 ≤ h ≤ 10⁹) — высота всех ростков, необходимая для победы.

В следующих n строках находится по два целых числа a_i и b_i (0 ≤ a_i, b_i ≤ 10⁹) — описание i-го ростка: его высота в момент начала соревнований и на сколько он вырастает за ночь, сооветственно.

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

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

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

2. Номер страницы

Ограничения: время – 2s/Java 2s, память – 256MiB

Однажды робот-библиотекарь решил устроить ревизию. На одной из полок, среди экземпляров тридцать третьего издания Кормена, он нашел листок из условий одного древнего контеста. Роботу известен формат оформления условий, однако этот листок привел его в замешательство.

Обычно внизу каждой страницы условий есть надпись вида «Страница i из n», где i — номер страницы условий, а n — количество страниц в условиях. Однако на этом листе была всего одна длинная последовательность цифр. Видимо, принтер почему-то не напечатал ни одного символа кроме цифр. Таким образом, номера i и n слились в единую последовательность цифр.

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

Выясните, сколько есть корректных надписей вида «Страница i из n», при удалении из которых всех символов кроме цифр получается заданная во входном файле строка.

Формат ввода. Входной файл содержит строку, состоящую только из цифр. Длина строки лежит в пределах от 1 до 200 000, включительно.

Формат вывода. Выведите количество корректных надписей вида «Страница i из n», при удалении из которых всех символов кроме цифр получается заданная во входном файле строка.

В приведенном примере можно проинтерпретировать строку тремя способами:

«Страница 2 из 3507645»

«Страница 23 из 507645»

«Страница 2350 из 7645»

3. Летопись

Ограничения: время – 2s/Java 2s, память – 256MiB

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

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

После анализа дисков было установлено, что они использовались в XXI веке по летоисчислению, использовавшемуся древней цивилизацией — так называемому «григорианскому» календарю — год продолжительностью 365 дней, разделялся по нему на двенадцать месяцев. Второй месяц в году имел продолжительность двадцать восемь дней, первый, третий, пятый, седьмой, восьмой, десятый и двенадцатый — тридцать один день, остальные — тридцать дней. В особые года, номер которых делился на четыре и не делился на сто, либо делился на четыреста, второй месяц длился двадцать девять дней. Веком номер i назывался период с 100·(i−1) + 1 года по 100·i. Так как достоверно не известно, в каком порядке представители древней цивилизации записывали даты, вам, как главному специалисту по григорианскому календарю, поручили провести исследование — установить, каким датам в XXI веке могла соответствовать надпись, в предположении, что одно из чисел соответствует дню в месяце (дни в каждом месяце нумеровались с единицы), еще одно из чисел — номеру месяца (месяцы также нумеровались с единицы), и еще одно число — последним двум цифрам года в XXI веке григорианского календаря. По заданной надписи на диске выясните, каким датам в XXI веке она могла соответствовать.

Формат ввода. Во входном файле в формате aa/bb/cc записаны числа с диска.

Формат вывода В выходной файл в произвольном порядке выведите все корректные даты dd/mm/yy в XXI веке, где dd соответствует номеру дня, mm – номеру месяца, yy — номеру года, причем числа, соответствующие dd, mm и yy являются перестановками чисел с диска. В случае, если никакая перестановка исходных чисел не является корректной датой XXI века, выведите «No such date».

4. Гномья нумерация

Ограничения: время – 2s/Java 4s, память – 32MiB

Хотя в основе системы нумерации у гномов лежит число 10, гномы для представления больших чисел используют не десятки, сотни, тысячи, а представляют числа в виде суммы слагаемых, состоящих из одинаковых цифр. Гномы используют 54 слагаемых, а именно 1, 2, …, 9, 11, 22, …, 99, 111, …, 999, 1111, …, 9999, 11111, …, 99999, 111111, …, 999999. Для каждого слагаемого в языке гномов существует особое название и обозначение в виде одной из букв алфавита. Числа в этой системе нумерации можно записать несколькими способами, и гном Док решил найти наиболее компактное представление для записи всех чисел от 1 до 1000000.

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

Ввод содержит целое число N (1 ≤ N ≤ 10⁶).

Вывести число N, затем символ '=', затем представление числа N в виде суммы гномьих слагаемых. Количество слагаемых в сумме должно быть минимально. Слагаемые могут повторяться, порядок слагаемых в сумме не важен.