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

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

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

• «YES», если в поезде есть свободные места. В этом случае пассажир покупает один билет с L-й по R-ю станцию.
• «NO», если подходящих свободных мест нет. В этом случае пассажир билет не покупает.

 

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

В первой строке находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.

Следующие k строк содержат по два натуральных числа L_i и R_i (1 ≤ L_i < R_i ≤ n)  — начальная и конечная станции в i-м обращении к системе.

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

Для каждого обращения к системе в своей строке выведите её ответ: YES или NO.

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

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

 

Мальчик Филя прочитал в одном научном журнале, что не так давно астрономы открыли новую планету, на которой как и на Земле существует жизнь. Ученые уже установили связь с ее жителями и успели выяснить, что эта планета обращается вокруг своей оси за другое время, поэтому сутки здесь длятся не 24 часа. На ней, так же как и на Земле, время измеряется часами, минутами и секундами. Но количество минут в часе, и секунд в минуте не совпадает с привычными земными.

А именно: в одном часе A минут, в одной минуте B секунд. Также, в одних сутках на этой планете X часов, Y минут Z секунд. То есть когда часы должны показать момент времени X:Y:Z, они показывают 0:0:0, и с этого момента начинается отсчет новых суток

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

Филя увлекается нумерологией, поэтому его интересует вопрос: сколько хороших моментов времени на часах этой планеты будет показано с момента времени H1:M1:S1 до момента времени H2:M2:S2 включительно. Филя называет момент времени хорошим, если в нем не содержится цифры c, то есть ни один из дисплеев не содержит (с учетом вышеописанных правил) цифру c.

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

В первой строке находятся два натуральных числа A, B (1 ≤ A, B ≤ 50) — количество минут в часе и секунд в минуте.
В следующей строке находятся три целых числа X, Y, Z (0 ≤ X ≤ 50, 0 ≤ Y < A, 0 ≤ Z < B) — количество часов, минут и секунд в сутках. Гарантируется, что X, Y, Z одновременно не равны нулю.
В следующей строке находятся три целых числа H1, M1, S1— стартовое время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
В следующей строке находятся три целых числа H2, M2, S2— конечное время время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
Обратите внимание, что моменты времени могут находиться в разных сутках. Также обратите внимание, что моменты времени могут совпадать. В этом случае в интервале находится единственный момент времени.
В следующей строке находится цифра c (0 ≤ c < 10).

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

Требуется вывести одно число — количество хороших моментов времени с H1:M1:S1 до H2:M2:S2 включительно.

 

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

Ввод	Вывод
3 2 5 0 0 0 0 0 1 0 0 3	7
4 2 3 1 1 1 0 0 0 0 0 0	6
50 50 24 0 0 3 0 0 18 15 0 7	26956

 

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

А именно: в одном часе A минут, в одной минуте B секунд. Также, в одних сутках на этой планете X часов, Y минут Z секунд. То есть когда часы должны показать момент времени X:Y:Z, они показывают 0:0:0, и с этого момента начинается отсчет новых суток

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

Гриша увлекается нумерологией, поэтому его интересует вопрос: сколько хороших моментов времени на часах этой планеты будет показано с момента времени H1:M1:S1 до момента времени H2:M2:S2 включительно. Гриша называет момент времени хорошим, если в нем содержится хотя бы одна цифра c, то хотя бы один из дисплеев содержит (с учетом вышеописанных правил) цифру c.

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

В первой строке находятся два натуральных числа A, B (1 ≤ A, B ≤ 50) — количество минут в часе и секунд в минуте.
В следующей строке находятся три целых числа X, Y, Z (0 ≤ X ≤ 50, 0 ≤ Y < A, 0 ≤ Z < B) — количество часов, минут и секунд в сутках. Гарантируется, что X, Y, Z одновременно не равны нулю.
В следующей строке находятся три целых числа H1, M1, S1— стартовое время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
В следующей строке находятся три целых числа H2, M2, S2— конечное время время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
Обратите внимание, что моменты времени могут находиться в разных сутках. Также обратите внимание, что моменты времени могут совпадать. В этом случае в интервале находится единственный момент времени.
В следующей строке находится цифра c (0 ≤ c < 10).

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

