Задача U. Тест ТЮП 2017 ≡

Условие

Вопрос 0

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

Вопрос 1

На диаграмме показано количество участников олимпиады по трём предметам в трёх регионах России

Вопрос 2

Сколько шестерок в семеричной записи числа 343²⁰¹⁹ + 2401²⁰²² - 343?

Вопрос 3

Укажите наименьшее основание системы счисления, в которой запись числа 321 трёхзначна.

Вопрос 4

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

• F(0) = 4, F(1) = 1
• F(n) = F(n − 1) ⋅ 6 + F(n − 2) ⋅ 4, при n ≥ 2

Вопрос 5

У Дмитрия есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2²⁰ бит в секунду. У Глафиры нет скоростного доступа в Интернет, но есть возможность получать информацию от Дмитрия по телефонному каналу со средней скоростью 2¹² бит в секунду. Глафира договорилась с Дмитрием, что он скачает для него данные объемом 10 Мбайт по высокоскоростному каналу и ретранслирует их Глафире по низкоскоростному каналу.

Компьютер Дмитрия может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Дмитрием данных до полного их получения Глафирой?

В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Вопрос 6

Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 8. Система команд Кузнечика:

Вперед 85 – Кузнечик прыгает вперёд на 85 единиц,

Назад 45 – Кузнечик прыгает назад на 45 единиц.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 45», чтобы Кузнечик оказался в точке 18?

Вопрос 7

Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.

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

Вопрос 8

Ниже на че­ты­рех язы­ках про­грам­ми­ро­ва­ния за­пи­сан ре­кур­сив­ный ал­го­ритм F

FUNCTION F(k)
  PRINT k
  IF k < 5 THEN
    F(k + 1)
    F(k + 2)
    F(k + 3)
  END IF
END FUNCTION

алг цел F(цел k)
нач
  вывод k
  если k < 5 то
    F(k + 1)
    F(k + 2)
    F(k + 3)
  все
кон

function F(k: integer): integer;
begin
  write(k);
  if k < 5 then begin
    F(k + 1);
    F(k + 2);
    F(k + 3);
  end;
end;

int F(int k) {
  int F;
  print(k);
  if (k < 5) {
    F(k + 1);
    F(k + 2);
    F(k + 3);
  }
  return F;
}

Вопрос 9

В детскую игрушку «Набор юного шпиона» входят два одинаковых комплекта из 3 флажков различных цветов. Сколько различных тайных сообщений можно передать этими флажками, условившись менять выставленный флажок каждые 8 минут и наблюдая за процессом 56 минут? Наблюдатель видит вынос первого флажка и 6 перемен флажка. При этом возможна смена флажка на флажок того же цвета.

Вопрос 10

Запись десятичного числа в системах счисления с основаниями 13 и 17 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?

Вопрос 11

У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавить 1
2. умножить на 5
3. умножить на 3

Вопрос 12

Определите асимптотическую сложность следующего алгоритма:

for (i = 0; i <= pow(n, 3); ++i)
  for (j = 0; j <= pow(n, 2); ++j){
    for (b = 0; b <= n; ++b){
      a = pow(n, 2);
      for (jk = 0; jk <= pow(a, 3); ++jk)
        print(b, jk, j, i);
    }
    if (i % pow(n, 2) == 0)
      for (bi = 0; bi <= pow(b, 3); ++bi){
        k = pow(a, 3);
        for (bk = 0; bk <= k; ++bk)
          print(bk, bi, j, i);
      }
  }

FOR i = 0 TO n ^ 3
  FOR j = 0 TO n ^ 2
    FOR b = 0 TO n
      a = n ^ 2
      FOR jk = 0 TO a ^ 3
        PRINT b, jk, j, i
      NEXT jk
    NEXT b
    IF i MOD n ^ 2 = 0 THEN FOR bi = 0 TO b ^ 3
      k = a ^ 3
      FOR bk = 0 TO k
        PRINT bk, bi, j, i
      NEXT bk
    NEXT bi
  NEXT j
NEXT i

for i := 0 to n ** 3 do
  for j := 0 to n ** 2 do begin
    for b := 0 to n do begin
      a := n ** 2;
      for jk := 0 to a ** 3 do
        write(b, jk, j, i);
    end;
    if i mod n ** 2 = 0 then
      for bi := 0 to b ** 3 do begin
        k := a ** 3;
        for bk := 0 to k do
          write(bk, bi, j, i);
      end;
  end;

нц для i от 0 до n ** 3
  нц для j от 0 до n ** 2
    нц для b от 0 до n
      a := n ** 2
      нц для jk от 0 до a ** 3
        вывод b, jk, j, i
      кц
    кц
    если mod(i, n ** 2) = 0 то
      нц для bi от 0 до b ** 3
        k := a ** 3
        нц для bk от 0 до k
          вывод bk, bi, j, i
        кц
      кц
    все
  кц
кц

1. Θ(n³)
2. Θ(n⁵)
3. Θ(n¹²)
4. Θ(n²)

Вопрос 13

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

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

int f(int n) {
  int f;
  if (n >= 32258064516)
    f = f(n / 3) + 1;
  if (n < 32258064516 && n >= 666666666)
    f = f(n - 5) + 1;
  if (n < 666666666)
    f = 1;
  return f;
}

print(f(1000000000000));

FUNCTION f(n)
  IF n >= 32258064516 THEN f = f(n / 3) + 1
  IF n < 32258064516 AND n >= 666666666 THEN f = f(n - 5) + 1
  IF n < 666666666 THEN f = 1
END FUNCTION

PRINT f(1000000000000)

function f(n: integer): integer;
begin
  if n >= 32258064516 then
    f := f(n div 3) + 1;
  if (n < 32258064516) and (n >= 666666666) then
    f := f(n - 5) + 1;
  if n < 666666666 then
    f := 1;
end;

write(f(1000000000000));

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

вывод f(1000000000000)

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

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