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


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 32947. Часы
Темы: Разбор случаев    Условный оператор    Задачи на моделирование   

Наручные часы на электронных чернилах могут показывать текущее время в нескольких разных формах. Одна из форм - это имитация механических часов со стрелками. Циферблат часов разделен на 12 больших часовых делений, а каждое из них - на 5 малых делений. Угол между малыми делениями на циферблате равен 6. Для экономии энергии перерисовка изображения происходит один раз в минуту, когда необходимо переместить минутную стрелку. Часовая стрелка также движется дискретно, перемещаясь через каждые 12 минут на одно малое деление. Таким образом в 12:35 часовая стрелка будет указывать на 2-е малое деление справа от 12 часов, а минутная будет указывать на 7 часов. Угол между стрелками в этот момент равен 162º. В 12:36 часовая стрелка переместится на 3-е малое деление после 12 часов, а минутная — на следующее малое деление после 7 часов. Угол между стрелками часов при этом не изменится.

Напишите программу, которая вычисляет величину "внутреннего" (меньшего) угла между часовой и минутной стрелкой в заданный момент времени.
Первая строка ввода содержит два целых числа, разделенных одним пробелом — время на часах, часы H и минуты M (\(1 <= H <= 12, 0 <= M <= 59\)).
Вывести одно целое число в диапазоне от 0 до 180 — величину угла между стрелками в градусах.
 
Примеры
№ Входные данные Выходные данные
1 12 35 162

ID 38138. Год Коровы
Темы: Цикл while    Задачи на моделирование   

Известно, что в Китайском календаре года следуют 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.

ID 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 вторая касса уже не работает).

ID 38320. Конец K-ого урока
Темы: Целые числа    Задачи на моделирование   

В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается K-ый урок?»

Формат входных данных
Вводится одно натуральное число K, не превышающее 15.

Формат выходных данных
Выведите время окончания K-ого урока: сначала часы, потом минуты, разделяя их пробелом.
ID 38321. Расстановка ноутбуков
Темы: Задачи на моделирование    Условный оператор   

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

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

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

Примечание
В примерах указаны всевозможные ответы на поставленную задачу. Ваша программа должна вывести один из них.

Примеры
№ Входные данные Выходные данные
1 10 2 2 10 20 2
2 20
4 10
10 4
2 5 7 3 2 9 5
5 9

ID 38322. Карточки
Темы: Задачи на моделирование   

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

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

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

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

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

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

Примеры
№ Входные данные Выходные данные
1 3 BCA
2 6 CDBEAF

ID 38324. Ёлочка
Темы: Символы    Задачи на моделирование   

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

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

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

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

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

Гарантируется, что входные данные будут таковы, что количество символов, которое нужно будет вывести в одной строке, не превысит 79.

Выходные данные
Выведите требуемый «рисунок». Для лучшего понимания смотрите примеры.
 

Примеры
№ Входные данные Выходные данные
1 2
3 2
3 3		 
...#......#....
..###....###...
...#....#####..
..###.....#....
.#####...###...
...#....#####..
..###..#######.
.#####....#....
#######..###...
........#####..
.......#######.
......#########
2 3
1 1
2 1
3 2		 
#.#...#...
..#..###..
.###..#...
.....###..
....#####.
......#...
.....###..
....#####.
...#######

ID 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

ID 38352. Оцените пассажиропоток
Темы: Задачи на моделирование   

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

Входные данные
Во входных данных записано сначала число N (2≤N≤100) – количество остановок на маршруте. Далее задается количество человек, севших в автобус на конечной. Далее идет (N-2) пары чисел, задающих для промежуточных остановок количество вышедших и количество вошедших пассажиров. Наконец, идет число, задающее количество вышедших из автобуса на конечной остановке.

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

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

Примеры
№ Входные данные Выходные данные Пояснение
1 5
10
3 1
5 10
0 2
15		 15 На конечной в автобус село 10 человек. Далее 3 вышло и 1 зашел. В автобусе стало 8 человек. На следующей остановке вышло 5 и зашло 10. Стало 13 человек. На последней промежуточной остановке никто не вышел, а зашло 2 человека. На конечной вышло 15 человек. Итого максимальное количество – 15.
2 5
10
10 0
0 0
0 10
10		 10 На конечной село 10 человек, которые на следующей остановке вышли. После этого на следующей остановке никто не сел и никто не вышел. Дальше опять село 10 человек, которые доехали до конечной.
3 5
0 
0 9
3 4
2 0
8		 10 С конечной автобус отправился без пассажиров. Дальше в него село 9 человек. На следующей остановке 3 вышли и зашли 4. В автобусе стало 10 человек. На следующей остановке 2 вышли и никто не зашел. 8 человек доехало до конечной. Максимальное количество пассажиров составляло 10
4 3
100
0 100
200		 200 На начальной и на промежуточной остановку в автобус село по 100 человек. Вышло из автобуса 200 человек.

