Задача F. Тест: теория сложности и подчсёт ≡

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

Условие

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

Вопрос 0

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

Вопрос 1

Функция 8 + 6 ⋅ n + 3 ⋅ n2 + 3 ⋅ n5 является
  1. O(n)
  2. O(n5)
  3. O(n2)
  4. O(8)

Вопрос 2

Всякая функция, являющаяся O(n5), является также и
  1. O(n-5)
  2. O(n(1 / 5))
  3. O(4n)
  4. O(log(n) + n3)

Вопрос 3

Асимптотическую сложность следующего алгоритма равна Θ(mx):
СиБейсик
j = pow(m, 2);
for (i = 0; i <= pow(j, 2); ++i){
  for (k = 0; k <= pow(m, 3); ++k){
    if (k == 0)
      for (ib = 0; ib <= pow(j, 3); ++ib)
        print(ib, i, k);
    if (i <= pow(j, 2))
      for (a = 0; a <= pow(m, 2); ++a)
        print(k, a, i);
  }
  for (jb = 0; jb <= pow(i, 2); ++jb)
    if (jb == i)
      for (c = 0; c <= ib; ++c)
        print(c, jb, i);
}
j = m ^ 2
FOR i = 0 TO j ^ 2
  FOR k = 0 TO m ^ 3
    IF k = 0 THEN FOR ib = 0 TO j ^ 3
      PRINT ib, i, k
    NEXT ib
    IF i <= j ^ 2 THEN FOR a = 0 TO m ^ 2
      PRINT k, a, i
    NEXT a
  NEXT k
  FOR jb = 0 TO i ^ 2
    IF jb = i THEN FOR c = 0 TO ib
      PRINT c, jb, i
    NEXT c
  NEXT jb
NEXT i
ПаскальАлгоритмический
j := m ** 2;
for i := 0 to j ** 2 do begin
  for k := 0 to m ** 3 do begin
    if k = 0 then
      for ib := 0 to j ** 3 do
        write(ib, i, k);
    if i <= j ** 2 then
      for a := 0 to m ** 2 do
        write(k, a, i);
  end;
  for jb := 0 to i ** 2 do
    if jb = i then
      for c := 0 to ib do
        write(c, jb, i);
end;
j := m ** 2
нц для i от 0 до j ** 2
  нц для k от 0 до m ** 3
    если k = 0 то
      нц для ib от 0 до j ** 3
        вывод ib, i, k
      кц
    все
    если i <= j ** 2 то
      нц для a от 0 до m ** 2
        вывод k, a, i
      кц
    все
  кц
  нц для jb от 0 до i ** 2
    если jb = i то
      нц для c от 0 до ib
        вывод c, jb, i
      кц
    все
  кц
кц
Чему равен x?

Вопрос 4

Дан алгоритм
СиБейсик
for (j = 0; j <= pow(m, 2); ++j){
  b = m;
  for (k = 0; k <= pow(b, 2); ++k)
    print(j, k);
  for (c = 0; c <= pow(k, 3); ++c)
    for (i = 0; i <= pow(c, 3); ++i){
      cc = m;
      if (XXXXX)
        for (ib = 0; ib <= pow(c, 3); ++ib)
          print(i, ib, j, c);
      for (kj = 0; kj <= pow(m, 3); ++kj)
        print(i, c, j, kj);
    }
}
FOR j = 0 TO m ^ 2
  b = m
  FOR k = 0 TO b ^ 2
    PRINT j, k
  NEXT k
  FOR c = 0 TO k ^ 3
    FOR i = 0 TO c ^ 3
      cc = m
      IF XXXXX THEN FOR ib = 0 TO c ^ 3
        PRINT i, ib, j, c
      NEXT ib
      FOR kj = 0 TO m ^ 3
        PRINT i, c, j, kj
      NEXT kj
    NEXT i
  NEXT c
NEXT j
ПаскальАлгоритмический
for j := 0 to m ** 2 do begin
  b := m;
  for k := 0 to b ** 2 do
    write(j, k);
  for c := 0 to k ** 3 do
    for i := 0 to c ** 3 do begin
      cc := m;
      if XXXXX then
        for ib := 0 to c ** 3 do
          write(i, ib, j, c);
      for kj := 0 to m ** 3 do
        write(i, c, j, kj);
    end;
