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

Автор:	А. Кленин		Ограничение времени:	1 сек
Входной файл:	input.txt		Ограничение памяти:	256 Мб
Выходной файл:	output.txt
Максимальный балл:	100

Условие

Данная задача — тест. Требуется ответить на приведённые вопросы и отправить ответ в тестирующую систему в указанном ниже формате. За каждый правильный ответ будут начисляться баллы. Баллы за все вопросы, кроме нулевого, будут видны после окончания тура.

Вопрос 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. Леонид живет левее, чем Яромир

Выясните, кто какой профессии, и кто где живет, и дайте ответ в виде номеров людей, в порядке слева направо. Например, если бы в домах жили (слева направо) Леонид, Владимир, Павел, Яромир, ответ был бы: 1324

Вопрос 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

Имеется задание: «Определить символ, стоящий в n-й строке на позиции 2ⁿ⁻⁴ − 1, считая от левого края цепочки».
Выполните это задание для n = 10. В ответе укажите номер символа в алфавите (A - 1, B - 2, ..., Z - 26).

Вопрос 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.

---