ID 38359. Черно-белые палиндромы
Темы: Задачи на моделирование   

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

Вам дана полоса длины N. Требуется разрезать ее на полоски, являющиеся палиндромами, так, чтобы количество получившихся полосок было строго меньше величины (2/5)N + 3.

Входные данные
Первая строка входного файла содержит число N — длину исходной полосы (N — натуральное число, не превышающее 100000). Далее идет N чисел, описывающих раскраску полосы: 0 означает черную клетку, а 1 — белую.

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

Примеры
№ Входные данные Выходные данные Пояснение
1 6
0 1 0 1 1 0		 3 5 Из исходной полосы мы получим 3 полосы-палиндрома, сделав разрезы после 3-й клетки (то есть между 3-й и 4-й) и после 5-й (то есть между 5-й и 6-й)
2 6
0 1 1 0 0 0		 1 3 Данную полосу можно разрезать на 2 полосы-палиндрома, однако по условию не требуется искать решение с минимальным числом получившихся полосок — достаточно, чтобы число полосок удовлетворяло указанному в условии ограничению.
3 5
0 0 0 0 0		   Исходная строка уже является палиндромом, поэтому можно ничего не разрезать

ID 38360. Луч света в темном царстве
Темы: Задачи на моделирование    Двумерные массивы   

Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

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


Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).

Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.

Примеры
№ Входные данные Выходные данные
1 
3 5
X....
.....
.....
 
XXXXX
XXXXX
XXXXX
2 
3 3
...
..X
...
 
/X\
X.X
\X/

ID 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

ID 38573. Роботы
Темы: Обход в ширину    Задачи на моделирование   

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

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

Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).

Входные данные
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

Выходные данные
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Примеры
№ Входные данные Выходные данные
1 4 5
1 2
2 3
3 4
1 4
1 3
3
1 2 4		 1
2 3 2
1 2
2 3
2
1 3		 1

ID 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

ID 38596. Игра в пьяницу
Темы: Очередь    Задачи на моделирование   

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

Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").

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

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

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

Выходные данные
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 106 ходов игра не заканчивается, программа должна вывести слово botva.

Примеры
№ Входные данные Выходные данные
1 1 3 5 7 9
2 4 6 8 0		 second 5

ID 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

ID 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
*****
*...*
*.***
*....
**...

ID 39388. Отслеживание контактов
Темы: Задача на реализацию    Задачи на моделирование    Перебор   

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

  1. Ровно одна корова была инфицирована изначально (нулевой пациент).
  2. После того, кaк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
  3. Однажды заболев, она остаётся больной.

К несчастью, ФД не знает, какая из его N коров, является "нулевым пациентом", кроме того он не знает значение K!. Помогите ему сузить диапазоны этих неизвестных, основываясь на его данных. Гарантируется, что ответ существует.

Входные данные
Первая строка ввода содержит N (2<= N <=100) и T (1 <= T <= 250). Следующая строка содержит строку длиной N, состоящую из 0 и 1, описывающую текущее состояние N коров ФД, 0 - здорова, 1 - больна. Каждая из последующих T строк описывает запись из списка взаимодействий ФД, и состоит из трёх чисел, t,x,y, где t - положительное целое время взаимодействия (t <= 250), x и y - различные целые в интервале 1…N, указывающее какие коровы взаимодействовали в момент времени T. В один момент времени T происходит не более одного взаимодействия.

Выходные данные
Выведите одну строку, содержащую три целых числа x,y,z, где x - количество различных коров, которые могли быть "нулевым пациентом", y - минимально возможное значение K, подходящее к исходным данным, z - наибольшее возможное значение K, подходящее к исходным данным. Если для K нет верхней границы, выведите "Infinity" для z. Заметим, что возможно K=0.
 
Примеры
№ Входные данные Выходные данные
1 4 3
1100
7 1 2
5 2 3
6 2 4		 1 1 Infinity

ID 39515. Три четыре пять корову поменять
Темы: Вывод формулы    Задача на реализацию    Задачи на моделирование   

N  коров (1 ≤ N ≤ 100) Фермера Джона выстроены в ряд. i-ая корова слева имеет метку i, для всех 1≤i≤N.
ФД приказал коровам повторить ровно K (1 ≤ K ≤109) раз следующий двухшаговый процесс:

