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

Электричка#90455

В столице Флатландии открыта линия городской электрички. На линии \(n\) станций, пронумерованных от \(1\) до \(n\). Линия проходит город по диаметру и обоими концами уходит в область. А именно, станции с \(1\)-й по \(a\)-ю находятся в области, затем станции с \((a+1)\)-й по \((b-1)\)-ю находятся в городе, а станции с \(b\)-й по \(n\)-ю находятся в области.

Стоимость билета на электричку зависит от начальной, конечной станции и того, через какие станции проезжает пассажир.

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

Напишите программу, которая по начальной станции \(s\) и конечной станции \(t\) определяет, какой тариф необходимо применить.

Формат входных данных
Первая строка содержит три целых числа: \(n\), \(a\) и \(b\) (\(3 \le n \le 10^9\), \(1 \le a\), \(b \le n\), \(b - a > 1\)).

Вторая строка содержит два целых числа: \(s\) и \(t\) (\(1 \le s, t \le n\), \(s \ne t\)).

Формат выходных данных
Если необходимо применить тариф <<город>>, выведите <<City>>.

Если необходимо применить тариф <<область>>, выведите <<Outside>>.

Если необходимо применить тариф <<полный>>, выведите <<Full>>.

Разбор случаев

✓ 2✗ 1—Войти и решать

Lights Out#90385

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

Амбар описывается простым (несамопересекающимся) многоугольником с целочисленными вершинами \((x_1, y_1) \ldots (x_n, y_n)\) перечисленными в порядке обхода по часовой стрелке. Его рёбра составляются чередующимися горизонтальными (параллельными оси Х) и вертикальными (параллельными оси Y) отрезками. Первое ребро может быть как горизонтальным, так и вертикальным. Выход расположен в точке \((x_1, y_1)\). Беси начинает в некоторой вершине \((x_i, y_i)\) для \(i > 1\). Она идёт только по периметру амбара, по часовой стрелке или против часовой стрелки, потенциально изменяя направления движения, в любой вершине. Её цель - пройти минимальное расстояние и добраться до выхода. Это довольно просто, когда свет включён - просто выбрать между движением по часовой стрелке и движением против часовой стрелки.

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

Помогите Беси определить минимальное количество, на которое возрастёт её путь в худшем случае при движении в темноте, по сравнению с движением при свете, полагая, что она движется оптимально в каждом случае. Оптимальная стратегия - такая, которая минимизирует увеличение расстояния в худшем случае.

ФОРМАТ ВВОДА (файл lightsout.in):

Первая строка ввода содержит \(N\) (\(4 \leq N \leq 200\)). Каждая из последующих \(N\) строк содержит по два целых числа, описывающих точки \((x_i, y_i)\) в почасовом порядке обхода. Все целые числа \(-100,000 \ldots 100,000\).

ФОРМАТ ВЫВОДА (файл lightsout.out):

Минимально возможное для худшего случая увеличение длины оптимального пути при походе в темноте по сравнению с походом при свете.

геометрия Задача на реализацию Разбор случаев

—Войти и решать

Fence Painting#90345

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

Если мы рассмотрим изгородь ФД как одномерную числовую прямую, то ФД закрашивает интервал между \(x=a\) and \(x=b\). Например, если \(a=3\) and \(b=5\), то ФД закрашивает интервал длиной 2. Беси, не понимая команды ФД, закрашивает интервал от \(x=c\) to \(x=d\), который может частично или полностью перекрываться с интервалом ФД. Пожалуйста, определите общую длину изгороди которую покрасят ФД и Беси.

Формат ввода (файл paint.in):

Первая строка ввода содержит целые числа \(a\) и \(b\), разделённые одним пробелом (\(a < b\)).

Вторая строка содержит целые числа \(c\) и \(d\), разделённые одним пробелом (\(c < d\)).

Значения \(a\), \(b\), \(c\), \(d\) все лежат в интервале \(0 \ldots 100\), включительно.

Формат вывода (файл paint.out):

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

Разбор случаев

—Войти и решать

Fence Painting#90336

Формат ввода (файл paint.in):

Первая строка ввода содержит целые числа \(a\) и \(b\), разделённые одним пробелом (\(a < b\)).

