Задача A. Тест ТЮП 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.

Задача B. Крейзик ≡

Условие

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

Кроме того, обычные четыре арифметических действия Вася заменил на четыре своих:

• Сцепление (обозначается символом +) — результат получается путём записи сначала всех цифр первого аргумента, а затем всех цифр второго.
• Выметание (обозначается символом -) — результат получается записью всех цифр первого аргумента, отсутствующих во втором. Если ни одной такой цифры не нашлось, результат равен 0.
• Окружение (обозначается символом *) — результат получается циклическим сдвигом первого аргумента влево столько раз, какова величина второго аргумента.
• Дробление (обозначается символом /) — результат получается записью цифр первого и второго аргумента по очереди, пока один или оба аргумента не закончатся, и затем оставшихся цифр более длинного аргумента.

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

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

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

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

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

Первая строка входного файла содержит целое число N — количество выражений. Последующие N строк содержат по одному выражению каждая.

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

Выходной файл должен содержать N строк — результаты вычисления каждого выражения.

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

5
2+3
57578-255
12304*8
11111/222
1+2/44*5-20

23
778
4123
12121211
441

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

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

1 ≤ X ≤ 2 × 10⁹

Пример

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