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

Лес#42971

Миша заблудился в лесу и пытается выйти из него. Он проходит A шагов на север, затем B шагов на восток, затем C шагов на юг, D шагов на запад, после чего повторяет свои действия (снова A шагов на север, B шагов на восток, C шагов на юг, D шагов на запад и т.д.).
Оказалось, что для того, чтобы выйти из леса из его первоначальной точки, ему нужно было пройти ровно K шагов в любом из четырёх направлений, то есть первоначально Миша находится в центре квадрата со стороной 2K шагов. Определите, сколько шагов Миша сделает, прежде чем выйдет из леса (впервые окажется на границе леса).

Входные данные
Первые четыре строки входных данных содержат по одному целому положительному числу A, B, C, D — количество шагов, которое Миша делает на север, восток, юг, запад. Пятая строка входных данных содержит целое число K — расстояние от начального расположения Миши до четырёх сторон квадрата (границ леса). Все входные числа не превосходят 10⁹.

Выходные данные
Программа должна вывести одно целое число — количество шагов, которое Миша сделает до выхода из леса. Гарантируется, что входные данные таковы, что Миша когда-нибудь выйдет из леса.
Обратите внимание, что значение ответа может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Примеры

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

Замечание
На рисунке изображён пример из условия. Миша делает 1 шаг на север (вверх), 1 шаг на восток (вправо), 2 шага на юг (вниз), 3 шага на запад (влево). От начального расположения Миши до стороны квадрата — 3 шага. Первоначальное расположение Миши и точка выхода из леса обозначены синими кругами. Путь Миши обозначен жёлтой линией. Миша пройдёт 13 шагов, прежде чем впервые окажется на границе леса.

Задачи на моделирование реализация

✓ 15✗ 1821 100средняяВойти и решать

Гость из прошлого#39059

Коля Герасимов очень любит кефир, и в своём 1984 году он освоил все тонкости покупки этого чудесного напитка. Но однажды, как вам, наверное, известно, он попал в далёкий 2084 год, где покупка кефира представляет собой более сложный процесс.

Будущее будущим, а кушать хочется всегда, поэтому Коля отправился в местную молочную лавку. В 2084 году кефир продают в литровых пластиковых бутылках по a копеек за штуку и в литровых бутылках из стекла по b копеек за штуку. При этом пустую стеклянную бутылку можно сдать и получить назад c (c < b) копеек, а пластиковую бутылку сдать нельзя.

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

Входные данные
В первой строке входных данных задаётся число n (1 <= n <= 10¹⁸)— количество копеек у Коли в кармане.
В строках со второй по четвертую по одному записаны числа a, b и c (1 <= a <= 10¹⁸, 1 <= c < b <= 10¹⁸) - стоимость пластиковой бутылки с кефиром, стоимость стеклянной бутылки с кефиром и сколько копеек можно получить, сдав пустую стеклянную бутылку, соответственно.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	10 11 9 8	2
2	10 5 6 1	2

Жадный алгоритм Задачи на моделирование

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

Наша Таня громко плачет#39057

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

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

Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

Для решения Таниной проблемы Миша решил по очереди использовать эти команды таким образом, чтобы в конце в папке остался ровно один документ.

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

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

