Информатика

Определите наибольшее целое значение A, при котором найдутся такие целые неотрицательные x и y, при которых значение выражения ложно?
 

Банк «Кисловодск» переходит на новый вид банковских карт. Для этого производятся одинаковые заготовки, на которых есть специальное место для идентификации клиента. Изначально на этом месте записывается кодовое число X. В банке с помощью специального прибора можно стирать некоторые цифры числа X. Оставшиеся цифры, будучи записанными подряд, должны образовывать номер счета клиента. Например, при X = 12013456789 номера счетов 5, 12, 17 или 12013456789 получить можно, а номера 22 или 71 получить нельзя.

Способ распределения номеров счетов в банке очень прост. Счетам присваиваются последовательно номера 1, 2, … Очевидно, что при таком способе в какой-то момент впервые найдется номер счета N, который нельзя будет получить из цифр X указанным выше способом. Руководство банка хочет знать значение N.

Напишите программу, которая находила бы N по заданному X.

Формат входных данных
Вводится натуральное число X без ведущих нулей (1 ≤ X ≤ 101000). 

Формат выходных данных
Выведите искомое N без ведущих нулей.

Определите наибольшее целое значение A, при котором найдутся такие целые неотрицательные x и y, при которых значение выражения ложно?
 

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч {1} либо увеличить количество камней в куче в два раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней. 
Игра завершается в тот момент когда суммарное количество камней в кучах становится не менее {2}. 
Победителем считается игрок, сделавший последний ход, т.е. первым получивший суммарно в кучах {2} или больше камней.
В начальный момент в первой куче было {3} камней, во второй - S камней; 1 <= S <= {4}.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. 

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

Задание 20
Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия: 
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. 
 Найденные значения запишите в порядке возрастания.

Задание 21
Найдите минимальное значение S, при котором одновременно выполняются два условия: 
- У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом, при любой игре Пети;
- У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. 
 Если найдено несколько значений S, в ответе укажите наименьшее из них.


Ответ на каждое задание вводите в отдельной строке. Несколько значений в одной строке разделяйте одним пробелом.

Вам дан массив A из N чисел. Найдите количество различных пар (i, j), таких, что j>=i и A[i] = A[j].

Формат входных данных
Первая строка входных данных содержит количество тестовых случаев T. Каждый тестовый случай состоит из двух строк, первая строка - число N, за ней следует строка, состоящая из N целых чисел, которые являются элементами массива A.

Ограничения
1 <= T <= 10
1 <= N <= 106 
-106 <= A[i] <= 106
0 <= i < N

Формат выходных данных
Для каждого тестового случая выведите количество различных пар.
 

Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательностей R1 и R2 начинается соответственно от точек A и D, а R3 и R4 - от точек B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников.
Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD.
Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника.
 

На физкультуре школьники 10-А класса играют в баскетбол. В классе учится \(n\) школьников, которые построились в ряд. Учитель физкультуры разделил их на две команды следующим образом: в первую команду пошли школьники, которые стоят на нечетных местах: первом, третьем, пятом, и т. д. Школьники, которые стоят на четных местах: втором, четвертом, шестом, и т. д. составили вторую команду.

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

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

Запасной же игрок, которые провел к этому моменту на поле меньше всего минут, выходит на поле. Если таких игроков несколько, на поле выходит игрок с минимальным номером в исходном построении.

Учителя заинтересовал вопрос, кто же будет на поле после \(m\)-й смены игроков. Помогите ему выяснить это.

Например, пусть исходно шесть учеников построились в следующем порядке: Иванов, Петров, Сидоров, Андреев, Казаков, Сергеев. Команды будут сформированы следующим образом. Первая команда: Иванов, Сидоров, Казаков. Вторая команда: Петров, Андреев, Сергеев. Пусть на поле одновременно находятся 2 игрока, тогда исходно на поле выйдут Иванов и Сидоров от первой команды, Петров и Андреев от второй.

После первой минуты игры Сидоров и Андреев пойдут на скамейку запасных, а на поле появятся Казаков и Сергеев. После второй минуты отдыхать пойдут Иванов и Петров, а Сидоров и Андреев вернутся на поле. Наконец, после третьей минуты Казаков и Сергеев снова пойдут отдыхать, а на площадке появятся Сидоров и Андреев. Таким образом после трех смен на поле будут (в алфавитном порядке) Андреев, Иванов, Петров и Сидоров.