Последовательность коров в позициях A1…A2 слева реверсивно меняют свой порядок (1≤A1<A2≤N).
Затем последовательность коров в позициях B1…B2 слева реверсивно меняют свой порядок (1≤B1<B2≤N).
Выведите получившийся порядок коров для всех i 1 ≤ i ≤ N после выполнения этого процесса ровно K раз.


Входные данные
Первая строка содержит N и K. Вторая строка содержит A1 и A2, третья строка содержит B1 и B2.
Выходные данные
На i-ой строке выведите метку i-ой коровы слева после завершения процесса всех обменов.

Примеры
№ Входные данные Выходные данные Пояснение
1 
7 2
2 5
3 7
 
1
2
4
3
5
7
6
 Изначально порядок коров слева направо такой     [1,2,3,4,5,6,7] 
После первого шага процесса порядок станет таким [1,5,4,3,2,6,7]
После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. 
Повторив оба шага ещё раз получим результат, приведенный в выводе.

ID 28323. Trapped in the Haybales
Темы: Задачи на моделирование   

Фермер Джон получил груз из N больших стогов сена (1≤N≤4000) и разместил эти стога в различных точках дороги, ведущей к его амбару. К несчастью, он совсем забыл, что Беси пасётся вдоль этой дороги и может оказаться в ловушке из этих стогов.
Каждый стог с номером j имеет размер Sj и уникальную позицию Pj, задающую его положение вдоль одномерной дороги. Беси начинает движение в некоторой позиции, где не было стога и может передвигаться свободно вдоль дороги, вплоть до позиции, где размещён стог сена, но она не может перейти эту позицию. В качестве исключения, если она движется в некотором направлении D единиц расстояния, она набирает достаточно скорости, чтобы протаранить любой стог сена с высотой строго меньше, чем D. Конечно, после того, как она сделает это, перед ней открывается пространство с другими стогами сена, которые она тоже может протаранить.
 
Беси может выйти на свободу как после самого левого, так и после самого правого стога сена. Пожалуйста, определите общую длину дороги, состоящую из тех позиций, из которых Беси не сможет выбраться. Например, если Беси не может выбраться если она начинает с позиции между стогами в позициях 1 и 5, тогда ответ будет 4 (поскольку эти позиции ограничивают область размером 4).
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит NN. Каждая из последующих NN строк описывает стог и содержит два целых числа, определяющих его размер и позицию, каждое в диапазоне 1…109.

ФОРМАТ ВЫВОДА:
Выведите целое число, определяющее длину части дороги из которой Беси не сможет сбежать.
 
Ввод Вывод
5
8 1
1 4
8 8
7 15
4 20
 14

ID 33125. Удаление чисел
Темы: Задачи на моделирование    Целые числа    Идеи   

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.
Выполняется один или несколько шагов по удалению чисел в этом ряду. На
очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.
Необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса.
Например, пусть n = 13, k = 2.
- На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
- На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
- На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
- На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.
Таким образом, число 13 будет удалено на третьем шаге.
Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.
Формат входных данных
Первая строка входных данных содержит целое число n (3 ≤ n ≤ 1018).
Вторая строка входных данных содержит целое число k (2 ≤ k ≤ 100, k < n).
Формат выходных данных
Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.
 
Ввод Вывод
13
2		 3


 
ID 34778. Турнир
Темы: Задачи на моделирование    Задача на реализацию    Структуры данных   

В турнире участвуют N команд. Турнир проводится по олимпийской системе (команды играют на вылет, проигравшие команды выбывают из турнира, выигравшие проходят в следующий тур, ничьих не бывает). Число команд в этой задаче будет степенью двойки: N = 2 k .

Все команды пронумерованы числами от 1 до N. В первом туре играют команды с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 матчей. По результатам этих матчей команды выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д.

Вам даны результаты всех матчей. Определите номер команды, которая стала победителем турнира.
В первой строке входных данных записано число N – количество команд, участвовавших в турнире. Оно является степенью двойки и может принимать значения от 20 = 1 до 216 = 65536. Следующие N − 1 строк содержат результаты всех сыгранных матчей. Первые N/2 строк из них являются результатами матчей первого тура, затем идёт N/4 строк с результатами второго тура, N/8 строк с результатами третьего тура и т. д.

Результат каждого матча является одним из двух возможных чисел: 1 или 2. Число 1 означает, что в матче выиграла первая команда (номер которой меньше), число 2 означает, что в матче выиграла вторая команда (номер которой больше).
Программа должна вывести одно число – номер победившей в турнире команды.
 

Ввод Вывод
8
1
2
2
1
2
1
1		 4

