Задача A. Продвинутый счёт ≡

Условие

Бронислав, внук Марфы Геннадьевны, недавно начал учиться считать. Чтобы приобрести как можно больше практических навыков, он считал всё подряд: деревья на улице, прохожих, ветки, листья на деревьях, свои шаги и даже калории.

После длительных занятий, в подтверждение закона перехода количества в качество, Бронислав придумал технологию, упрощающую счёт. Он взял блокнот и каждый раз ставил чёрточку для очередного объекта. Одну чёрточку Бронислав назвал единицей нулевого уровня. Если a₀ единиц 0-го уровня идут в блокноте друг за другом, то Бронислав заменяет их на одну единицу 1-го уровня (например, это может быть более длинная или более жирная чёрточка или чёрточка другого цвета). Далее a₁ идущих друг за другом единиц 1-го уровня заменяются на одну единицу 2-го уровня и т.д. В итоге у Бронислава в блокноте вместо кучи чёрточек остаётся компактный код следующего вида: k_N k_N−1 … k₁ k₀, где k_j — количество единиц j-го уровня.

Можно заметить, что если a_j = B^j (B > 1), то код — это представление количества объектов M в системе счисления с основанием B.

Эксперты высоко оценили методику Бронислава — ведь с её помощью можно эффективно и с высокой точностью считать самые разные объекты, например время: единицы 0-го уровня — это секунды, 1-го — минуты, далее часы, дни, недели, месяцы, годы и т.д.

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

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

Входной файл содержит целые числа M N, за которыми следуют N целых чисел a₀ a₁ a₂ … a_N−1.

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

Выходной файл должен содержать N+1 целых чисел k_N k_N−1 … k₁ k₀.

Ограничения

1 ≤ M ≤ 2⋅10⁹.

1 ≤ N ≤ 10.

2 ≤ a_i ≤ 100.

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

123456789
4
10 10 10 10

12345 6 7 8 9

5400
3
60 60 24

0 1 30 0

101
3
2 5 3

3 1 0 1

Задача B. Тест ТЮП 2016 ≡

Условие

Вопрос 0

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

Вопрос 1

Путешественник пришел в 7:37 на автостанцию населенного пункта ЗАЙЦЕВО и обнаружил следующее расписание автобусов для всей районной сети маршрутов:

Определите самое раннее время, когда путешественник сможет оказаться в пункте МЕДВЕЖЬЕ согласно этому расписанию. Укажите время в виде последовательности цифр без знака ':', но с указанием лидирующего нуля в минутах. Например, время 06:03 укажите как 603.

Вопрос 2

Результаты тестирования представлены в таблице

Вопрос 3

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

Четыре команды проверяют условие отсутствия стены у той клетки, где находится РОБОТ

Цикл

ПОКА < условие > команда

выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Сколько клеток приведённого лабиринта соответствует условию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?

Вопрос 4

Семь школьников, остававшихся в классе на перемене, были вызваны к классному руководителю. Один из них разбил окно в кабинете. На вопрос руководителя, кто это сделал, были получены следующие ответы:

1. Жанна: «Это сделали Ирма или Сергей»
2. Надежда: «Это Ирма или Елена или я или Демьян»
3. Сергей: «Виноват я»
4. Юлиан: «Это сделали Жанна или я или Сергей или Надежда»
5. Демьян: «Это Жанна»
6. Елена: «Я не виновата»
7. Ирма: «Всему виной я или Юлиан или Надежда»

Вопрос 5

Сколь­ко слов длины 4, на­чи­на­ю­щих­ся с гласной буквы, можно со­ста­вить из букв: Ю, Т, Н, В, Я, Ы. Каж­дая буква может вхо­дить в слово не­сколь­ко раз. Слова не обя­за­тель­но долж­ны быть осмыс­лен­ны­ми сло­ва­ми рус­ско­го языка.

Вопрос 6

В таблице представлена схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, З, И и К. Двигаться по каждой дороге можно только в направлении, указанном стрелкой. Сколько существует различных дорог из города А в город К?

Вопрос 7

Функция 8 + 7 ⋅ n + 4 ⋅ n⁶ + 6 ⋅ n³ является

1. O(n³)
2. O(8)
3. O(n⁶)
4. O(n)

Вопрос 8

Всякая функция, являющаяся O(n⁵), является также и