Вторая строка содержит целые числа \(c\) и \(d\), разделённые одним пробелом (\(c < d\)).

Значения \(a\), \(b\), \(c\), \(d\) все лежат в интервале \(0 \ldots 100\), включительно.

Формат вывода (файл paint.out):

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

Разбор случаев

—Войти и решать

Moorbles#90257

Беси и Эльза играют с шариками так: Беси и Эльза начинают игру с некоторым количеством шариков. Беси берёт \(A\) шариков из своих, а Эльза должна угадать является ли число \(A\) чётным или нечётным. Если Эльза угадает, она забирает эти \(A\) шариков, если нет - она отдаёт \(A\) своих шариков Беси. Если у Эльзы нет \(A\) шариков - она проиграла. Игрок проиграл, если остался без шариков.

После нескольких этапов игры, у Эльзы осталось \(N\) \((1 \leq N \leq 10^9)\) шариков. Она думает, что ей тяжело выиграть, она играет, чтобы не проиграть. Она хорошо изучила привычки Беси и заметила, что на \(i\)-ом ходу есть только \(K\) \((1 \leq K \leq 4)\) различных количеств шариков, которые может предложить Беси. Проходит всего только \(M\) \((1 \leq M \leq 3 \cdot 10^5)\) ходов прежде, чем Беси надоест, и она перестанет играть. Можете ли Вы определить лексикографически минимальную последовательность ходов такую, чтобы Эльза не проиграла вне зависимости от ходов Беси.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит целое число \(T\) (\(1 \leq T \leq 10\)) представляющее количество подтестов. Каждый подтест описывается следующим образом:

Сначала идёт строка, содержащая три целых числа \(N\), \(M\), \(K\), представляющая количество шариков у Эльзы, количество ходов, и количество потенциальных ходов, которые может сделать Беси, соответственно.
Затем идут \(M\) строк, где строка \(i\) содержит \(K\) различных разделённых одиночными пробелами целых чисел \(a_{i,1} \; a_{i,2} \ldots a_{i,K}\) (\(1 \leq a_{i, j} \leq 10^3\)) представляющих возможные количества шариков, которые Беси может выложить на \(i\)-ом ходу.

Гарантируется. что сумма \(M\) по всем подтестам не более \(3 \cdot 10^5\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого подтеста выведите лексикографически минимальную последовательность ходов Эльзы, которая гарантирует, что Эльза не проиграет или \(-1\), если Эльза проиграет. Последовательность ходов должна быть на одной строке и состоять из разделённых одиночными пробелами токенов, каждый из которых равен либо "Even" либо "Odd".

Замечание: "Even" лексикографически меньше чем "Odd".

Жадный алгоритм Разбор случаев

—Войти и решать

Reverse Engineering#90140

У Эльзы есть программа, которая получает на ввод массив из \(N\) (\(1\le N\le 100\)) переменных \(b[0],\dots,b[N-1]\), каждая из которых равна 0 или 1 и возвращает результат применяя последовательность операторов if / else if / else, указанную на вводе. Каждый оператор проверяет значение не более одной переменной и возвращает 0 или 1. Примером такой программы может быть:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

Например, если ввод в эту программу есть "10" (то есть, \(b[0] = 1\) и \(b[1] = 0\)), тогда вывод должен быть 1

Эльза должна сказать правильный ответ для \(M\) (\(1\le M\le 100\)) различных вводов. Бесси сейчас пытается сделать "реверс инжиниринг" для программы Эльзы. К несчастью, Эльза может и солгать - то есть не существует программы вида указанного выше, которая выведет ответы как сказала Эльза.

Для каждого из \(T\) (\(1\le T\le 10\)) подтестов определит, лгала Эльза или нет.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(T\), количество подтестов.

Каждый подтест начинается с двух целых чисел \(N\) и \(M\), за которыми следуют \(M\) строк, каждая из которых содержит \(N\) 0 и 1 представляющих ввод, т.е. значения \(b[0] \ldots b[N-1]\)) и один дополнительный символ (0 или 1), представляющий ответ. Подтесты разделены пустыми строками.

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого тесты выведите "OK" или "LIE" на отдельной строке.