В первой строке содержится целое число n ( 1 <= n <= 2*10⁹) - количество копий документа в папке у Тани.
Во второй строке содержится целое число k ( 1 <= k <= 2*10⁹) - количество раз, в которое уменьшает количество файлов вторая команда.
В третьей строке содержится целое число A ( 1 <= A <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение первой команды.
В четвёртой строке содержится целое число B ( 1 <= B <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение второй команды.

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

Выведите единственное число - минимальное количество секунд, которое придётся потратить Мише на решение проблемы.

Примечание

В первом тестовом примере оптимальная стратегия Миши такова:

За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

На выполнение этих четырёх операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.

Примеры

№	Входные данные	Выходные данные
1	9 2 3 1	6
2	5 5 2 20	8
3	19 3 4 2	12

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

✓ 6✗ 371 000средняяВойти и решать

Спираль#38875

Робот перемещается по клетчатой плоскости и рисует спираль. Исходно он находится в клетке (0, 0) и направлен в сторону увеличения первой координаты.
Далее он действует по следующему алгоритму: совершает d перемещений вперед, затем поворачивает налево и снова делает d перемещений вперед. После этого он поворачивает налево и умножает значение d на k. Затем робот повторяет описанный процесс. Робот останавливается, сделав суммарно ровно n перемещений.
Требуется вывести картинку, на которой отмечены клетки, на которых побывал робот.

Входные данные
На вход подаются целые числа n, d и k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).

Выходные данные
Пусть минимальный прямоугольник из клеток, содержащий все посещенные роботом клетки, имеет высоту h и ширину w. На первой строке выведите числа h и w, разделенные пробелом. Следующие h строк должны содержать по w символов, выведите «*» для клетки, посещенной роботом и «.» для не посещенной.

Примеры

№	Входные данные	Выходные данные
1	13 2 2	5 5 ***** ... .** .... *...

Двумерные массивы Задачи на моделирование

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

Мегазорды#38866

Мегазорд — необходимая вещь для защиты Земли. Для сборки одного мегазорда, необходимо ровно три зорда: зеленый, красный и синий.
Зеленому, красному и синему рейнджеру стало интересно, сколько у них есть различных способов собрать мегазорд. Для каждого рейнджера известен набор зордов, которыми он обладает. У зеленого рейнджера есть зеленые зорды, у красного рейнджера — красные, а у синего — синие.
При сборке мегазорда необходимо соблюдать три правила:

Первая цифра номера модели красного зорда должна быть равна последней цифре модели зеленого.
Последняя цифра номера модели красного зорда должна быть равна первой цифре модели синего.
Все три использованных зорда должны иметь разные номера моделей.

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

Входные данные
В первой строке входного файла заданы числа g, r и b — количество зордов у зеленого, красного и синего рейнджера соответственно (1 ≤ g, r, b ≤ 10⁵).
В следующей строке находится g чисел x_i — номера моделей, которые есть у зеленого рейнджера (0 ≤ x_i ≤ 10⁹).
В следующей строке находится r чисел y_i — номера моделей, которые есть у красного рейнджера (0 ≤ y_i ≤ 10⁹).
В следующей строке находится b чисел z_i — номера моделей, которые есть у синего рейнджера (0 ≤ z_i ≤ 10⁹).

Выходные данные
Выведите одно число — количество различных мегазордов, которые можно собрать.

Примеры

№	Входные данные	Выходные данные
1	3 3 2 101 11 52 11 23 23 31 13	3

Замечание
Различные мегазорды из первого примера: 101 + 11 + 13, 52 + 23 + 31, 52 + 23 + 31. Последний мегазорд встречается дважды, так как красный ренжер мог взять либо второй, либо третий зорд. Обратите внимание, что собрать мегазорд 11+11+13 нельзя, так как при этом одна и та же модель будет использована дважны.

Вывод формулы Задачи на моделирование

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

Рейнджеры в автобусе#38865

Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!
Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.
Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, Синий садится справа.
Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
Жёлтый рейнджер тоже, любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.

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

Входные данные
В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2 · 10⁵, 2n)).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i-й из этих строк заданы числа x_i и y_i — место, на которое сел i-й пассажир (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), x_i — это номер ряда, y_i = 1, если это место слева от прохода, и y_i = 2, если справа.
Все места, на которые сели пассажиры, различны.

Выходные данные
В первой строке выведите число s₁ — количество пассажиров, которые могли бы быть красным рейнджером, а затем, через пробел, s₁ чисел — номера этих пассажиров в порядке возрастания (пассажиры нумеруются с 1 по k в том порядке, в котором они заданы во входных данных).
В следующих четырёх строках выведите в том же формате информацию об остальных рейнджерах: синем, чёрном, жёлтом и розовом соответственно.

Примеры

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

Замечание

На этой картинке показаны места, на которые садились пассажиры в примере.

Задачи на моделирование Линейные алгоритмы

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

Переключение между окнами#38849

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

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

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

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

