Задачи олимпиады "Личное первенство по программированию среди школьников и студентов ИКИТ СФУ"

Задача A. Ближайшее нечётное

Дано целое четное число X. Требуется вывести ближайшее для него нечётное число. Если вариантов несколько, то вывести то, которое короче в десятичной записи. Если вариантов все-равно несколько, вывести то, которое меньше.

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

Входной файл INPUT.TXT содержит целое четное число X (|X| ≤ 10⁶).

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

В выходной файл OUTPUT.TXT выведите ближайшее нечётное число, удовлетворяющее условию задачи.

Примеры

Примечание

Минус также считается символом десятичной записи.

Задача B. Бобры-Зомби

Вы сидите на вершине дерева с небольшой командой выживших в центре бобро-зомби апокалипсиса. На земле вас окружили N бобров-зомби, которые вот-вот сточат ствол дерева! У каждого бобра-зомби есть свой размер S_i, выраженный натуральным числом.

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

Срочно посчитайте, сколькими способами можно создать доброго Бобротрона, стравливая двух бобров-зомби!

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

Первая строка входного файла INPUT.TXT содержит целое число N – количество бобров-зомби (2 ≤ N ≤ 200 000).

Вторая строка содержит N целых чисел S_i, разделённых пробелами – размеры бобров-зомби (1 ≤ S_i ≤ 200 000).

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

В выходной файл OUTPUT.TXT выведите целое число – количество пар бобров, которые смогут образовать доброго Бобротрона.

Примеры

Примечание

В первом примере подойдёт любая пара бобров.

Во втором примере подойдёт лишь пара бобров с размерами 2 и 8.

Задача C. CSV Reader

CSV (от англ. Comma-Separated Values – значения, разделённые запятыми) – текстовый формат, предназначенный для представления табличных данных.

Описание формата:

Каждая строка файла – это одна строка таблицы. Строки не могут быть пустыми. Каждая строка заканчивается символом перевода строки.

aaa,bbb,ccc
xxx,yyy,zzz

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

aaa,a and b,bbb
aaa„ccc,ddd

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

aaa,"bbb","c , c"

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

"aaa","a ""and"" b"

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

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

Входной файл INPUT.TXT имеет CSV формат и содержит не более 100 непустых строк. Каждая строка содержит не более 100 символов. Допустимые символы: строчные и прописные английские буквы, цифры, знаки препинания (точка, запятая, вопросительный и восклицательный знак, двоеточие, точка с запятой, двойные кавычки) и пробелы.

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

В выходной файл OUTPUT.TXT выведите информацию из файла, отформатированную по следующим правилам:

• каждая строка содержит одинаковое количество ячеек. Строки могут дополняться справа необходимым количеством пустых ячеек;
• ширина каждого столбца подбирается автоматически по ширине самого длинного значения;
• остальные значения выравниваются по левому краю и дополняются справа необходимым количеством пробелов;
• разделитель между ячейками в строке – вертикальная черта «|».

Пример

a,b,c,d,e
"aa",,"cc",dd
"a,a,a","b,b","c"
"a,""a"",""","a and ""b""",,a"b

a      |b        |c |d  |e
aa     |         |cc|dd | 
a,a,a  |b,b      |c |   | 
a,"a","|a and "b"|  |a"b| 

Задача D. Суперпозиция

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

Точнее, пока лишь он предоставил схему этого аппарата. На схеме присутствуют N точек и M каналов. Каждый канал соединяет ровно две точки и имеет заряд: «+» или «-». На некоторых каналах заряд находится в суперпозиции «?», то есть пока неизвестен.

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

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

Простой цикл является отрицательным, если произведение зарядов каналов этого цикла даёт знак «-».

Поликарп понимает, что ответ может быть слишком большим, поэтому просит вывести его остаток от деления на число 111111111111111111 ((10¹⁸−1)/9).

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

Первая строка входного файла INPUT.TXT содержит два целых числа N и M – количество точек и каналов на схеме соответственно (1 ≤ N, M ≤ 2∙10⁵).

Следующие M строк содержат описания каналов в виде пары целых чисел a_i и b_i (1 ≤ a_i, b_i ≤ N, a_i≠b_i), обозначающих номера точек, которые соединяет этот канал, а также символ, означающий заряд этого канала: «+», «-» или «?».

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

В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.

Примеры

Задача E. Системы счисления

Вам необходимо вывести все основания систем счисления, в которых запись числа A оканчивается на десятичную запись числа B.

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

