Информатика

Двое играют в такую игру: перед ними лежит шоколадка размера NxM. За ход можно разломить имеющийся кусок шоколадки вдоль одной из сторон на 2 "непустых".

 

Однако, нельзя разламывать куски размером не больше, чем 1k (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части). Таким образом, нельзя разламывать куски размером 11, 12, , 1k, а остальные куски разламывать можно.

 

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

 

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

Вводятся целые числа 0 < N, M, K <= 100.

 

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

Вывести 1 или 2 - номер игрока, который выиграет при правильной игре.

Ввод	Вывод
1 1 1	2
2 2 1	1

 

Верс нужно подготовить рапорт о последнем боевом вылете. Она уже сочинила в голове текст, осталось лишь его записать. Рапорт будет состоять из двух частей: первая будет содержать n слов, i-е из которых состоит из ai букв, вторая — m слов, j-е из которых состоит из bj букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.

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

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

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

   

Примеры

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

Примечание

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить такую максимальную сумму элементов пары, чтобы суммы элементов пары и их индексов были кратны 3. Если такой суммы не найдется, вывести «–1». Нумерация элементов начинается с 1.
Напишите эффективную по памяти и времени программу.

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

В первой строке входных данных задаётся количество чисел N (1 < N <=100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.

Выходные данные 
В качестве результата программа должна вывести одно число: максимальную сумму пары кратную трём с суммой индексов кратной трём или «–1», если такой пары не нашлось.

 

Примеры

№	Входные данные	Выходные данные	Комментарий
1	10  1 2 3 4 5 6 7 8 9 10	18	найденная пара: (a[8]=8; a[10]=10)
2	23  36 16 15 15 17 16 14 15 47 22 27 29 35 23 39 29 15  25 16 35 28 45 26	75	найденная пара: (a[9]=47; a[21]=28)

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

В одной из деревень Центрального района решили построить новую школу, но никак не могут выбрать, в какой именно. Решили сделать так: подсчитать для каждой деревни суммарное расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне, и выбрать место, для которого эта сумма будет минимальной. В распоряжении администрации есть карта дорог Центрального района. Напишите программу, которая поможет выбрать место для школы. Если какой-то населенный пункт не имеет связи с другим населенным пунктом, где предполагается разместить школу, считайте, что доставка каждого ученика вертолётом "стоит" 10000 единиц расстояния.

 

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

В первой строке вводится количество деревень N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог: положительное число означает расстояние между деревнями, ноль говорит о том, что дороги нет. В последней строке вводится N чисел - количество школьников в каждой деревне.

 

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

Программа должна вывести два числа: сначала номер деревни, где нужно построить школу, а затем (через пробел) – общее расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне.

Ввод	Вывод
4 0 11 8 4 11 0 2 5 8 2 0 13 4 5 13 0 15 26 30 12	2 255

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

 

1 P R I 

2 R A N 

3 O M G 

4 G M 
 

а затем, если выбрать порядок строк 3, 1, 2, 4, получают закодированное сообщение OMGPRIRANGM.

 

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

 

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

Входные данные содержат: в первой строке высоту прямоугольника H (2 ≤ H ≤ 10), во второй – порядок прочтения строк (числа записаны через пробел), в третьей – закодированное сообщение, длина которого составляет от 1 до 200 символов. Закодированное сообщение состоит из заглавных и строчных латинских букв  и цифр.

 

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

В выходные данные записывается декодированное сообщение.

Ввод	Вывод
4 3 1 2 4 OMGPRIRANGM	PROGRAMMING

 

На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «abacaba», а мать — «bbccaa», то их ребенок может носить имена «a», «bba», «bcaa», но не может носить имена «aaa», «ab» или «bbc». Возможно, что имя ребенка совпадает с именем отца и/или матери, если оно может быть получено из имени другого родителя удалением нескольких (возможно, ни одной) букв.

 

Пусть отец по имени X и мать по имени Y выбирают имя своему новорожденному ребенку. Так как в таукитянских школах учеников часто вызывают к доске в лексикографическом порядке имен учеников, то есть в порядке следования имен в словаре, то они хотят выбрать своему ребенку такое имя, чтобы оно лексикографически следовало как можно позже.

 

- Формально, строка S лексикографически больше строки T, если выполняется одно из двух условий: строка T получается из S удалением одной или более букв с конца строки S;

- первые (i - 1) символов строк T и S не различаются, а буква в i-й позиции строки T следует в алфавите раньше буквы в i-й позиции строки S.

Требуется написать программу, которая по именам отца и матери находит лексикографически наибольшее имя для их ребенка.

 

Первая строка входного файла содержит X — имя отца. Вторая строка входного файла содержит Y — имя матери. Каждое имя состоит из строчных букв латинского алфавита, включает хотя бы одну букву и имеет длину не более 105 букв.

 

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

Ввод	Вывод
abcabca abcda	ca
ccba accbbaa	ccba

На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

 

Сначала вводится одно целое число N (0<N<=10000).

 

В каждой из следующих N строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.

 

Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.

 

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

 

Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все N касс.
 

Ввод	Вывод
3 1 0 0 23 0 0 12 0 0 12 0 0 22 0 0 2 0 0	7200
2 9 30 0 14 0 0 14 15 0 21 0 0	0
2 14 0 0 18 0 0 10 0 0 14 0 1	1

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

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

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

Вводится одно число N: 1 ≤ N ≤ 2*10⁹

Выводится одно число – количество секунд.

Ввод	Ввод
2	2

(с) Ковешников М., 2018 г.

Жил дотер по имени Ануфрий. И вдруг случилось так, что его заботливая мама отрубила ему интернет. И как назло на компьютере Ануфрия была всего одна офлайновая игра – Minecraft.

 

Во время увлекатейнешего разрушения своего разума мальчик не знал что в этой версии игры надо думать о еде. И тут ему пришла интереснейшая мысль насчет своей еды: так как у него был только торт(как ни странно он круглый), каким образом он может получить максимальное количество кусков торта при разрезаний n. Но так как, как типичный игрок в Dota 2, Ануфрий не отличался сообразительностью. HELP HIM!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

Гарантируется, что меч, которым он режет торт, прямой. Так как Ануфрий не учит математику, а играет в доту, то не гарантируется n – натуральное(если такое произошло то выведите смайлик «

 

-1»).

 

На вход подается n.

 

На выходе вы должны вывести ответ на задачу)))

