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

Электричка#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—Войти и решать

Прямоугольный забег#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—Войти и решать

Турнир ФХЛ#50446

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

В этом году в финал вышли команды <<Капибары>> и <<Бурундучки>>. Петя и Вася очень любят хоккей, но во время турнира они были на сборах по информатике. Теперь они решили просмотреть все матчи финального турнира в записи, скачав их с официального сайта. Зайдя на сайт, они обнаружили, что в этом году финальный турнир ФХЛ состоял из \(k\) матчей. Скачав все видеозаписи, ребята начали их смотреть, но неожиданно поняли, что могут предсказать итог турнира, не досмотрев все матчи. Более того, они заметили, что про некоторые матчи они понимают, кто их выиграет, даже не начав смотреть запись.

Например, пусть \(n = 3\) и \(k = 4\). Петя и Вася сразу могут сделать вывод, что турнир закончится со счетом по матчам \(3:1\) или \(1:3\), ведь всего будет сыграно 4 игры. Пусть первый матч закончился победой команды <<Капибары>>, счет стал \(1:0\), второй матч также закончился победой команды <<Капибары>>, счет стал \(2:0\). Теперь ребята точно знают, что победителем турнира станет команда <<Капибары>>, ведь если бы турнир выиграла команда <<Бурундучки>>, то финальный счет был бы \(2:3\) и всего было бы сыграно 5 игр. Более того, команда <<Бурундучки>> гарантированно выиграет третий матч, иначе окончательный счет был бы \(3:0\), а команда <<Капибары>> "— четвертый матч.

По заданным \(n\), \(k\) и результатам игр определите, после какой игры Петя и Вася поймут, какая команда станет победителем турнира, а также про каждый матч определите, знают ли ребята победителя этого матча до того, как посмотрят его.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 100\), \(n \le k \le 2n-1\)). Вторая строка ввода содержит \(k\) целых чисел: \(i\)-е из них равно 1, если \(i\)-й матч выиграла команда <<Капибары>>, либо 2, если \(i\)-й матч выиграла команда <<Бурундучки>>.

Гарантируется, что по итогам турнира одна из команд выиграла ровно \(n\) матчей, причем ни одна из команд не выигрывает \(n\) матчей до того, как будут сыграны все \(k\) матчей, описанных во входных данных.

Формат выходных данных
Выведите две строки. Первая строка должна содержать одно число \(z\) (\(1 \le z \le k\)) "— номер матча, после которого ребята могут однозначно определить победителя турнира.

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

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

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

Номера по диагонали#50398

Пронумеруем клетки прямоугольной таблицы с \(r\) строками и \(c\) столбцами, начиная с левого верхнего угла. Нумерацию будем вести по диагоналям, идущим справа-сверху налево-вниз, клетки одной диагонали будем нумеровать сверху вниз.

Например, для таблицы \(3 \times 5\) клетки будут пронумерованы следующим образом:

1	2	4	7	10
3	5	8	11	13
6	9	12	14	15

Задано \(q\) номеров клеток. Для каждого номера найдите, в какой клетке он находится.

Формат входных данных
Первая строка ввода содержит три целых числа: \(r\), \(c\) и \(q\) (\(1 \le r, c \le 10^9\), \(1 \le q \le 100\)).

Вторая строка содержит \(q\) целых чисел \(1 \le n_1 < n_2 < \ldots < n_q \le r\cdot c\).

Формат выходных данных
Выведите \(q\) строк. Для каждого числа \(n_i\) выведите два числа: номер строки и номер столбца, где находится соответствующая клетка. Строки нумеруются с 1 сверху вниз. Столбцы нумеруются с 1 слева направо.

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

✓ 3✗ 7—Войти и решать

Горнолыжный курорт#43133

Саша Белый недавно устроился подрабатывать на горнолыжный курорт недалеко от Аши. Первым делом ему поручили установить ограждения для лыжной трассы.
Саше дали n ограждений, каждое длиной a_i. Любые два последовательных ограждения скреплены друг с другом, но при этом могут произвольно поворачиваться друг относительно друга.
Саша хочет сделать трассу интересной: по его мнению, трасса должна быть в форме спирали (ограждение под номером i +1 должно быть повернуто на 90 градусов по часовой стрелке относительно ограждения под номером i; при этом никакие ограждения, кроме смежных, не должны касаться друг друга и пересекаться).
К сожалению, не из любых наборов ограждений можно сложить спираль. Помогите Саше для заданного набора определить, возможно ли из него составить спираль.
Входные данные
В первой строке входных данных записано целое число n — количество ограждений (1 <= n <= 10⁵). Во второй строке через пробел заданы n целых чисел a_i — длина i-го ограждения (1 <= a_i <=10⁹).
Выходные данные
Выведите YES, если возможно из данных ограждений сложить спираль, или NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 3 5	YES
2	6 5 7 6 8 6 10	NO
3	9 1 1 2 2 6 2 2 1 1	YES

Замечание
Обратите внимание на третий пример, спираль может иметь два центра, главное, чтобы ограждения не пересекались. Иллюстрация к третьему примеру:

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

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

Лекция по товароведению#43126

Гена Букин приехал в Златоуст провести управленческую лекцию в обувном магазине. Зайдя в магазин, Гена увидел полнейший бардак: коробки обуви хаотично валялись в куче посреди зала.
Конечно же, его эта ситуация не устроила, и он решил, что нужно показать, как правильно расставлять коробки. Он заметил, что в магазине есть коробки только двух типов: красные имеют высоту x сантиметров, их a штук; синие имеют высоту y сантиметров, их b штук.
Гена хочет взять несколько коробок из кучи и составить из них башню. Однако из каких-то личных представлений об эстетике Гена не ставит две коробки одинакового цвета друг на друга, в башне он может только чередовать цвета.
Попробовав все возможные способы построения башни, Гена запомнил, сколько различных высот конструкции он смог получить. А сможете ли вы определить, сколько существует различных высот h > 0, что можно построить башню из коробок высотой h, удовлетворяя требованиям о чередовании цветов?
Входные данные
В единственной строке через пробел вводятся 4 целых числа x, y, a, b — высота красной коробки, высота синей коробки, количество красных коробок, количество синих коробок (1<= x,y,a,b <=10⁹).
Выходные данные
Выведите одно число — количество различных высот башен из коробок.

Примеры

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

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

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