Входные данные
В первой строке вводится целое число n – количество действий пользователя ( 1 ≤ n ≤ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

Выходные данные
Выведите n строк – последовательность имен приложений, с которыми работал пользователь в порядке, в котором их окна становились активными.

Примеры

№	Входные данные	Выходные данные
1	6 Run Mozilla Firefox Run Free Pascal Alt+Tab Run Miranda IM Alt+Tab+Tab Alt+Tab+Tab+Tab	Mozilla Firefox Free Pascal Mozilla Firefox Miranda IM Free Pascal Free Pascal

Задачи на моделирование Список

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

Экспресс тест#38798

В данной задаче вам предлагается автоматизировать оценку результата экспресс теста.
Вам дана двухцветная картинка размером 10×20. Для обозначения цветов используются символы «#» и «.». Тест
считается отрицательным, если на картинке изображена одна вертикальная полоска и положительным, если три. В любом
другом случае тест считается испорченным.
Полоской будем считать область картинки 10×k, состоящую из символов «#», где k может быть произвольным. При этом
все соседние клетки с этой областью должны быть «.». Полоска может находиться на границе картинки.

Входные данные
В первой строке входных данных задано число t - число тестов (1 ≤ t ≤ 30). В следующих t⋅10+(t−1) строках заданы картинки
тестов. Соседние картинки разделены пустыми строками. После последней картинки, пустой строки нет.
Каждая картинка состоит из 10 строк по 20 символов, каждый из которых либо «#», либо «.».

Выходные данные
Для каждой картинки выведите результат теста в отдельной строке:
Negative - если тест отрицательный;
Positive - если тест положительный;
Incorrect - если тест испорчен.

Примеры

№	Входные данные	Выходные данные
1	4 .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........#.......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..#.......#.....###.	Negative Incorrect Positive Incorrect

№

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

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

4
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

.........##.........
.........##.........
.........##.........
.........#..........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.

..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..#.......#.....###.

Negative
Incorrect
Positive
Incorrect

Алгоритмы обработки Задача на реализацию Задачи на моделирование

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

Путешествие по джунглям#38753

Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан.
Всего в джунглях есть N лиан, расположенных друг за другом и пронумерованных слева направо целыми числами от 1 до N. Расстояние между соседними лианами составляет D метров. Находясь на i-й лиане, Коко может совершить прыжок с нее не более, чем на ai метров вправо. В процессе прыжка Коко должна зацепиться за какую-то другую лиану, мимо которой будет пролетать.
В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо.
Помогите Коко и определите максимальный номер лианы, до которой она сможет добраться.

Входные данные
Первая стока входных данных содержит целое число N (2 ≤ N ≤ 10⁵) — количество лиан.
Во второй строке записано целое число D (1 ≤ D ≤ 10⁹) — расстояние между соседними лианами.
В каждой из следующих N строк записано целое число ai (1 ≤ a_i ≤ 10⁹) — на сколько метров вправо может прыгнуть Коко, находясь на i-й лиане.

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

Примеры

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

Замечание
В примере из условия дано 5 лиан, а расстояние между лианами равно 3 метрам. Находясь на первой лиане, Коко может прыгнуть не более, чем на 7 метров, то есть она сможет допрыгнуть до второй и третьей лианы. Ей нужно остановиться на второй лиане, потому что со второй лианы длина прыжка равна 8 метрам, и это позволит ей допрыгнуть до четвёртой лианы. С четвёртой лианы длина прыжка равна 2 и это меньше, чем расстояние до следующей лианы, поэтому Коко остановится на четвёртой лиане.

Задачи на моделирование Линейные алгоритмы

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

Цифры в умножении#38581

Дано целое число N (\(1<=N<=10^{10}\)).
Для двух положительных целых чисел A и B определим \(F (A, B)\) как большее из двух:
- количество цифр в десятичной записи числа A;
- количество цифр в десятичной записи числа B.
Например, \(F (3,11) = 2\), поскольку 3 состоит из одной цифры, а 11 - из двух.
Найдите минимальное значение \(F (A, B)\) среди всех пар положительных целых чисел A и B, таких что \(N = A \cdot B\).

Входные данные
На вход подается целое число N (\(1<=N<=10^{10}\)).

Выходные данные
Выведите на экран ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10000	3	\(F(A,B) \) имеет минимальное значение при \((A,B)=(100,100)\).
2	1000003	7	Есть две пары `A` и `B`, таких чтобы выполнялость условие задачи: \((1,1000003)\) и \((1000003,1)\). Для этих пар, `\(F(1,1000003)=F(1000003,1)=7\)`.
3	9876543210	6

Задача на реализацию Задачи на моделирование

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

"Сортировка" с конфеткой#38576

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

Выходные данные
Требуется вывести массив после сортировки.

Примеры

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

Задачи на моделирование Сортировка "пузырьком"

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

Туристический налог#38492

Для пополнения бюджета в стране Авалон, известной своими горными туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению, совершённому туристической группой. Кроме того, в силу старинного обычая все
туристические группы должны перемещаться по горам Авалона строго с запада на восток. Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным, он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута.
Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния.
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска.
Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 10⁵.
Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего
условиям, не существует, программа должна вывести одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 18 10 15 20 20 10 3	3 6	Дано 7 точек с высотами 18, 10, 15, 20, 20, 10, 3. Самый короткий маршрут, содержащий подъём и спуск, – это 15, 20, 20, 10. Он начинается в точке номер 3 и заканчивается в точке номер 6.
2	3 9 8 5	0	Высота гор монотонно убывает, поэтому искомого маршрута не существует.

Задачи на моделирование Линейные алгоритмы

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

Коллайдер#38476

Физики проводят эксперимент для исследования частиц трёх типов: x, y и z. Они запускают в коллайдер пронумерованный ряд из n частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с i-ого места ряда и моментально появляется на месте j. После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте k. Напишите программу, которая поможет физикам.

Входные данные
В первой строке файла два целых числа: n – количество частиц и m — общее количество воздействий и вопросов (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). Во второй строке — последовательность из символов x, y и z длиной n. На каждой из следующих m строк (1 ≤ m ≤ 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом a и после пробела дается два целых числа из интервала [1; n]. Первое из них показывает начальное, а второе - конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом q и после пробела дается одно целое число из интервала [1; n]. Оно указывает позицию, которая интересует физиков.

Выходные данные
Выведите столько строк, сколько вопросов во входном файле. В строке номер i надо записать ответ на вопрос i — название соответствующей частицы x, y или z.

Пояснения к примеру
Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,

Примеры

№	Входные данные	Выходные данные
1	15 6 xzxyyzxxzxyyzyx a 2 10 a 15 4 q 3 a 12 2 q 14 q 2	y z y

Двоичное дерево поиска Задачи на моделирование

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

Таблица#38465

Бесконечную таблицу, строки и столбцы которой пронумерованы целыми числами начиная с 1 сверху вниз и слева направо, заполняют целыми числами 1, 2, 3 и т.д. Числа выписываются в
соседние клетки по границам квадратов увеличивающегося размера (см. рисунок).

Формат входных данных
Программа получает на вход одно целое число n, 1 ≤ n ≤ 10¹⁸
Формат выходных данных
Программа должна вывести два целых числа: номер строки и номер столбца, в которых находится число n в этой таблице. Запись выводимых чисел должна содержать только цифры, вывод
действительных чисел в ответе считается неверным.

Примеры

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

Вывод формулы Задачи на моделирование

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

Таблица#38370

В новой математической игре для одного игрока «Таблица чисел» используется таблица размером n строк на m столбцов, заполненная целыми числами. За один ход игрок выбирает одну из строк или один из столбцов и меняет знак на противоположный у всех чисел этой строки или столбца.

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

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

Входные данные
Первая строка входного файла содержит два целых числа: n и m (2 ≤ n, m ≤ 100). Каждая из последующих n строк содержит по m целых чисел a_i,j (|a_i,j| ≤ 100).

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

Описание каждого хода должно быть выведено в отдельной строке, которые должны содержать: тип хода («R» — на этом ходе выбирается строка или «C» — на этом ходе выбирается столбец) и номер соответствующей строки или столбца. Строки и столбцы нумеруются натуральными числами начиная с единицы, строки нумеруются сверху вниз, а столбцы — слева направо.

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

Примеры

№	Входные данные	Выходные данные
1	2 2 -1 -3 1 -2	1 C 2
2	3 2 -1 -1 -1 -1 -1 -1	3 R 1 R 2 R 3

Жадный алгоритм Задачи на моделирование

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

Рассадка участников#38335

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

Входные данные
Программа получает на вход целое положительное число участников олимпиады N1000. Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.

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

Если задача не имеет решения, необходимо вывести одно число 0.

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

Примеры

№	Входные данные	Выходные данные
1	4 1005 1005 5 2005	1005 5 1005 2005
2	4 1005 1005 2005 1005	0

Алгоритмы сортировки Задачи на моделирование

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

Карточки#38322

Вася изготовил карточки, написав на них N первых заглавных букв латинского алфавита. Карточки Вася положил в стопку.

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

После этого оказалось, что карточки лежат строго по алфавиту, если просматривать их сверху вниз.

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

Входные данные
Вводится натуральное число N (N не превышает 26).

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

Примеры

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

Задачи на моделирование

✓ 24✗ 221 000средняяВойти и решать

Жук в деревне#38263

Однажды утром во время традиционной инспекции картофельного поля кот Матроскин обнаружил на одном из кустиков колорадского жука. Придя в ужас, он тут же помчался расспрашивать дядю Фёдора (как наиболее образованного из друзей) о том, как эти жуки размножаются и как с ними бороться.

Картофельные поля обычно очень аккуратно устроены: кусты картофеля рассажены на них так, что образуют клетчатое поле, где каждая клетка — картофельный куст. Как только на каком-то из кустов появляется колорадский жук, он начинает активно есть и размножаться. Поэтому каждый час на каждый куст будет добавляться столько же жуков, сколько соседних с ним по стороне кустов, уже зараженных жуками. Например, если у куста ровно один сосед, на котором уже есть жуки, то на него добавится один жук, а если все четыре соседа заражены жуками, то на куст добавится четыре новых жука. И если жуков не остановить, они заполнят собой все поле. Но к счастью, когда-то давно дядя Фёдор, прочитав статью в «Мурзилке», сделал отпугиватель колорадских жуков...

Если честно, Матроскин не очень понял, как работает этот отпугиватель. Но главное он запомнил: его надо установить на один из кустиков картофеля, и как только на этом кустике окажется ровно k колорадских жуков, что-то (вот этого Матроскин и не понял) произойдет и все жуки сбегут с поля.

Зная координаты куста картофеля, на который Матроскин установил отпугиватель, посчитайте, через сколько часов после появления первого колорадского жука на поле он подействует. Матроскин поставил ловушку в первый час после появления жука на поле.

Входные данные
Вам даны три числа: x и y — координаты кустика картофеля, на который Матроскин установил отпугиватель, и k — параметр отпугивателя (1<=k<=10⁹, |x|<=10⁹, |y|<=10⁹ ). Тот из кустов, на котором был найден первый жук, имеет координаты (0, 0) . Координаты всех кустов поля не превосходят 10⁹+1 по модулю.

Выходные данные
Выведите одно целое число: через сколько часов ловушка сработает. Если же ловушка никогда не сработает, выведите −1.

Примеры

№	Входные данные	Выходные данные
1	0 0 1	0
2	0 0 5	2

Вывод формулы Задачи на моделирование

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

Кассы#38195

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

Входные данные
Сначала вводится одно целое число N (0 < N ≤ 1000).

В каждой из следующих N строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), оставшиеся два — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч. 30 мин. до 18 ч. 30 мин., ежесуточно работает 480 минут.

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

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 0 23 0 12 0 12 0 22 0 2 0	120	Первая касса работает с часу до 23 часов, вторая – круглосуточно, третья – с 22 часов до 2 часов ночи следующего дня. Таким образом, все три кассы одновременно работают с 22 до 23 часов и с часу до двух часов, то есть 120 минут.
2	2 9 30 14 0 14 15 21 0	0	Первая касса работает до 14 часов, а вторая начинает работать в 14 часов 15 минут, то есть одновременно кассы не работают.
3	2 14 00 18 00 10 00 14 01	1	Вместе кассы работают лишь одну минуту – с 14:00 до 14:01 (в 14:01 вторая касса уже не работает).

Дата и время Задачи на моделирование

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

Год Коровы#38138

Известно, что в Китайском календаре года следуют 12-летнему циклу: Ox(Бык), Tiger(Тигр), Rabbit(Кролик), Dragon(Дракон), Snake(Змея), Horse(Лошадь), Goat(Коза), Monkey(Обезьяна), Rooster(Петух), Dog(Собака), Pig(Свинья), Rat(Крыса), и затем Ox опять.
Уже много лет корова Беси гордится, что она родилась в год Быка. Её подружка Эльза хочет узнать сколько лет отделяет её рождение от рождения Беси и надеется, что вы поможете ей узнать это, основываясь на отношениях между датами рождения некоторых коров на ферме.

Входные данные
Первая строка ввода содержит целое число N (\(1<=N<=100\)). Каждая из следующих N строк содержит 8-словную фразу указывающую отношение между датами рождения двух коров. В следующей форме

"Mildred born in previous Dragon year from Bessie",

или

"Mildred born in next Dragon year from Bessie" (previous - предыдуший, next-следующий).

Последнее слово - имя коровы, которое или Bessie или корова ранее упомянутая в предыдущей строке ввода.
Первое слово - имя коровы, которая не Bessie и ещё не упоминалась на вводе. Все имена коров имеют не более 10 символов a..z или A..Z.

5-ое слово - один из знаков зодиака, указаных ранее.

4-ое слово либо "previous" либо "next". Например, фраза "Mildred born in previous Dragon year from Bessie", означает, что год рождения Mildred был год Дракона(Dragon), ближайший и строго раньше (не равен) года рождения Беси.

Выходные данные
Выведите количество лет, на которое отличаются дни рождения Беси и Эльзы. Гарантируется, что это число может быть определено из введённых данных.

Примеры

№	Входные данные	Выходные данные	Примечание
1	4 Mildred born in previous Dragon year from Bessie Gretta born in previous Monkey year from Mildred Elsie born in next Ox year from Gretta Paulina born in next Dog year from Bessie	12	В примере выше Elsie родилась на 12 лет раньше Bessie. Mildred родилась на 9 лет раньше Bessie. Gretta родилась на 17 лет раньше Bessie. Paulina родилась на 9 лет раньше Bessie.

Задачи на моделирование Цикл while

✓ 3✗ 121 100средняяВойти и решать