Примечание к ответу
Далее нарисована схема турнира для примера из условия. В турнире участвовало 8 команд. Результаты матчей: 1, 2, 2, 1, 2, 1, 1.
В первом туре играли команды 1 и 2, 3 и 4, 5 и 6, 7 и 8. Результаты матчей первого тура: 1, 2, 2, 1, во второй тур вышли команды 1, 4, 6, 7.
Во втором туре играли команды 1 и 4, 6 и 7. Результаты матчей второго тура: 2, 1.
В третий тур вышли команды 4 и 6. В последнем, третьем, туре играют команды 4 и 6, результат матча: 1, поэтому победителем турнира является команда 4.
ID 34881. Ожерелье
Темы: Сортировка "пузырьком"    Задачи на моделирование   

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

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

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

Входные данные
Первая строка входных данных содержит  число N (2 ≤ N ≤ 50).

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

Выходные данные
Ваша программа должна вывести описание процесса упорядочения.

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

Количество выводимых строк  не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается,  программа должна вывести одно число –1
 

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

ID 39057. Наша Таня громко плачет
Темы: Задачи на моделирование    Динамическое программирование   

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

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

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

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

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

 

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

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

 

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

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

 

Примечание

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

  • За 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

ID 39056. Экономическая грамотность
Темы: Условный оператор    Задачи на моделирование   

Многие банки при оплате покупок их банковскими картами предлагают систему возврата части потраченных средств, называемую cashback .

Мама Алёны имеет три подобные карты с разными условиями возврата части потраченной суммы. На карту банка RR возвращается 5 рублей из каждых полных 100 рублей стоимости одной покупки. Например, 5 рублей возвращается и за покупку стоимостью 100 рублей, и 199 рублей. Банк BB возвращает 2 рубля с каждых 50 рублей покупки, и за покупку стоимостью 199 рублей он вернет уже 6 рублей. А банк ММ возвращает 3% с полной стоимости любой покупки (заметим, что при цене в целом числе рублей, 3% всегда будут составлять целое число копеек), поэтому за покупку в 199 рублей вернется 5 руб. 97 коп.

Алёна любит ходить вместе с мамой за покупками. Мама предложила Алёне определять, какую покупку какой картой оплачивать, чтобы сумма возврата была максимально возможной. Считайте, что оплата любой покупки возможна любой картой. Если какие-то две или все три карты дают лучшую сумму возврата с точностью до копеек, то Алёна выбирает ту из карт, которая ей больше нравится по оформлению. Больше всего Алёна любит карту банка MM, затем идёт карта банка BB, а меньше всего Алёне нравится карта банка RR.


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

Вводится одно целое число S ( 1 <= S <= 10 000 ) — стоимость покупки в рублях.


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

Выведите название банка RR , BB или MM в зависимости от того, картой какого банка выгоднее оплатить эту покупку. А при равенстве суммы возврата - название банка, определённого в условии задачи.

 

Примечание

В первом примере только банк MM вернёт часть суммы покупки. Второй пример разобран в условии задачи.

 
Примеры
№ Входные данные Выходные данные
1 10 MM
2 199 BB
3 101 RR

ID 50991. Полимино
Темы: Эвристические методы    Задачи на моделирование   

Известный математик Соломон В. Голомб предложил название полимино для связной фигуры, вырезанной из клетчатой бумаги по линиям сетки. Фигура называется связной, если из любой ее клетки можно добраться в любую другую, переходя из клетки в клетку через их общую сторону. Шахматист, добавил Голомб, сказал бы, что из любой клетки полимино можно дойти ладьей в любую другую. На рис. 1 приведены примеры восьми полимино.

Саша увлекается полимино. Для своих экспериментов она вырезает новое полимино из бумаги в клеточку или из старых полимино, оставшихся после предыдущих попыток. Далеко не всегда из старого полимино (рис. 2а, слева) можно вырезать новое (рис. 2а, справа). Поэтому Саша может перед вырезанием нового полимино разделить каждую клетку старого полимино на K2 одинаковых квадратных клеток меньшего размера (см. рис. 2б, здесь K = 2).
 

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

Например, на рис. 2б приведены все возможные способы вырезания полимино, приведенного на рис. 2а, при K = 2.

Напишите программу, которая ответит на интересующий Сашу вопрос.


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

Первая строка входных данных содержит число K (1 ≤ K ≤ 10 000).

Далее следуют описания двух полимино, сначала нового, затем старого. Каждое полимино задается следующим образом — в первой строке описания задаются размеры H (высота) и W (ширина) минимально возможного прямоугольника, в котором можно разместить данное полимино. Следующие Н строк содержат по W символов описания клеток. При этом клетка, входящая в полимино, обозначается символом « X» (прописная латинская буква «икс»), а не входящая — символом «.» (точка). Количество клеток в каждом полимино не превышает 300.


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