Разбор случаев

—Войти и решать

Stuck in a Rut#90095

Недавно Фермер Джон увеличил размер своей фермы, теперь с точки зрения коров, она бесконечная по размеру. Коровы представляют пастбище фермы как бесконечную 2D решётку квадратных ячеек, каждая из которых заполнена вкуснейшей травой. (Думайте о каждой ячейке как о клетке на шахматной доске). Каждая из \(N\) коров (\(1\le N\le 1000\)) ФД начинает в различной ячейке. Некоторые начинают, глядя на север, а некоторые - на восток.

Каждый час корова или

Останавливается, если трава в текущей ячейке уже съедена другой коровой.
Съедает всю траву в текущей ячейке и перемещается на одну ячейку вперёд в своём исходном направлении.

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

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

ФД не любит, когда корова прекращает пастись, и он хочет узнать, кто виноват в его остановленных коровах. Если корова \(b\) остановилась в ячейке, которую съела корова \(a\), тогда он считает, что корова \(a\) остановила корову \(b\). Более того, если корова \(a\) остановила корову \(b\), а корова \(b\) остановила корову \(c\), он считает, что корова \(a\) также остановила корову \(c\) (то есть отношение "остановила" транзитивно). Каждая корова "виновата" в количестве коров, которые она остановила. Для каждой коровы вычислите количество остановленных ею коров.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит целое число \(N\). Каждая из последующих \(N\) строк описывает стартовую позицию коровы в терминах: символ (N или E, смотри на север или на восток) и и два неотрицательных целых числа \(x\) and \(y\) (\(0\le x\le 10^9\), \(0\le y\le 10^9\)) - координаты ячейки. Все \(x\)-координаты различны. Все \(y\)-координаты различны.