Требуется вывести одно число — количество хороших моментов времени с H1:M1:S1 до H2:M2:S2 включительно. 

 

Ввод	Вывод
3 2 5 0 0 0 0 0 1 0 0 3	0
4 2 3 1 1 1 0 0 0 0 0 0	14
50 50 24 0 0 3 0 0 18 15 0 7	11295

В школьную столовую пришли n учеников разных классов и выпили суммарно k стаканов компота. Кассирша тетя Таня хорошо знает всех учеников, поэтому про i-го пришедшего школьника она знает число a_i — минимальное количество стаканов компота, которое мог выпить этот школьник. Также она знает, i-й школьник выпьет явно не больше a_i+x стаканов компота. Теперь ей стало интересно: а какое максимальное количество стаканов компота гарантированно выпил один из школьников? То есть она хочет найти такое максимальное число m, что при любом корректном распределении количества выпитых стаканов компота между школьниками, школьник, выпивший максимальное количество стаканов компота, выпил их не менее чем m штук. Помогите ей с этой задачей.

Формат входного файла

В первой строке входного файла input.txt находятся три натуральных числа n, k, x (1 ≤ n ≤ 100; 1 ≤ k ≤ 2 · 10⁴; 1 ≤ x ≤ 100) — количество школьников, пришедших в столовую, количество стаканов компота, выпитого ими, и максимальное количество стаканов, которое каждый школьник мог выпить сверх своего минимального количества, соответственно.
В следующей строке находятся n целых чисел a_i (1 ≤ a_i ≤ 100), разделенных пробелами, — минимальное количество стаканов компота, которое выпил i-й школьник.
Гарантируется, что входные данные корректны.

Формат выходного файла

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

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

Ввод	Вывод	Комментарий
3 4 1 1 1 2	2	Так как всего было выпито 4 стакана компота, а школьники выпили хотя бы 1, 1 и 2 стакана соответственно, первый школьник выпил ровно 1 стакан, второй — ровно 1 стакан, третий — ровно 2 стакана. Следовательно, ответ равен 2.
3 6 1 1 1 2	2	Каждый из школьников мог выпить по 2 стакана компота. Значит, ответ 3 гарантировать нельзя. Следовательно, ответ равен 2.
3 7 1 1 1 2	3	Так как всего выпито 7 стаканов компота, хотя бы один школьник выпил 3 стакана. Ответ 4, очевидно, недостижим. Следовательно, ответ равен 3.
3 12 2 1 2 4	5	Первый школьник выпил хотя бы 1 стакан и не более 3, второй — хотя бы 2 и не более 4, третий — хотя бы 4 и не более 6. Невозможно выпить 12 стаканов компота, если третий школьник выпьет ≤ 4 стакана, следовательно, ответ равен 5.

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

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

• Ящик под номером i поступает на склад.
• Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
• Поступающий ящик помещается наверх найденной или сформированной стопки.
• Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

 

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

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

В первой находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k)  — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков будут отправлены.

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

 

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

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

Е-елка
О-охрана
1-зона 1
2-зона 2
3-зона 3
4-зона 4
Х-олени
К-зайцы
С-снеговики
М-медведи
Л-лисицы
В-волки
П-подарки
Д-деды Морозы.

Вот план для размеров поля 9 на 9. Размер поля всегда нечетный и больше 8.

О М М М 2 С С С О
Л О М М 2 С С О К
Л Л О М 2 С О К К 
Л Л Л О О О К К К
3 3 3 О Е О 1 1 1
В В В О О О Х Х Х
В В О П 4 Д О Х Х
В О П П 4 Д Д О Х
О П П П 4 Д Д Д О

Человек, находящийся в зоне 1, одет в зайца, если стоимость его костюма кратна 3, в противном случае, он одет в оленя.
Человек, находящийся в зоне 2, одет в снеговика, если стоимость его костюма кратна 5, в противном случае, он одет в медведя.
Человек, находящийся в зоне 3, одет в лисицу, если стоимость его костюма кратна 5, в противном случае, он одет в волка.
Человек, находящийся в зоне 4, одет в подарок, если количество единиц его стоимости , записанной в двоичной системе счисления, больше количества нулей, в противном случае, он одет в Деда Мороза.
Про каждый костюм известно, за сколько его можно сшить.
Посчитайте и выведите стоимость костюма елки, затем охраны.
Затем надо вывести в порядке убывания стоимость и название костюма персонажа.