Выведите одно число — количество различных способов вырезать заданное новое полимино из старого, каждая клетка которого разбита на K2 клеток.
ID 53906. Цифровое табло
Темы: Задачи на моделирование    Двумерные массивы   

В комнате у Аркадия Семеновича Тапкина стоят электронные часы. Цифры на этих часах показываются в специальной псевдографике. А именно каждое поле, на котором изображается цифра, состоит из \(w\) ячеек в ширину и \(h\) ячеек в высоту (при этом ячейки на поле имеют форму квадратов).

Но недавно у Аркадия Семеновича появилась проблема. Последнее время он стал плохо видеть. В связи с этим он хочет увеличить изображение этих цифр. Он уже приладил старый \(19''\) монитор к часам, и теперь дело осталось за малым. Осталось написать программу, которая будет рисовать цифры на дисплее. Аркадий Семенович хочет увеличить изображение в \(k\) раз и сделать толщину линий равной \(d\). Помогите ему в этом.

Опишем более формально понятие <<увеличить в \(k\) раз>>. Занумеруем ячейки поля \(w \times h\) сверху вниз и слева направо. Таким образом, верхняя левая ячейка имеет координаты \((0, 0)\), правая нижняя — \((w - 1, h - 1)\), правая верхняя — \((w - 1, 0)\), левая нижняя — \((0, h - 1)\). Кроме этого, введем декартову прямоугольную систему координат так, что начало координат находится в центре верхней левой ячейки, ось \(Ox\) направлена вправо, ось \(Oy\) — вниз, длину единичного отрезка примем равной длине стороны ячейки. Таким образом, координаты центра ячейки совпадают с ее координатами во введенной нумерации.

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

Увеличенная в \(k\) раз цифра рисуется на поле размером \((w - 1) \cdot (k - 1) + w\) ячеек по горизонтали на \((h - 1) \cdot (k - 1) + h\) ячеек по вертикали.

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

После этого, для того, чтобы получить толщину линий равную \(d\), дополнительно закрашиваются те ячейки, центры которых располагаются на расстоянии, не превышающем \((d - 1)\) от центров основных ячеек. Расстоянием между точками \(A(x_A, y_A)\) и \(B(x_B, y_B)\) будем называть число \(\rho(A, B) = |x_A - x_B| + |y_A - y_B|\).

По описанию цифры и параметрам \(k\) и \(d\) выведите изображение цифры, увеличенное в \(k\) раз, с толщиной линий \(d\).

Формат входных данных
Первая строка содержит целые числа \(k\) и \(d\) (\(1 \le k \le 100\), \(1 \le d \le 500\)). Вторая строка содержит целые числа \(w\) и \(h\) (\(1 \le w, h \le 10\)).

Третья строка содержит целое число \(n\) (\(1 \le n \le 100\)) — количество отрезков в описании цифры. Далее следуют \(n\) строк, каждая из которых описывает один отрезок. Описание отрезка состоит из четырех целых чисел: \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(0 \le x_1, x_2 < w\), \(0 \le y_1, y_2 < h\)) — координат концов отрезка.

Каждый из отрезков либо параллелен одной из координатных осей, либо идет под углом в 45 градусов к ней. Все отрезки имеют ненулевую длину.

Формат выходных данных
Выходные данные должны содержать ровно \((h - 1) \cdot (k - 1) + h\) строк по \((w - 1) \cdot (k - 1) + w\) символов в каждой, \(j\)-ый символ \(i\)-ой строки должен быть равен символу <<*>> (звездочка), если ячейка с центром в точке \((j,i)\) закрашена, и символу <<.>> (точка) — иначе.
ID 53922. Форматирование документа
Темы: Алгоритмы на строках    Задачи на моделирование   

Вася пишет новую версию своего офисного пакета <<Closed Office>>. Недавно он начал работу над редактором <<Dword>>, входящим в состав пакета.

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

Документ в формате редактора <<Dword>> представляет собой последовательность абзацев. Каждый абзац представляет собой последовательность элементов — слов и рисунков. Элементы одного абзаца разделены пробелами и/или переводом строки. Абзацы разделены пустой строкой. Строка, состоящая только из пробелов, считается пустой.

Слово — это последовательность символов, состоящая из букв латинского алфавита, цифр, и знаков препинания: <<.>>, <<,>>, <<:>>, <<;>>, <<!>>, <<?>>, <<->>, <<’>>.