end;
нц для j от 0 до m ** 2
  b := m
  нц для k от 0 до b ** 2
    вывод j, k
  кц
  нц для c от 0 до k ** 3
    нц для i от 0 до c ** 3
      cc := m
      если XXXXX то
        нц для ib от 0 до c ** 3
          вывод i, ib, j, c
        кц
      все
      нц для kj от 0 до m ** 3
        вывод i, c, j, kj
      кц
    кц
  кц
кц
Чтобы сложность этого алгоритма составляла Θ(m42), строку XXXXX следует заменить на выражение
  1. i = j
  2. j ≤ b2
  3. j ≤ cc
  4. j = 0

Вопрос 5

Асимптотическую сложность следующего алгоритма равна Θ(mx):
СиБейсик
for (i = 0; i <= pow(m, 3); ++i)
  for (j = 0; j <= pow(m, 2); ++j){
    k = m;
    for (ib = 0; ib <= k; ++ib)
      for (b = 0; b <= pow(m, 3); ++b)
        print(j, i, ib, b);
    if (i == 0)
      for (jj = 0; jj <= ib; ++jj)
        for (ba = 0; ba <= pow(b, 2); ++ba)
          print(jj, j, ba, i);
  }
FOR i = 0 TO m ^ 3
  FOR j = 0 TO m ^ 2
    k = m
    FOR ib = 0 TO k
      FOR b = 0 TO m ^ 3
        PRINT j, i, ib, b
      NEXT b
    NEXT ib
    IF i = 0 THEN FOR jj = 0 TO ib
      FOR ba = 0 TO b ^ 2
        PRINT jj, j, ba, i
      NEXT ba
    NEXT jj
  NEXT j
NEXT i
ПаскальАлгоритмический
for i := 0 to m ** 3 do
  for j := 0 to m ** 2 do begin
    k := m;
    for ib := 0 to k do
      for b := 0 to m ** 3 do
        write(j, i, ib, b);
    if i = 0 then
      for jj := 0 to ib do
        for ba := 0 to b ** 2 do
          write(jj, j, ba, i);
  end;
нц для i от 0 до m ** 3
  нц для j от 0 до m ** 2
    k := m
    нц для ib от 0 до k
      нц для b от 0 до m ** 3
        вывод j, i, ib, b
      кц
    кц
    если i = 0 то
      нц для jj от 0 до ib
        нц для ba от 0 до b ** 2
          вывод jj, j, ba, i
        кц
      кц
    все
  кц
кц
Чему равен x?

Вопрос 6

Определите количество вызовов функции f при исполнении следующего алгоритма (в предположении неограниченной длины целых чисел):
СиБейсик
int f(int n) {
  int f;
  if (n >= 55555555555)
    f = f(n / 5) + 1;
  if (n < 55555555555 && n >= 5263157894)
    f = f(n - 3) + 1;
  if (n < 5263157894)
    f = 1;
  return f;
}

print(f(1000000000000));
FUNCTION f(n)
  IF n >= 55555555555 THEN f = f(n / 5) + 1
  IF n < 55555555555 AND n >= 5263157894 THEN f = f(n - 3) + 1
  IF n < 5263157894 THEN f = 1
END FUNCTION

PRINT f(1000000000000)
ПаскальАлгоритмический
function f(n: integer): integer;
begin
  if n >= 55555555555 then
    f := f(n / 5) + 1;
  if (n < 55555555555) and (n >= 5263157894) then
    f := f(n - 3) + 1;
  if n < 5263157894 then
    f := 1;
end;

write(f(1000000000000));
алг цел f(цел n)
нач
  если n >= 55555555555 то
    f := f(n / 5) + 1
  все
  если n < 55555555555 и n >= 5263157894 то
    f := f(n - 3) + 1
  все
  если n < 5263157894 то
    f := 1
  все
кон

вывод f(1000000000000)

Вопрос 7

Известно, что в дереве, каждый узел которого имеет степень либо 6 (внутренний узел), либо 0 (листовой узел), имеется 1486 листовых узлов. Определите количество узлов в этом дереве.

Вопрос 8

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

Вопрос 9

Графическая последовательность чисел — последовательность целых неотрицательных чисел такая, что существует граф, последовательность степеней вершин которого совпадает с ней. Какая из следующих последовательностей является графической?
  1. 5,5,2,2,1,1
  2. 5,4,3,3,2,1
  3. 5,4,3,2,1,1
  4. 5,5,4,3,2,1

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

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

0.100s 0.008s 13