Формат входных данных
Первая строка содержит три целых числа: \(n\), \(m\) и \(p\) (\(2p \le n \le 50\), \(1 \le p \le 10\), \(0 \le m \le 100\)). Следующие с \(n\) строк содержат по одной фамилии — игроки в том порядке, в котором они исходно построились Каждая фамилия представляет собой непустую последовательность букв латинского алфавита не длиннее 50. Все фамилии различны.

Формат выходных данных
Выведите в алфавитном порядке фамилии игроков, которые будут на поле после \(m\) смен составов. Разделяйте фамилии пробелом.

Задано число \(n\). Требуется найти число от 1 до \(n\), включительно, которое имеет максимальное число положительных целых делителей.

Например, если \(n = 20\), то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6 и 12.

Формат входных данных
На вход подается одно число \(n\) (\(1 \le n \le 100\,000\))

Формат выходных данных
Выведите на первой строке число от 1 до \(n\), включительно, которое имеет максимальное число делителей. На второй строке выведите число его делителей.

Если есть несколько чисел от 1 до \(n\) с максимальным числом делителей, выведите любое из них.

Задано четыре числа: \(a\), \(b\), \(c\) и \(d\). Требуется разбить их на две пары, чтобы сумма произведений в этих парах была максимальна.

Например, если заданы числа 2, 3, 4 и 5, то оптимально разбить их на пары \((2, 3)\) и \((4, 5)\), в этом случае искомая сумма равна \(2 \times 3 + 4 \times 5 = 26\).

Формат входных данных
На вход подаются четыре числа: \(a\), \(b\), \(c\) и \(d\). Все числа по модулю не превышают 1000.

Формат выходных данных
Выведите искомую максимальную сумму.

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

Определите в 27-ричной записи числа количество цифр с числовым значением, превышающим 9:

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

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M (1 \le N, M \le 100, N \times M \le 100))\), в одной клетке которого находится клад, в K
 клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

Формат входных данных
Первая строка содержит 2 числа N<=100 и M<=100, задающие размеры лабиринта. Далее следует описание лабиринта: N
 строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В (N+2)-й строке находится число \(K (1 \le K \le N \times M)\) - количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа \(x_i\) и \(y_i\), означающие, что i-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце \((1 \le x_i \le N, 1\le y_i \le M)\). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	4 1 1 2 1 2 2 3 2 3 3
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

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

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

Формат входных данных
Вам даны 8 целых чисел - \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\), где \((x_1, y_1)\) - координаты левого нижнего угла рисунка Пети, \((x_2, y_2)\) - координаты правого верхнего угла рисунка. Аналогично, \((x_3, y_3)\) - координаты левого нижнего угла вырезанного Васей прямоугольника, \((x_4, y_4)\) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (\(x_1 < x_2\), \(y_1 < y_2\) и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит \(10^4\).

Формат выходных данных
Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примечание

В городе Н. олимпиада по информатике состоит из двух туров, каждый из которых оценивается из 400 баллов. Для удобства все её участники занумерованы числами от 1 до \(N\).

Сразу после проведения олимпиады курьер принёс жюри пренеприятнейшее известие: <<сверху>> пришло указание о том, что некто Вася, выступавший в олимпиаде под номером 1, должен занять как можно более высокое место, то есть как можно меньше участников должны набрать по сумме двух туров больше баллов, чем Вася. При этом места, занятые школьниками в каждом из туров в отдельности, уже опубликованы, и их менять нельзя. Для каждого тура дан список номеров участников в порядке занятого места — перестановка чисел от 1 до \(N\). Теперь работа жюри заключается в том, чтобы расставить целые баллы от 1 до 400 каждому участнику в первом и втором турах таким образом, чтобы в итоговой таблице Вася занял как можно более высокое место, а места участников в каждом из туров не изменились. При этом никакие два участника не должны получить в одном туре одинаковые баллы.

Ваша задача — проделать за жюри такую работу.

Считается, что участник по сумме двух туров занял место \(A\), если ровно \(A-1\) участников набрали по сумме двух туров строго больше баллов.

Формат входных данных
Сначала вводится целое число \(N\) (\(1 \le N \le 200\)) — количество участников олимпиады. Во второй строке перечислены номера участников в порядке занятых мест в первом туре (от первого места до \(N\)-го). В третьей строке в таком же формате следует описание второго тура. Номера участников во второй и третьей строках разделены пробелами.

Формат выходных данных
Сначала выведите \(N\) целых чисел от 1 до 400, соответствующих расстановке баллов участникам первого тура, где \(i\)-ое число — балл в первом туре участника, занявшего на нём \(i\)-е место, затем аналогично \(N\) целых чисел, соответствующих расстановке баллов во втором туре. Числа разделяйте пробелами или переводами строки. Никакие два участника не должны получить одинаковые баллы в одном и том же туре. Если существует несколько способов расставить баллы требуемым образом, выведите любой из них.

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

В этой задаче Вася готовится к олимпиаде. Учитель дал ему \(N\) (\(1 \le N \le 100\)) задач для тренировки. Для каждой из этих задач известно, каким умением \(a_i\) нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения \(i\)-й задачи Васино умение увеличивается на число \(b_i\).

Исходное умение Васи равно \(A\). Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Формат входных данных
Сначала вводятся два целых числа \(N\), \(A\) (\(1 \le N \le 100\), \(0 \le A \le 100\)) — количество задач и исходное умение. Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(1 \le a_i \le 100\), \(1 \le b_i \le 100\)) — соответственно сколько умения нужно для решения \(i\)-й задачи и сколько умения прибавится после её решения.

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

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

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