Рисунок описывается следующим образом: <<(image параметры рисунка)>>. Каждый параметр рисунка имеет вид <<имя=значение>>. Параметры рисунка разделены пробелами и/или переводом строки. У каждого рисунка обязательно есть следующие параметры:

Параметр Описание
width Целое положительное число — ширина рисунка в пикселях
height Целое положительное число — высота рисунка в пикселях
layout Одно из следующих значений: embedded (в тексте), surrounded (обтекание текстом), floating (свободное) — описывает расположение рисунка относительно текста

Документ размещается на бесконечной вверх и вниз странице шириной \(w\) пикселей (разбиение на конечные по высоте страницы планируется в следующей версии редактора). Одна из точек на левой границе страницы условно считается точкой с ординатой равной нулю. Ордината увеличивается вниз.

Размещение документа происходит следующим образом. Абзацы размещаются по очереди. Первый абзац размещается так, что его верхняя граница имеет ординату 0.

Абзац размещается следующим образом. Элементы располагаются по строкам. Каждая строка исходно имеет высоту \(h\) пикселей. В процессе размещения рисунков высота строк может увеличиваться, и строки могут разбиваться рисунками на фрагменты.

Слова размещаются следующим образом. Считается, что каждый символ имеет ширину \(c\) пикселей. Перед каждым словом, кроме первого во фрагменте, ставится пробел шириной также в \(c\) пикселей. Если слово помещается в текущем фрагменте, то оно размещается на нем. Если слово не помещается в текущем фрагменте, то оно размещается в первом фрагменте текущей строки, расположенном правее текущего, в котором оно помещается. Если такого фрагмента нет, то начинается новая строка, и поиск подходящего фрагмента продолжается в ней. Слово всегда <<прижимается>> к верхней границе строки.

Размещение рисунка зависит от его расположения относительно текста.

Если расположение рисунка относительно текста установлено в <<embedded>>, то он располагается так же как слово, за тем исключением, что его ширина равна ширине, указанной в параметрах рисунка. Кроме того, если высота рисунка больше текущей высоты строки, то она увеличивается до высоты рисунка (при этом верхняя граница строки не перемещается, а смещается вниз нижняя граница). Если рисунок типа <<embedded>> не первый элемент во фрагменте, то перед ним ставится пробел шириной \(c\) пикселей. Рисунки типа <<embedded>> также прижимаются к верхней границе строки.

Если расположение рисунка относительно текста установлено в <<surrounded>>, то рисунок размещается следующим образом. Сначала аналогично находится первый фрагмент, в котором рисунок помещается по ширине. При этом перед рисунком этого типа не ставится пробел, даже если это не первый элемент во фрагменте.

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

Если расположение рисунка относительно текста установлено в <<floating>>, то рисунок размещается поверх текста и других рисунков и никак с ними не взаимодействует. В этом случае у рисунка есть два дополнительных параметра: <<dx>> и <<dy>> — целые числа, задающие смещение в пикселях верхнего левого угла рисунка вправо и вниз, соответственно, относительно позиции, где находится верхний правый угол предыдущего слова или рисунка (или самой левой верхней точки первой строки абзаца, если рисунок — первый элемент абзаца).

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

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

По заданным \(w\), \(h\), \(c\) и документу найдите координаты верхних левых углов всех рисунков в документе.

Формат входных данных
Первая строка содержит три целых числа: \(w\), \(h\) и \(c\) (\(1 \le w \le 1000\), \(1 \le h \le 50\), \(1 \le c \le w\)).

Далее следует документ. Размер входного файла не превышает 1000 байт. Гарантируется, что ширина любого слова и любого рисунка не превышает \(w\). Высота всех рисунков не превышает \(1000\). Относительное смещение всех рисунков типа <<floating>> не превышает \(1000\) по абсолютной величине.

Формат выходных данных
Выведите по два числа для каждого рисунка — координаты его верхнего левого угла. Выводите координаты рисунков в том порядке, в котором они встречаются во входных данных.

 
ID 53964. Изображение таблицы
Темы: Строки    Задачи на моделирование   

При разработке программ для просмотра веб-страниц одной из наиболее сложных задач является корректное отображение таблиц. Компания <<Kozilla>>, в которой вы работаете, планирует разработать новую версию браузера <<Waterrat>> для работы в терминальном режиме, и просит вас написать фрагмент ядра отображения веб-страниц, ответственный за формирование структуры таблиц.

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

Таблица состоит из строк, каждая строка состоит из одной или нескольких ячеек, \(j\)-я ячейка \(i\)-й строки имеет ширину \(a_{i,j}\).

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

Формат входных данных
Первая строка содержит \(n\) — количество строк в таблице (\(1 \le n \le 100\)). Следующие \(n\) строк входного файла содержат описание строк таблицы.