1. O(log(n) + n²)
2. O(n^{(1 / 5)})
3. O(log(n) ⋅ n³)
4. O(4ⁿ)

Вопрос 9

Асимптотическая сложность следующего алгоритма равна Θ(n^x):

for (a = 0; a <= n; ++a){
  for (k = 0; k <= pow(n, 4); ++k)
    buf[k] = k;
  for (j = 0; j <= pow(n, 3); ++j)
    buf[j] = j;
}

FOR a = 0 TO n
  FOR k = 0 TO n ^ 4
    buf(k) = k
  NEXT k
  FOR j = 0 TO n ^ 3
    buf(j) = j
  NEXT j
NEXT a

for a := 0 to n do begin
  for k := 0 to n ** 4 do
    buf[k] := k;
  for j := 0 to n ** 3 do
    buf[j] := j;
end;

нц для a от 0 до n
  нц для k от 0 до n ** 4
    buf[k] := k
  кц
  нц для j от 0 до n ** 3
    buf[j] := j
  кц
кц

Вопрос 10

Дан алгоритм

for (i = 0; i <= pow(n, 2); ++i){
  c = n;
  for (cb = 0; cb <= pow(c, 2); ++cb){
    k = c;
    if (XXXXX)
      for (ca = 0; ca <= pow(cb, 3); ++ca)
        print(ca, cb, i);
  }
}

FOR i = 0 TO n ^ 2
  c = n
  FOR cb = 0 TO c ^ 2
    k = c
    IF XXXXX THEN FOR ca = 0 TO cb ^ 3
      PRINT ca, cb, i
    NEXT ca
  NEXT cb
NEXT i

for i := 0 to n ** 2 do begin
  c := n;
  for cb := 0 to c ** 2 do begin
    k := c;
    if XXXXX then
      for ca := 0 to cb ** 3 do
        write(ca, cb, i);
  end;
end;

нц для i от 0 до n ** 2
  c := n
  нц для cb от 0 до c ** 2
    k := c
    если XXXXX то
      нц для ca от 0 до cb ** 3
        вывод ca, cb, i
      кц
    все
  кц
кц

1. cb % k³ = 0
2. i = cb
3. i ≤ c
4. i ≤ c³

Вопрос 11

Определите количество вызовов функции f при исполнении следующего алгоритма:

Прим. Пренебречь размерностью целочисленных переменных.

int f(int n) {
  int f;
  if (n >= 32258064516)
    f = f(n / 4) + 1;
  if (n < 32258064516 && n >= 645161290)
    f = f(n - 4) + 1;
  if (n < 645161290)
    f = 1;
  return f;
}

print(f(1000000000000));

FUNCTION f(n)
  IF n >= 32258064516 THEN f = f(n / 4) + 1
  IF n < 32258064516 AND n >= 645161290 THEN f = f(n - 4) + 1
  IF n < 645161290 THEN f = 1
END FUNCTION

PRINT f(1000000000000)

function f(n: integer): integer;
begin
  if n >= 32258064516 then
    f := f(n / 4) + 1;
  if (n < 32258064516) and (n >= 645161290) then
    f := f(n - 4) + 1;
  if n < 645161290 then
    f := 1;
end;

write(f(1000000000000));

алг цел f(цел n)
нач
  если n >= 32258064516 то
    f := f(n / 4) + 1
  все
  если n < 32258064516 и n >= 645161290 то
    f := f(n - 4) + 1
  все
  если n < 645161290 то
    f := 1
  все
кон

вывод f(1000000000000)

Вопрос 12

Выберите набор ровно из 4 команд, необходимый для того чтобы из списка (3,1,3,1) получить список (3,2,2)

1. удалить справа
2. добавить справа 1
3. заменить все 3 на 2
4. заменить все 1 на 2
5. удалить все 1
6. добавить справа 3

Вопрос 13

Известно, что в дереве, каждый узел которого имеет степень исхода либо 4, либо 0, высота равна 7. Определите максимально возможное количество узлов такого дерева. (Высота дерева — максимальная длина пути от вершины дерева до его корня. Например, высота дерева, состоящего только из корня, равна 0.)

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

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

Задача C. Чёрный ящик ≡

Условие

Данная задача является интерактивной.

Юные программисты Петя и Вася играют в следующую игру. Петя задумывает последовательность команд двух видов:

