Задача A. Кубический глобус ≡

Условие

Желая поразить воображение учительницы географии (и исправить годовую отметку), Антон хочет изготовить глобус в форме куба. Чтобы изделие не порвалось при переноске, он раздобыл лист Очень Прочной Бумаги размером a на b миллиметров.

Теперь он хочет вырезать из этого листа бумаги развертку куба с максимальной длиной стороны. Как продвинутый математик, Антон точно знает, что существует ровно 11 принципиально различных разверток куба (см. рисунок).

Помогите Антону определить длину наибольшей целой стороны куба, который можно вырезать из имеющегося у него листа бумаги. Стороны развертки должны располагаться параллельно сторонам листа. Антон может выбрать любую из 11 разверток и (при необходимости) повернуть ее на 90 градусов.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1 1

0

3 4

1

101 101

25

Задача B. Тимофей и среднее треугольное ≡

Условие

Сегодня в школе на уроке математики Тимофею рассказали про среднее арифметическое. Вдохновившись и пообедав, Тимофей придумал понятие "среднее треугольное". Он берет три числа и записывает их в вершинах равностороннего треугольника. На середине каждой стороны он записывает новое число — среднее арифметическое двух чисел в вершинах треугольника, соединенных этой стороной. Эту конструкцию Тимофей и называет "среднее треугольное" и собирается поразить ей одноклассников.

Например, выбрав числа  − 2, 2 и 6, Тимофей получит новую тройку чисел: 0, 2 и 4. Процесс можно продолжить и получить следующую тройку чисел: 1, 2 и 3.

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

Помогите Тимофею! Подберите для него исходную тройку чисел, такую, что ровно через указанное число повторений получится "среднее треугольное", соответствующее числам, записанным на его листочке. Тимофей твердо помнит, что исходные числа по модулю не превышали 10¹⁵ и ни на одном этапе вычислений он не получал дробных чисел.

Формат входного файла

В первой строке входного файла содержится натуральное число: k — количество полученных за вечер троек чисел. В трех последующих строках содержатся целые числа a, b, c (по одному числу в строке) — последняя полученная Тимофеем тройка чисел.

Формат выходного файла

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

Ограничения

1 ≤ k ≤ 40

 − 100 ≤ a, b, c ≤ 100

Примеры тестов

2
1
2
3

-2
2
6

10
0
0
0

0
0
0

3
0
1
0

-5
3
3

Задача C. Много-много шоколадок ≡

Условие

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

Альпен и Баунти купили N прямоугольных конфет размера 1 × 2 и M конфет размера 1 × 3. Шоколадки же имеют размер 3 × 5. Из набора конфет можно скрафтить одну шоколадку, если получится сложить конфеты так, чтобы получился прямоугольник нужного размера. Отрывать или откусывать части конфет нельзя, то есть в крафте могут участвовать только целые конфеты.

Помогите Альпену и Баунти определить максимальное количество шоколадок, которые они могут скрафтить.

Формат входного файла

Входной файл должен содержать два целых числа N и M — количество конфет размера 1 × 2 и 1 × 3 соответственно.

Формат выходного файла

Выходной файл должен содержать единственное целое число — максимальное количество шоколадок, которые могут получить Альпен и Баунти.

Ограничения

0 ≤ N, M ≤ 10¹⁸

Описание подзадач и системы оценивания

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

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

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

Примеры тестов

5 3

1

10 10

3

0 12

2

Задача D. Поход за шляпой ≡

Условие

Юная программистка Маша уговорила своего друга Васю сходить с ней в торговый центр и помочь в выборе новой шляпы. Торговый центр состоит из N бутиков, каждый из которых продаёт шляпы определённого бренда. Бренды обозначены малыми латинскими буквами. Один и тот же бренд может встречаться в нескольких бутиках. Бутики расположены в один ряд и пронумерованы от 1 до N.

Маша выбирает шляпу в несколько заходов. Заход номер i состоит из посещения отрезка бутиков с номерами от L_i до R_i (1 ≤ L_i ≤ R_i ≤ N). Маше нравится процесс выбора, поэтому она хочет сделать как можно больше заходов. Однако, чтобы не слишком сильно испытывать терпение Васи, она решила делать заходы по следующим правилам:

• отрезки, пройденные в различных заходах, не должны совпадать (но могут частично перекрываться);
• в каждом из заходов, начиная со второго, могут встречаться бутики только тех брендов, которые были посещены в предыдущий заход (то есть множество различных брендов либо остаётся таким же, либо сокращается).

Например, для ряда из 5 бутиков с брендами caabb возможна такая последовательность заходов:

(1, 5), (1, 4), (2, 5), (3, 4), (2, 4), (3, 5), (4, 4), (4, 5), (5, 5).

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

Отправка решения и тестирование

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

За тесты c 1 по 20 начисляется по 2 балла, за остальные (с 21 по 40) по 3 балла.

Формат входного файла

Первая строка входного файла содержит целое число T — количество тестов. Далее идут T описаний тестов, по две строки на описание.

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

Формат выходного файла

Выходной файл должен содержать T ответов на тесты.

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

В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с числом 0.

Ограничения

Буквы брендов находятся в диапазоне от 'a' до 't'.

1 ≤ N ≤ 1000

Примеры тестов