Описание каждой строки включает число \(m_i\) — количество ячеек этой строки, и \(m_i\) целых чисел \(a_{i,1}, a_{i,2}, \dots, a_{i,m_i}\) — ширину каждой из ячеек строки (\(1 \le m_i \le 10\), \(1 \le a_{i,j} \le 20\)).

Формат выходных данных
Выведите символическое изображение структуры таблицы.

Изображение \(i\)-й строки таблицы должно начинаться изображением горизонтальной линии, составленным из символов <<+>> (плюс) и <<->> (минус). Затем должна следовать строка, содержащая пробелы и символы <<|>> (вертикальная черта). Первым символом строки должна быть вертикальная черта, затем \(a_{i,1}\) пробелов, затем вертикальная черта, затем \(a_{i,2}\) пробелов, и так далее, всего \(m_i\) блоков пробелов. После последнего блока должна следовать вертикальная черта. После последней строки таблицы также должно следовать изображение горизонтальной линии.

В изображении горизонтальной линии используйте символ <<+>>, если сверху или снизу от этой позиции находится вертикальная черта, и <<->> в противном случае. Горизонтальная линия должна иметь минимальную возможную длину, чтобы над каждым символом вертикальной черты следующей строки и под каждым символом вертикальной черты предыдущей строки были символы <<+>>.
ID 53993. На лифтах через пропасть
Темы: Задачи на моделирование   

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

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

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

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

Формат входных данных
Первая строка содержит целое число \(n\) — количество лифтов (\(1 \le n \le 100\)). Следующие \(n\) строк содержат описания лифтов.

Каждое описание состоит из четырех целых чисел: \(l\), \(u\), \(s\) — самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах (\(-100 \le l \le s \le u \le 100\), \(l < u\)), и \(d\) — направление движения лифта в начальный момент (\(d = 1\) означает, что лифт двигается вверх, \(d = -1\) — вниз).

Формат выходных данных
Выведите минимальное время в секундах, необходимое чтобы перебраться на противоположный край пропасти. Если перебраться на противоположный край пропасти невозможно, выведите в выходной файл \(-1\).
ID 54204. Тупики
Темы: Сканирующая прямая    Куча    Задачи на моделирование   

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

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

Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Входные данные
Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 109. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.

Выходные данные
Выведите N чисел — по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию,  выведите два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.
ID 54267. Парикмахерская
Темы: Задачи на моделирование   

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

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

Входные данные
В первой строке вводится натуральное число N, не превышающее 100 – количество клиентов.

N строках вводятся времена прихода клиентов – по два числа, обозначающие часы и минуты (часы – от 0 до 23, минуты – от 0 до 59). Времена указаны в порядке возрастания (все времена различны).
Гарантируется, что всех клиентов успеют обслужить до полуночи.

Выходные данные
Требуется вывести N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-го клиента (часы и минуты).
ID 55065. Детский праздник
Темы: Бинарный поиск по ответу    Сканирующая прямая    Задачи на моделирование   

Организаторы детского праздника планируют надуть для него M воздушных шариков. С этой целью они пригласили N добровольных помощников, i-й среди которых надувает шарик за Ti минут, однако каждый раз после надувания Zi шариков устает и отдыхает Yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

Входные данные
В первой строке входных данных задаются числа M и N (0 <= M <= 15000, 1 <= N <= 1000). Следующие N строк содержат по три целых числа - Ti, Zi и Yi  соответственно (1 <= Ti, Yi <= 100, 1 <= Zi <= 1000).

Выходные данные
Выведите в первой строке число T - время, за которое будут надуты все шарики. Во второй строке выведите N чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.
ID 55075. Маджонг
Темы: Задачи на моделирование    Очередь   

Петя недавно узнал о существовании игры маджонг. Она ему показалась настолько интересной, что он играет в нее целыми днями. Для этой игры необходима прямоугольная доска размером m x n полей и набор фишек разных цветов. При этом фишек каждого цвета в наборе должно быть ровно две. В начале игры фишки располагаются на доске произвольным образом.

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


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

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

Задана начальная расстановка фишек на доске. Требуется найти самую длинную последовательность ходов, которую может сделать Петя из заданной позиции.
Входные данные
Первая строка входного файла содержит размеры доски: два целых числа m и n (1 ≤ m, n ≤ 300, хотя бы одно из этих чисел четно). Далее следуют m строк по n
 чисел в каждой, j-е число в i-й из этих строк представляет собой номер цвета j-й слева фишки в i-й горизонтали. Цвета пронумерованы натуральными числами от 1 до n*m / 2. На доске ровно две фишки каждого цвета.