Чтобы было понятнее относительно направлений и координат, если корова в ячейке \((x,y)\) и двигается на север, то она попадёт в ячейку \((x,y+1)\), а если на восток - то в ячейку \((x+1, y)\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(N\) строк. Строка \(i\) должна описывать количество коров, которые остановила \(i\)-ая по вводу корова.

графы Разбор случаев реализация

—Войти и решать

Sleepy Cow Herding#90049

Три лучшие коровы Фермера Джона Беси, Эльза и Милдред всегда уходят далеко от фермы. Помогите ФД "сгрудить их в стадо".

Главное поле фермы можно представить в виде числовой прямой, и каждая корова находится в целочисленной координате. Все три координаты различны. ФД хочет переместить их так, чтобы они заняли последовательные координаты (например, 6,7,8).

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

Определите минимальное и максимальное количество перемещений, которое возможно сделать прежде чем коровы расположатся в трёх последовательных позициях.

ФОРМАТ ВВОДА (файл herding.in):

Входной файл содержит одну строку с тремя разделёнными пробелами целыми числами, определяющими координаты Беси, Эльзы и Милдред. Каждая координата - целое число в интервале \(1 \ldots 10^9\).

ФОРМАТ ВЫВОДА (файл herding.out):

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

Жадный алгоритм Задачи на моделирование Разбор случаев

—Войти и решать

Taming the Herd#90005

Однажды утром Фермер Джон проснулся от звуков дробления древесины. Это коровы ломали амбар.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

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

ФОРМАТ ВВОДА (файл taming.in):

Первая строка ввода содержит одно целое число \(N\) (\(1 \leq N \leq 100\)), обозначающее количество дней, с дня когда ФД начал логгирование.

Вторая строка содержит \(N\) целых чисел, разделённых одиночными пробелами. \(i\)-ое число это неотрицательное целое \(a_i\) (не более 100), указывающее что в день \(i\) на счётчике было \(a_i\) если коровы не подделали эту запись в логе.

ФОРМАТ ВЫВОДА (файл taming.out):

Вывод состоит из \(N\) целых чисел, по одному в строке. \(i\)-ое целое число должно содержать минимум из всех возможных последовательностей с \(i\) сломами количества записей, которые несостоятельны в этой последовательности.

Динамическое программирование: один параметр Жадный алгоритм Разбор случаев

—Войти и решать

65823#65823

Аспирант Шлёпов собирается провести чемпионат вуза по шахматам. Так как игроков в вузе много, у сообщества есть свой рейтинг ELO. Шлёпов собирается разделить игроков на основании этого рейтинга на две лиги. В высшей лиге должно играть не менее трети игроков, но при этом наименьшее возможное количество; отбор в лигу идёт на основании ELO. Двух игроков с одинаковым ELO распределять в разные лиги нельзя. Высшая лига на турнире должна быть обязательно. Определите, начиная с какого ELO, игроки попадают в высшую лигу.

Формат входных данных
На вход программе в первой строке подаётся натуральное число N (N ≤ 1000) – количество игроков. Далее в N строках идёт по одному натуральному числу k_i – рейтинг ELO игрока номер i (1 ≤ k_i ≤ 2500).
Формат выходных данных
Выведите одно целое число – ELO, начиная с которого, игроки попадают в высшую лигу. Если в высшей лиге окажется весь турнир, надо вывести наименьший ELO среди заявленных игроков.

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

Использование сортировки Разбор случаев

✓ 9✗ 10—Войти и решать

Переключая каналы#60951

Родители Лизы подключили пакет, содержащий N телевизионных каналов, пронумерованных числами от 1 до N. Переключать каналы можно с помощью двух кнопок на пульте: «+» и «−». Короткое нажатие на кнопку «+» приведёт к переключению на следующий канал, если номер текущего канала меньше N; если же номер текущего канала равен N, то телевизор продолжит показывать этот канал. Если кнопку «+» нажать и удерживать некоторое время, произойдёт переход на K каналов вперёд, при условии, что номер текущего канала не превосходит N − K. В противном случае произойдёт переход на канал N.
Аналогично, короткое нажатие на кнопку «−» приведёт к переключению на предыдущий канал, если номер текущего канала больше 1; если же номер текущего канала равен 1, телевизор продолжит показывать этот канал. Если кнопку «−» нажать и удерживать некоторое время, то произойдёт переход на K каналов назад при условии, что номер текущего канала превышает K. В противном случае произойдёт переход на канал 1.
Лиза включила телевизор и обнаружил, что он показывает канал P. Лиза знает, что очень скоро по каналу с номером U начнётся интересная передача. Определите, какое минимальное количество нажатий на кнопки пульта потребуется сделать Лизе, чтобы переключиться на канал U.
Формат входных данных
В первой строке содержится целое число N (3 ≤ N ≤ 10⁹ ) — количество телевизионных каналов.
Во второй строке содержится целое число K (2 ≤ K < N) — количество каналов, на которое осуществится переход назад или вперёд при удерживании соответствующей кнопки переключения.
В третьей строке содержится целое число P (1 ≤ P ≤ N) — номер канала, который показывает телевизор.
В четвёртой строке содержится целое число U (1 ≤ U ≤ N) — номер канала, на который желает переключиться Лиза. Гарантируется, что P = U.
Формат выходных данных
Выведите одно целое неотрицательное число — минимальное количество нажатий на кнопки пульта, которое необходимо для переключения с канала P на канал U.

Замечание
В первом примере Лизе следует сначала выполнить одно короткое нажатие на кнопку «+» и переключиться с канала 3 на канал 4, а затем трижды осуществить переход вперёд на 5 каналов: сначала переключиться с 4 на 9, затем с 9 на 14 и, наконец, с 14 на 19 канал.
Во втором примере Лиза может сначала переключиться коротким нажатием на кнопку «−» на канал 2, после чего выполнить три перехода вперёд на 5 каналов: с канала 2 на канал 7, затем на канал 12 и, наконец, на канал 17.
В третьем примере Лиза дважды выполнит короткое нажатие кнопки «−».
В четвёртом примере Лизе нужно сначала перейти назад, на канал 1, после чего трижды выполнить переход вперёд, последовательно на каналы 6, 11, 16.

Линейные алгоритмы Разбор случаев

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

Порядок во всём#60129

Вася — очень порядочный мальчик, он любит порядок во всём.

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

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(2 \le n \le 3 \cdot 10^{5}\)) — количество чисел в тетрадке у Васи.

Следующие \(n\) строк содержат \(n\) чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие \(10^9\).

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