2
2
aa
5
caabb

3
9

Задача E. Цветные квадраты ≡

Условие

Талантливый художник Казимир создал профиль в социальной сети для художников. Он публикует там свои картины. Каждая картина Казимира представляет собой квадрат цвета c_i. Картины в профиле этой социальной сети размещаются в три столбца и произвольное количество строк в указанном порядке (числа обозначают последовательные номера картин):

Когда Казимир публикует очередную картину, она располагается в левом верхнем углу, а все предыдущие картины сдвигаются вправо, при необходимости переходя на новую строку:

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

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

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

Формат входного файла

В первой строке входного файла содержится единственное число N — количество уже опубликованных картин. В следующих строках находятся N целых чисел c_i — цвета картин (1 — красный, 2 — зеленый, 3 — синий). Картины во входном файле расположены в порядке, описанном в условии.

Формат выходного файла

Выходной файл в должен содержать единственное целое число M — минимальное количество картин, которые нужно опубликовать Казимиру. Далее должны следовать M целых чисел p_i — цвета картин в том порядке, в котором Казимир должен их публиковать. Если существует несколько вариантов ответа, выведите любой из них.

Ограничения

1 ≤ c_i, p_i ≤ 3

1 ≤ N ≤ 100

Примеры тестов

8
3 3 1
2 1 1
2 1

4
2 1 1 2 

3
1 2 1

3
1 2 1 

7
3 1 2
1 1 2
1

5
1 2 3 1 2 

Задача F. Тест ТЮП 2018 ≡

Условие

Вопрос 0

Сколько будет 7 + 2?

Вопрос 1

Сколько бит содержит 2 Гбайт (укажите номер правильного ответа)?

1. 2 × 10⁹
2. 2³¹
3. 2³⁴
4. 16 × 10⁹

Вопрос 2

На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Леонид (1), Павел (2), Владимир (3), Яромир (4). Известно, что каждый из них владеет ровно одной из следующих профессий: Штукатур, Веб-дизайнер, Художник, Риэлтер, но неизвестно, кто какой и неизвестно, кто в каком доме живет. Однако, известно, что:

1. Владимир живёт рядом c Павлом
2. Владимир живет левее Веб-дизайнера
3. Веб-дизайнер живет левее Художника
4. Риэлтер живёт не рядом c Штукатуром
5. Риэлтер живёт не рядом c Художником
6. Художник живёт правее, чем Штукатур
7. Леонид живет левее, чем Яромир

Вопрос 3

На вход ал­го­рит­ма подаётся на­ту­раль­ное число N. Ал­го­ритм стро­ит по нему новое число R сле­ду­ю­щим об­ра­зом:

1. Стро­ит­ся дво­ич­ная за­пись числа N.
2. К этой за­пи­си до­пи­сы­ва­ют­ся спра­ва ещё два раз­ря­да по сле­ду­ю­ще­му пра­ви­лу:
   а) скла­ды­ва­ют­ся все цифры дво­ич­ной за­пи­си, и оста­ток от де­ле­ния суммы на 2 до­пи­сы­ва­ет­ся в конец числа (спра­ва).
   На­при­мер, за­пись 11100 пре­об­ра­зу­ет­ся в за­пись 111001;
   б) над этой за­пи­сью про­из­во­дят­ся те же дей­ствия – спра­ва до­пи­сы­ва­ет­ся оста­ток от де­ле­ния суммы цифр на 2.

По­лу­чен­ная таким об­ра­зом за­пись (в ней на два раз­ря­да боль­ше, чем в за­пи­си ис­ход­но­го числа N) яв­ля­ет­ся дво­ич­ной за­пи­сью ис­ко­мо­го числа R.
Ука­жи­те такое наи­мень­шее число N, для ко­то­ро­го ре­зуль­тат ра­бо­ты ал­го­рит­ма боль­ше 2251. В от­ве­те это число за­пи­ши­те в де­ся­тич­ной си­сте­ме счис­ле­ния.

Вопрос 4

Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа — латинской буквы «A». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется i-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу:

1. A
2. AAB
3. AABAABC
4. AABAABCAABAABCD

Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ

Вопрос 5

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

Вопрос 6

Дан неориентированный граф с вершинами v₁, v₂, ... , v_n. Вершины v_i, v_j связаны ребром тогда и только тогда, когда 1 ≤ |i − j| ≤ 2. Каждому такому ребру соответствует вес i + j. На рисунке представлен граф с n = 4. Вам требуется получить другой граф, удалив из исходного графа некоторые ребра так, что в полученном графе:

• из каждой вершины существует путь в любую другую
• не существует ни одного цикла
• суммарный вес ребер минимально возможный

Какой минимально возможный суммарный вес будет иметь полученный вышеописанным способом граф, при исходном графе с n = 4?

Вопрос 7

Какой минимально возможный суммарный вес будет иметь полученный вышеописанным способом граф, при исходном графе с n = 1000000?

Вопрос 8

Какая последняя цифра у числа 112313^3773422

Формат выходного файла

В качестве решения принимается текстовый файл, содержащий по одному числу в строке — ответы на каждый из вопросов. При отправке файла следует выбрать в тестирующей системе среду разработки "Answer text". Если вы не знаете ответа на какой-то из вопросов, укажите вместо ответа число 0.