Выходные данные
В первой строке выходного файла выведите k — максимальное количество ходов, которое может сделать Петя из заданной начальной позиции. Во второй строке выходного файла выведите разделенные пробелами k чисел — номера цветов фишек в том порядке, в котором они должны сниматься с доски. Если возможных ответов несколько, выведите любой.
ID 55398. Сортировка вагонов
Темы: Стек    Задачи на моделирование   

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.




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

Входные данные
Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

Выходные данные
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:

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

Если выстроить вагоны по порядку невозможно, выведите одно число 0.

 

Примеры
№ Входные данные Выходные данные
1 3
3 2 1		 1 3
2 3
2 4
4 1 3 2		 1 2
2 1
1 2
2 3
3 3
2 3 1		 0

ID 56036. Сортировка вагонов
Темы: Стек    Задачи на моделирование   

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.




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

Входные данные
Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

Выходные данные
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

 

Примеры
№ Входные данные Выходные данные Примечание
1 3
3 2 1		 YES Надо весь поезд завезти в тупик, а затем целиком вывезти его на 2-й путь.
2 4
4 1 3 2		 YES Сначала надо в тупик завезти два вагона, один из которых оставит в тупике, а второй — вывезти на 2-й путь, после чего завезти в тупик еще два вагона и вывезти 3 вагона, стоящие в тупике, на 2-й путь
3 3
2 3 1		 NO  

ID 55415. Фитнесс-клуб
Темы: Задачи на моделирование   

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

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

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

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

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

Входные данные
Первая строка входного файла содержит два целых числа: n (1≤n≤100) и k (1≤k≤1000) Каждая из последующих n строк содержит по два целых числа ai и bi (0≤ai,bi≤k, ai+bi≤k).

Выходные данные
В выходной файл выведите одно число — ответ на задачу.

Примечание
Пронумеруем шкафчики числами от 1 до 4. Посетителям, пришедшим на первую тренировку выдадим ключи так: тому, кто закроет, от шкафчика 1, тем, кто не закроет, от 2 и 3. Посетителям, пришедшим на вторую тренировку, выдадим ключи так: тому, кто закроет, номер 2, тому, кто не закроет, номер 3. В итоге открытым после окончания дня останется только шкафчик номер 3.
ID 44936. Исследование зеркальных цветов
Темы: Бинарный поиск по ответу    Задачи на моделирование   

Члены экипажа космического корабля «Пегас» приземлились на третьей планете Системы Медуза, для изучения зеркальных цветов. Их корабль приземлился в начале узкого поля фермы, на которой выращивают цветы. Зеркальные цветы начинают прорастать после полуночи. Любезные работники фермы предоставили экипажу план прорастания цветов в виде точки и времени прорастания. Экипажу корабля необходимо улетать с планеты в следующую полночь. Исследовательская группа корабля может передвигаться по планете с максимальной скоростью vmax. На исследование одного цветка группе необходимо время d. Исследовать цветок необходимо сразу весь, нельзя будет к нему вернуться позже. Цветы прорастают тем позже, чем дальше они расположены от начала поля. В одной точке прорастает только один цветок, и каждый цветок прорастает в свой момент времени. Нет двух цветков, которые бы проросли одновременно.
Команда экипажа хочет определить момент времени, когда исследовательская группа сможет вернуться на корабль, исследовав все цветы и затратив на исследование как можно меньше времени.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит 2 целых числа через один пробел: vmax (в см/мин) и d (в минутах), 0 < vmax <= 200, 0 <= d <= 500.
Вторая строка содержит одно число N – количество цветов (в штуках). 0 <= N <= 1400 при d = 0, в противном случае 0 <= N <= 200.
Далее идут N строк, в каждой из которых записано по два числа через пробел: целое число xi – расстояние от цветка до начала поля (в сантиметрах), 0 <= xi <= 32767, и число ti – момент прорастания цветка (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

Выходные данные
Выведите момент времени возвращения исследовательской группы на корабль (в формате hh:mm), округленный до целых минут в большую сторону.

Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Можно считать, что исследовательская группа не меняет направления движения до тех пор, пока не дойдет до последнего цветка.

 

Примеры
№ Входные данные Выходные данные
1 
3 1 
1
100 00:01
 
01:08
 
ID 55434. iDishwasher
Темы: Задачи на моделирование   

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

Входные данные
Единственная строка содержит числа B и W задающие количество белых и черных клеток соответственно (0≤B,W≤10000).

Выходные данные
Выведите одно число — максимальную длину стороны квадрата, который можно составить из данных клеток. Или слово "Impossible" если нельзя составить ни одного квадрата.