Ввод	Вывод
-2	-1
0	0
3	7

 

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.

 

Входные данные: 
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке  - N чисел P1, P2, ..., PN;
- в четвертой строке - число M;
- в пятой строке - M чисел Q1, Q2, ..., QM.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

 

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

Если они не могут рассчитаться, выведите строку Impossible.

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Программа должна работать быстрее, чем за линейный поиск
 

Одно целое число N (1 <= N <= 10⁹).

 

Выведите одно целое число - N-й элемент последовательности.
 

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

Маленькому Арсению на кружке по системам счисления задали следующую задачу: перевести число X в системе счисления s1 в систему счисления s2. Недолго думая, он позвал на помощь своего лучшего друга Добрыню, который славился тем, что замечательно умел считать до 10 на пальцах. После нескольких бессонных ночей ребята общими усилиями справились с задачей.

 

Однако, на следующем занятии Арсению задали похожую задачу, где X, к сожалению, превышало 10. Тогда ребята решили обратиться в Летнюю Компьютерную Школу с просьбой написать универсальную программу, которая решает задачу для любых X, s1 и s2. Ваша цель – выполнить просьбу Арсения и Добрыни.

 

Во входных данных вашей программе дается 3 числа: исходное число X, основания систем счисления s1 и s2 (\(2  <=  s1,\ s2  <=  10\)). Число X в десятичной системе счисления не превышает \(2 \cdot 10^9\).

 

В выходных данных должно находиться одно число, равное числу X в системе счисления s2, или -1, если входные данные некорректны.

 

 

Примеры

№	Входные данные	Выходные данные
1	101 2 10	5
2	200 2 10	-1

 

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

 

В первой строке записано два числа n и m (1 <= n, m <= 10⁶) - количество вершин в графе и количество производимых добавлений и запросов. Далее следует m строк с описанием добавления или запроса. Каждая строка состоит из двух или четырех чисел. Первое из чисел обозначает код операции. Если первое число 1, то за ним следует еще три числа x, y, w. Это означает, что в граф добавляется ребро из вершины x в вершину y веса w. (1 <= x < y <= n, 1 <= w <= 10³). Кратные ребра допустимы. Если первое число 2, то за ним следует ровно одно число x. Это означает, что необходимо ответить на вопрос, какова сумма ребер в компоненте связности, которой принадлежит вершина x (1 <= x <= n).

 

Для каждой операции с кодом 2 выведите ответ на поставленную задачу. Ответ на каждый запрос выводите на отдельной строке.

 

Примеры

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

На плоскости задано N прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.

 

В первой строке входного файла указано число N (0≤N≤1500). В следующих N строках заданы по 4 целых числа x1, y1, x2, y2 — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (0≤x1≤x2≤10⁹, 0≤y1≤y2≤10⁹). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

 

В выходной файл выведите единственное число — ответ на задачу.
 

Ввод	Вывод
3 1 1 3 5 5 2 7 4 2 4 6 7	23
2 0 0 2 2 1 3 2 4	5

На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (M — натуральное число), содержащее наименьшее число отрезков.

 

В первой строке указана константа M (\(1<=M<=5000\)). В каждой последующей строке записана пара чисел Li и Ri (\(|L_i|,|R_i| < 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.

 

В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка \([0; M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка \([0; M]\) исходным множеством отрезков \([L_i, R_i]\) невозможно, то следует вывести единственную фразу “No solution”.

 

Примеры

№	Входные данные	Выходные данные
1	1 -1 0 -5 -3 2 5 0 0	No solution
2	1 -1 0 0 1 0 0	1 0 1

На автобусных билетах указываются их номера. Номера всех билетов всегда записываются при помощи одного и того же количества цифр, при этом число используемых цифр чётно. При необходимости числа дополняются ведущими нулями. К примеру, если для записи используют 4 цифры, то 514 будет записано как 0514. Билеты отпечатаны на лентах, билеты на каждой ленте нумеруются подряд числами от 00...01 до 99...99.

Счастливым считается тот билет, у которого сумма цифр первой половины равна сумме цифр второй половины, например, билеты 1001 и 123051 счастливые, а 7778 и 39 – нет. Сегодня Дима зашел в автобус, и кондуктор выдал ему билет с номером N. Поскольку Диме ехать достаточно долго, а заняться чем-нибудь надо, он стал думать, какой номер будет иметь следующий счастливый билет, выданный из той же ленты, что и Димин билет. Если в текущей ленте не осталось счастливых билетов, Диму интересует номер минимального счастливого билета из новой ленты.

В первой и единственной строке входного файла содержится номер Диминого билета N, записанный с ведущими нулями. Количество цифр в записи числа N не превосходит 100 000 и чётно.

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

Ввод	Вывод	Примечание
0514	0523	Диме был выдан счастливый билет (сумма цифр обеих половин равна 5), но Диму не интересует номер его билета, его интересует номер следующего счастливого билета.