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

Задачи из рубрикатора

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

Условие задачи  
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-ого урока: сначала часы, потом минуты, разделяя их пробелом.

Примеры
Входные данные Выходные данные
1 1 8 45
2 6 12 55

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 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