1. Увеличить число на 1.
2. Увеличить число в X раз.

Игра наскучила Пете, и он написал программу, которая играет за него. Программа действует почти так же, как Петя, однако если результат вычислений превосходит 2 × 10⁹, программа сообщает число −1 вместо результата.

Теперь Вася хочет написать программу, которая выиграет у программы Пети.

Протокол взаимодействия

На каждом шаге взаимодействия, кроме последнего, ваша программа должна:

1. Вывести целое число X в выходной поток.
2. Ввести результат вычисления из входного потока.

На последнем шаге программа должна вывести строку, состоящую из символов + и *, обозначающих соответственно команды "Увеличить число на 1" и "Увеличить число в X раз".

После каждого шага, включая последний, следует вывести перевод строки и выполнить сброс буфера (flush).

Ограничения

Количество команд в последовательности находится в диапазоне от 1 до 20

1 ≤ X ≤ 2 × 10⁹

Пример

Если Петя задумал последовательность +*++, а Вася предложил выполнить её для X = 3, то Петя ответит ему числом 8. Такое же число 8 получилось бы, если бы Петя задумал *+++++. Поэтому Вася пока не может однозначно угадать Петину последовательность, и должен сделать ещё один ход.

Задача D. Уровни доступа ≡

Условие

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

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

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

Рекомендуется рассмотреть частичные решения.

• N, K_i, M ≤ 100
• M ≤ 2000

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

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

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

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

Первая строка выходного файла должна содержать целое число L — количество разных уровней доступа. Следующие L строк должны содержать описания уровней. Каждая из этих строк соответствует очередному уровню доступа и должна содержать целое число D_i ≥ 1, за которым следует строго возрастающая последовательность из D_i целых чисел — номера кабинетов, доступных на этом и последующих уровнях, но недоступных на предыдущих уровнях.

Если решения не существует, выведите единственное число −1.

Ограничения

1 ≤ N, K_i ≤ 2000, 1 ≤ M ≤ 10⁹

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

3 3
2 0 1
3 0 2 1
3 2 1 0

2
2 0 1
1 2

3 3
1 0
1 1
1 2

-1

Задача E. Рассадка школьников ≡

Условие

Марфа Геннадьевна является главным организатором школьной олимпиады по информатике.

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

На олимпиаду придут участники трех школ  — с номерами 1, 2, 3. Марфа Геннадьевна также ведет в этих школах мастер-классы, поэтому знает, что ученики школы 1 ведут себя хорошо и не разговаривают ни с кем во время олимпиады.

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

А ученики школы 3 могут разговаривать друг с другом так громко, что Марфа Геннадьевна не будет садить их ближе чем через два участника из других школ.

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

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

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

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

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Если правильный ответ на какой-то из тестов получить не удалось, выведите вместо него число 0.

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

Первая строка входного файла содержит целое число T — количество тестов. Далее следует T троек чисел c₁ c₂ c₃ — количества участников из соответствующих школ.

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

Выходной файл должен содержать T строк, состоящих из цифр 1, 2 или 3 — рассадки школьников, согласно требованиям Марфы Геннадьевны. Если составить рассадку невозможно, выведите в соответствующую строку слово impossible.

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

2
1 1 1
1 0 2

231
impossible

Задача F. Подходящий интервал ≡

Условие

Во время тура данная задача будет проверяться только на тестах из условия. Окончательное тестирование будет проведено после тура.

Дан массив из N целых чисел a_i.

Требуется найти два числа, a_p и a_q, удаленных друг от друга не менее, чем на L и не более чем на R (т.е. p < q, L ≤ q − p ≤ R), таких что минимальное из этих двух чисел будет максимально возможным.

Рекомендуется рассмотреть частичные решения

• N ≤ 1000
• L = 1
• R = N − 1

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

Входной файл содержит целые числа N L R, за которыми следуют N целых чисел: a₁ a₂ … a_N.

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

Выходной файл должен содержать два целых числа p q — позиции искомых чисел в массиве. Нумерация позиций начинается с 1.

Если решений несколько, выберите решение с наименьшим значением p, а если и таких несколько — с минимальным значением q.

Ограничения

2 ≤ N ≤ 100000

1 ≤ L ≤ R < N; 1 ≤ p < q ≤ N

1 ≤ a_i ≤ 10⁹

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

3 1 2
2 1 2

1 3