Примечание

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

Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число.

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

Задача на реализацию Разбор случаев

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

Фестиваль чисел#59883

В городе Летовецк "Фестиваль Чисел" отмечается всегда в день с магической датой. Дата называется магической, если день, номер месяца и две последние цифры года совпадают. Например, 01.01.01 - магическая дата.
По текущей дате, записанной в формате дд.мм.гг определите дату, когда будет отмечатся ближайший "Фестиваль чисел". То есть первую магическую дату, которая была бы не ранее текущей.

Формат входных данных
Программа получает на вход одну строку, которая содержит дату в формате дд.мм.гг (дд, мм, гг - числа, соответствующие реальным значениям дня, месяца и года).

Формат выходных данных
Программа должна вывести ближайшую дату "Фестиваля чисел" в формате дд.мм.гг.

Задачи на моделирование Разбор случаев

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

Весы#59831

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

Помогите учителю физики уравновесить весы или убедитесь, что это невозможно.

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

Формат выходных данных
Если уравновесить весы невозможно, выведите единственное число \(-1\).

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

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

Разбор случаев

✓ 29✗ 28500лёгкаяВойти и решать

Прямоугольный забег#57865

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

Центральная площадь Зожбурга представляет собой прямоугольник, разделенный на одинаковые единичные квадраты. Строки пронумерованы сверху вниз с единицы, столбцы слева направо с единицы. Каждый квадрат площади имеет координаты \(r\) и \(c\) — номер строки и столбца, соответственно.

На площади находится прямоугольный газон со сторонами, параллельными сторонам площади. Координаты левого верхнего углового квадрата газона \((R_L, C_L)\), координаты правого нижнего углового квадрата газона \((R_R, C_R)\). Вокруг газона оборудованы \(n\) дорожек для \(n\) бегунов. Дорожка \(i\) находится на расстоянии \(i\) от границы газона, на дорожке \(i\) находится бегун с номером \(i\). Бегун \(i\) стартует с квадрата с координатами \((r_i, c_i)\). Бегуны стартуют одновременно с одинаковой скоростью: через каждую секунду каждый спорстмен меняет текущий квадрат на своей дорожке на следующий квадрат на своей дорожке в направлении против часовой стрелки.

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

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

Формат входных данных
В первой строке входных данных находится число \(n\) (\(1 \le n \le 18\)) — количество бегунов. В следующей строке ввода даны шесть целых чисел \(R_L\), \(C_L\), \(R_R\), \(C_R\) (\(n + 1 \le R_L \le R_R \le 100 - n\), \(n + 1 \le C_L \le C_R \le 100 - n\)), \(R_p\) (\(R_L \le R_p \le R_R\)), \(C_p\) (\(C_L \le C_p \le C_R\)) — координаты левого верхнего квадрата газона, правого нижнего квадрата газона, координаты фотографа, соответственно. Гарантируется, что \(R_R - R_L + C_R - C_L\) делится на \(4\).

В следующих \(n\) строках даны два числа \(r_i\), \(c_i\) — стартовые координаты бегуна \(i\). Гарантируется, что стартовые координаты бегуна \(i\) находятся на дорожке \(i\), на каждой дорожке находится один бегун, дорожка \(i\) находится на расстоянии \(i\) от границы газона.

Формат выходных данных
Выведите единственное число \(t\) — через какое минимальное количество секунд \(t\) после старта забега фотограф сможет сделать красивую фотографию, или \(-1\), если фотографию сделать не получится.

Рисунок ко второму примеру.

Стартовое положение бегунов.

Положение бегунов через 3 секунды. Все бегуны находятся в строке \(R_p\), и фотограф делает красивое фото.

битмаски Задачи на моделирование Разбор случаев

✓ 1✗ 0—Войти и решать

Поле для крикета#55165

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

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

Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север - юг и восток - запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север - юг и восток - запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева. Оси этой системы координат, конечно, параллельны направлениям север - юг и восток - запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный - координаты (W, H), где W и H - длина и ширина парка соответственно.

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

Входные данные
Первая строка содержит три целых числа, N, W и H, разделённых пробелами: N - число деревьев в парке, W и H - длина и ширина парка соответственно.