Входной файл INPUT.TXT содержит целые числа A и B (1 ≤ A ≤ 10⁹, 10 ≤ B <100), записанные в десятичной системе счисления.

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

В выходной файл OUTPUT.TXT в произвольном порядке выведите все основания систем счисления, в которых запись числа A оканчивается на десятичную запись числа B. Если таких систем нет, выведите −1.

Пример

Задача F. Раздел империи

Короли прошлого создали великую империю, в которой было N городов, и соединили их M двусторонними дорогами таким образом, что между любыми двумя городами существует путь, возможно через другие города. Одну и ту же пару городов может соединять несколько дорог, также дороги могут выходить и входить в один и тот же город. Со временем K городов усилились и возвысились над остальными, между ними начались междоусобицы. И однажды империя развалилась на K государств, столицей в каждом из которых стал усилившийся город.

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

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

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

В первой строке входного файла INPUT.TXT записаны числа N (1 ≤ N ≤ 1000) и M (N-1 ≤ M ≤ 10⁵) – количество городов и дорог соответственно. В следующих M строках идет описание дорог: каждая строка содержит два целых числа x_i и y_i (1 ≤ x_i, y_i ≤ N) – номера городов, соединенные дорогой.

В следующей строке записано целое число K (1 ≤ K ≤ N) – количество столиц. В последней строке перечислены K различных целых чисел c_i (1 ≤ c_i ≤ N) – номера столиц.

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

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

Пример

Задача G. Крыша

Петя на лето уехал к бабушке в деревню, где он помогает строить новый дом. Стены уже готовы, теперь нужно делать крышу. Бабушка хочет знать: сколько шифера понадобится, чтобы накрыть крышу? Петя знает ширину и длину дома, а так же необходимую высоту крыши. Но сама крыша может быть двух видов: двускатная или шатровая. Помогите Пете – для каждого типа крыши найдите площадь, которую необходимо покрыть шифером.

Двускатная крыша	Шатровая крыша

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

Входной файл INPUT.TXT содержит три целых положительных числа a, b, h – ширина, длина и высота крыши дома соответственно. Все числа не превосходят 10 000.

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

В выходной файл OUTPUT.TXT выведите два вещественных числа – площадь двускатной и шатровой крыши с точностью не менее 6 знаков после запятой.

Пример

Задача H. Хардкорный массив

Всё, что делает Генри, является хардкорным. Вот и сейчас он выписал N целых чисел, принадлежащих отрезку [0,10⁹] и образующих хардкорный массив – массив, в котором все попарные разности различны. Попарные разности массива – это все числа |a_i−a_j| для всех i и j таких, что 1 ≤ i < j ≤ N.

Думаете, Вы такой же хардкорный, как Генри? Конечно, нет! Поэтому, Ваша задача немного проще: в выведенном Вами массиве количество различных попарных разностей должно быть хотя бы 90% от количества всех попарных разностей.

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

Входной файл INPUT.TXT содержит целое число N – требуемый размер массива (2 ≤ N ≤ 10 000).

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

В выходной файл OUTPUT.TXT выведите N целых чисел a_i (0 ≤ a_i ≤ 10⁹), удовлетворяющих заданным требованиям.

Примеры

Пояснение

Массив в третьем тестовом примере не является абсолютно хардкорным. Всего попарных разностей в нём 21, но две из них, |3−9| и |15−9|, равны между собой. Тем самым в нём 20 различных разностей, что составляет примерно 95% и является приемлемым результатом.

Задача I. Виталя и Рома

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

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

1. В начале игры число P равно нулю.
2. За всю игру совершается N операций.
3. Каждая операция – прибавление к числу P или вычитание из числа P числа 2^S.
4. После выполнения каждой операции необходимо вывести число единиц в двоичной записи числа P.

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

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

Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 10⁵) – количество операций. На следующих N строках заданы операции, где каждая операция задается одной из двух строк: «add S» или «sub S», где S (0 ≤ S ≤ 10⁵) – целое число.

Операция «add S» означает, что к числу P нужно прибавить 2^S.

Операция «sub S» означает, что из числа P нужно вычесть 2^S.

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

Для каждого из N запросов в выходной файл OUTPUT.TXT в отдельной строке выведите количество единиц в двоичной записи числа P после выполнения данной операции.

Примеры

Задача J. Квадратов много не бывает

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

Какое максимальное количество квадратных кусков можно получить таким образом?

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

Входной файл INPUT.TXT содержит два целых числа W и H, разделённых пробелом (1 ≤ W, H ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите единственное целое число – ответ на задачу.

Пример