• Входные данные:
  Вводится n-размер квадратной матрицы, затем сама матрица.
• Выходные данные:
  Вывести сначала стоимость костюма елки, затем сумму всех костюмов охраны, затем в порядке убывания стоимость костюмов остальных персонажей и название костюма.
• Входные данные:
  9
  0 1 1 0 2 5 5 4 1
  2 3 2 4 5 6 1 2 0
  1 2 3 4 2 3 1 2 3
  1 2 2 4 3 5 7 1 2
  0 2 3 1 2 3 4 5 6
  0 1 2 3 5 3 3 4 5
  5 6 2 7 4 2 2 4 2
  8 4 3 4 3 1 3 4 5
  6 7 8 2 5 2 1 3 3
• 2
  58
  39 podarok
  32 olen
  27 snegovik
  27 volk
  21 zayka
  16 medved
  16 ded moroz
  10 lisiza

(с) Чуканова Юля, 10и

Герцог Циклонский, обладая безграничным могуществом, что отражено в его девизе "Все могу!", ежегодно проводит конкурс среди приглашенных на исполнение самого заветного желания.
Отбор проводится следующим образом: все претенденты рассаживаются на пронумерованных стульях (нумерация стульев начинается с 1) вокруг Большого Круглого стола, после чего посредством Константы счета начинается отсчет по часовой стрелке.
Претендент, на которого падает Константы счета, обязан освободить место, отсчет продолжается до тех пор, пока не останется два человека. 
Требуется при известном числе гостей N и Константы счета С определить номера стульев, которые нужно занять, чтобы попасть в число этих двух "счастливчиков".

Входные данные
В первой строке вводится число N (\(1<=N<=100\))  - количество приглашенных претендентов. Во второй строке вводится Константы счета (\(С<=100\)).

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

Примеры

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

У нас было 2 набора юного химика, 75 мятных таблеток, 5 упаковок оберточной бумаги, полфунта детских драже и целое множество подарков всех сортов и расцветок, а также машинки, куклы,  мешок вкусного оленьего корма, пинта чистого сока и стадо быстрых оленей.
Не то что бы это был необходимый запас для поездки. Но если начал развозить подарки, становится трудно остановиться.
Единственное что вызывало у меня опасение - это олени. Нет ничего более непредсказуемого, чем стадо северных оленей, кто знает чего от них ожидать?  Я догадывался, что рано или поздно они дадут о себе знать.
Самое страшное, что домов, куда нужно доставить подарки, более 10^100000000 и ребенок сильно расстроится, узнав, что не получил подарка на Новый Год. Этого допускать нельзя, благо вы - не единственный Санта, и вам будет достаточно доставить подарки только в своем городе. Детишек в вашем городе не больше 10^4, но все они живут в разных домах. У вас есть список, в котором не больше 10^4 элементов, каждый элемент списка представляет собой 2 целых числа – координаты дома следующего ребеночка.  Доставив подарки в очередной дом, вы, как порядочный Санта, обязаны стирать координаты этого дома из своего списка. Но ваши олени не хотят спокойно доставлять подарки, они коллективно прокладывают на их взгляд более оптимальный и правильный маршрут, и выбирают номер следующего дома из вашего списка по своей очень логичной и тривиальной формуле:
N_next  = |(K₁  - K₂  ) *R|% L,
где N_next – номер следующего дома в вашем списке (Как делают настоящие ТРУ-программисты? Они считают элемент с  единицы нуля!)  K₁  - количество еще не посещенных домов, K₂ – количество уже посещенных домов, R – коэффициент рандомности стада и L – длина текущего списка. Заметим, что после посещения дома, количество элементов в вашем списке уменьшается, вы же порядочный Санта, верно? Вечером, после тяжелого трудового дня, вы, как и остальные труженики Новогоднего фронта,  выкладываете в свой блог количество  километров, которые сегодня преодолели. Изначально вы находитесь в доме с индексом 0 и считается, что подарок в этот дом уже доставлен.  Зная столь тривиальную, понятную и очевидную формулу расчета следующего дома, а также имея список домов и  хорошо зная свое стадо, вплоть до их коэффициента рандомности, скажите какое расстояние  вы пройдете за всю поездку? Ответ округлите вверх до целых, в таких вещах можно чуть-чуть  преувеличить.  
 