Следующие N строк описывают координаты деревьев в парке. Каждая строка содержит два целых числа xi и yi, разделённых пробелом и представляющих собой координаты i-го дерева. Все деревья имеют различные координаты.

Ограничения: 1 <= N <= 100, 1 <= W, H <= 10 000, 0 <= x_i <= W, 0 <= y_i <= H.

Выходные данные
Вывести через пробел три целых числа, P, Q и L, где (P, Q) - координаты юго-западного угла поля для крикета, L - длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.

Бинарный поиск по ответу Разбор случаев

✓ 1✗ 0—Войти и решать

Диалог компьютеров#55132

Три компьютера соединены сетью. Один из них - сервер, два других - клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение - второму.

Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать полное имя файла). Однако клиенты вынуждены общаться очень ограниченным способом. Они по очереди посылают сообщения друг другу, но могут сказать только, что не знают полного имени файла. Если клиент не знает полного имени выбранного файла, он может послать другому клиенту сообщение, говорящее: "Я не знаю полного имени файла". Клиенты чередуются, посылая только это сообщение туда и обратно. Так продолжается до тех пор, пока один из клиентов не узнает полное имя файла, или они не решат закончить диалог. Клиент, получивший первую часть полного имени файла, всегда ждёт, что второй клиент пошлёт первое сообщение.

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

Входные данные
В первой строке находятся два целых числа, N и M, разделённые пробелом: N - число файлов на сервере, M - число сообщений, посланных клиентами, пытающимися определить полное имя файла.

Каждая из следующих N строк содержит одно полное имя файла. Полное имя файла дано в стиле, аналогичном формату 8.3 MS-DOS. Каждое полное имя представлено в форме имя.расширение, где и имя, и расширение состоит только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трёх символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.

Каждое полное имя файла появляется во входном файле не более одного раза.

1 <= N <= 1000, 1 <= M <= 100.

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

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

Задачи на моделирование Разбор случаев

✓ 1✗ 0—Войти и решать

Витя и Денис играют в игру "Быки и коровы"#54490

Витя и Денис играли в игру «Быки и коровы». Витя загадал четырёхзначное число с неповторяющимися цифрами, а Денис пытался это число угадать. Для этого он предлагал свои четырёхзначные числа (тоже с неповторяющимися цифрами), а Витя про каждое из них сообщал, сколько в нём «быков» (т. е. цифр, которые не только присутствуют и в Витином числе, и в числе Дениса, но даже стоят на одних и тех же местах) и «коров» (цифр, которые присутствуют в обоих числах, но стоят на разных местах). У них осталась запись партии (последовательность тестовых чисел и ответов на них), но задуманное число утратилось. Восстановите задуманное число.

Входные данные
Вводится сначала число N—количество четырёхзначных чисел,названных Денисом в одной партии (N < 100).Затем вводятся
N строк, по три числа в каждой. Первое — четырёхзначное число, названное Денисом (оно не начинается с нуля), второе — количество «быков», третье — количество «коров».

Выходные данные
Требуется вывести одно четырёхзначное число, задуманное Витей. Это число не начинается с 0.

Гарантируется, что ответ в задаче существует и является единственным

Простые задачи на перебор Разбор случаев

✓ 2✗ 0—Войти и решать

Сложное уравнение#53645

Решить в целых числах уравнение ( ax + b ) : ( cx + d ) = 0.

Входные данные
Вводятся 4 числа: a, b, c и d; c и d не равны нулю одновременно.

Выходные данные
Необходимо вывести все целочисленные решения, если их число конечно, “NO” (без кавычек), если целочисленных решений нет, и “INF” (без кавычек), если их бесконечно много.

Вывод формулы Разбор случаев

✓ 2✗ 0—Войти и решать

Уравнение#53644

Решить в целых числах уравнение ax + b = 0.

Входные данные
Вводятся 2 целых числа: a и b.

Выходные данные
Необходимо вывести все решения, если их число конечно, “NO” (без кавычек), если решений нет, и “INF” (без кавычек), если решений бесконечно много.

Разбор случаев

✓ 5✗ 1—Войти и решать