Код Рудольф гуляет вдоль улицы, от фонаря с номером a до фонаря с номером b. Полосатый кот Ихмиллион прогуливается от фонаря с номером c до фонаря с номером d. Определите, количество фонарных столбов, мимо которых проходя оба кота.



Входные данные
Вводятся четыре числа в одной строке через пробел: a, b, c, d (0 < a, b, c, d <= 100). 

Выходные данные
Выведите ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 8 6 2	2	Рудольф прогуливается от фонаря с номером 5 до  8-го фонаря и обратно, а Ихмиллион со 6-го по 2-й и обратно. Одновременно оба кота прогуливаются мимо фонарей с номерами 5 и 6. Всего фонарей два.
2	5 3 7 9	0	Нет общих фонарей, мимо которых прогуливаются оба кота.

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

Каждый ход устроен следующим образом.

1. Компьютер называет целое число \(k > 0\).

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

3. Компьютер называет координаты \((i, j)\) произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки \((i, j)\) существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке \((i, j)\), вы можете сообщить компьютеру, что игра завершена, и вы победили.

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

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

Формат входных данных
В единственной строке ввода даны четыре целых числа \(n\), \(m\), \(r\) и \(c\) — размеры доски и координаты изначального расположения фишки (\(1 \le r \le n \le 1000\); \(1 \le c \le m \le 1000\)).

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

В следующих \(n \cdot m\) строках даны ходы, которые последовательно собирается сделать компьютер. Описание \(t\)-го хода задается тремя целыми числами \(k_t\), \(i_t\) и \(j_t\) — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить (\(1 \le k_t \le 10^9\); \(1 \le i_t \le n\); \(1 \le j_t \le m\)).

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

Формат выходных данных
Выведите одно целое число от \(1\) до \(n \cdot m\) — номер хода, после которого вы сообщите компьютеру о своей победе.

 

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

Финальный турнир Флатландской Хоккейной Лиги (ФХЛ) играется между двумя командами-лидерами сезона. Команды играют матчи между собой до тех пор, пока одна из команд не выиграет ровно \(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\).

Сеня выбирает себе подарки на новый год. Он знает, что Дед Мороз купит ему ровно два подарка: один якобы от мамы, а другой якобы от папы.

В магазине, где Дед Мороз будет покупать подарки, продаётся \(n\) подарков, про каждый подарок известна его цена: цена \(i\)-го подарка равна \(a_i\) рублей. Сеня знает, что Дед Мороз может потратить на покупку его подарков не больше \(x\) рублей. Разумеется, он хочет получить как можно более дорогие подарки. Таким образом, он хочет выбрать два различных подарка с максимальной суммарной ценой, но при этом она не должна превышать \(x\).

Помогите Сене выбрать себе подарки.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(x\) (\(2 \le n \le 100\,000\), \(2 \le x \le 10^9\)). Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)). Гарантируется, что существует два подарка с суммарной ценой не больше \(x\).

Формат выходных данных
Выведите одно целое число: максимальную суммарную цену двух различных подарков, не превышающую \(x\).