Входные данные:
В первой строке входного файла находятся целые положительные числа N, R (1<N<=10000,1< R <1000000) – количество детей в вашем списке и коэффициент рандомности вашего стада, соответственно.
В следующих N строках находятся по 2 целых числа X,Y (-100000<=X,Y<=100000) – координаты конкретного  дома.
Выходные  данные:
Выведете одно целое число – ответ на поставленную задачу.
 
Пример, как же без примера:
Входит:
4 2
1 1
0 0
2 0
2 1
Выходит:
6

(с) Ярослав Свиридов 10и

Пример вывода:
2


(с) Даниил Кирионенко  8и

GLaDOS приготовила для Челл новое, последнее испытание! В его рамках ей предстоит найти торт. Но всё не так-то просто — у неё отобрали портальную пушку и завязали глаза. Единственное, что Челл известно, — что она находится в прямоугольной комнате, выложенной квадратной плиткой, и что где-то в этой комнате расположен торт. Всё что остаётся делать Челл, — слепо переходить с плитки на плитку в поисках торта.

Кроме того, так как действие происходит в Лаборатории Исследования Природы Порталов, на каждой стене комнаты расположен портал, связанный с противоположной стеной. Формально: рас- смотрим комнату как прямоугольную сетку размера W × H и введем систему координат так, чтобы левая нижняя ячейка сетки имела координаты (0, 0), а правая верхняя — (W − 1, H − 1). За один шаг Челл может перейти в одну из четырёх соседних ячеек, причём попытка пройти сквозь стену приводит к тому, что Челл появляется с противоположной стороны комнаты. Например, шаг вниз из ячейки (x, 0) приведёт в ячейку (x, H −1), а шаг влево из ячейки (0, y) приведёт в ячейку (W −1, y).

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

Челл может найти торт, только оказавшись в одной клетке с ним. Помогите ей пройти последнее испытание! Формат взаимодействия с тестирующей системой Это интерактивная задача. Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже. Вам разрешается произвести не более 200 000 ходов. Чтобы переместиться в соседнюю ячейку, выведите строку, содержащую ровно один символ, задающий направление перемещения: «U» — вверх; «D» — вниз; «L» — влево; «R» — вправо. Затем вы должны считать строку, в которой будет находиться ровно один символ, обозначающий результат перемещения: • «Y» — после произведённого хода Челл оказалась в клетке с тортом; • «N» — после произведённого хода Челл оказалась в клетке, не содержащей торт; • «E» — служебный символ, обозначающий, что после произведённого хода Челл всё ещё не нашла торт, а ваша программа превысила ограничение на количество ходов. Обратите внимание, после считывания символа «Y» или «E» вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некор- ректным! Гарантируется, что в клетке, в которой исходно находится Челл, нет торта. В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасы- вайте буфер вывода — для этого используйте команды flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

В интеллектуальном шоу «Твоя игра» принимают участие 3 человека. Им даются 5 тем, каждая из которых содержит по 5 вопросов стоимостью 100, 200, 300, 400 и 500 баллов. Если игрок правильно отвечает на вопрос, то к его текущей сумме прибавляется стоимость вопроса, если же он допускает ошибку, то от его суммы стоимость вопроса отнимается. При этом у игрока может оказаться отрицательная сумма баллов.

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

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

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

В следующих строках содержится информация о сыгранном вопросе. Сперва идёт имя участника, отвечавшего на вопрос, а через пробел — полученная им сумма баллов. Если количество баллов положительно, то ответ оказался правильным, если же отрицательно, то игрок ошибся. Гарантируется, что разыгранное количество вопросов каждой стоимости (100, 200, 300, 400 и 500) не превосходит 5. Также гарантируется, что во время игры будет разыгран хотя бы один вопрос.

В последней строке находится надпись «GAME OVER», означающая, что игра окончена и больше вопросов не будет.

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

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

Ввод: