Задача A. Параллелепипед со спицами

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

Условие

Возьмём A × B × C одинаковых кубиков. Сложим из всех кубиков один большой прямоугольный параллелепипед шириной A кубиков, высотой B кубиков и длиной C кубиков. Начнём протыкать этот параллелепипед спицами параллельно его рёбрам.

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

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

Входной файла содержит целые числа A B C — размеры параллелепипеда.

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

Выходной файл должен содержать единственно целое число — максимальное количество спиц.

Ограничения

1 ≤ A, B, C ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
37 19 29
1073

Задача B. Питание программистов

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

Условие

Оргкомитет сборов по программированию знает, что важно организовать правильное питание участников. Еда должна быть вкусной, а блюда — разнообразными. Поэтому разработку меню доверили повару тёте Вале.

Тётя Валя умеет готовить несколько разных блюд. Она использует для их обозначения маленькие английские буквы. Всего в течение сборов будет n приёмов пищи. Тётя Валя составила черновик меню — строку s, состоящую из n маленьких английских букв. Символ si обозначает блюдо, которое она запланировала для i-го приёма пищи.

Черновик меню полностью сбалансирован по всем питательным компонентам, но тётя Валя не особо заботилась о разнообразии.

Помогите тёте Вале сделать меню наиболее разнообразным. Для этого нужно переставить блюда в меню таким образом, чтобы минимальное расстояние между одинаковыми блюдами было как можно больше.

Если существует несколько решений, выведите любое из них.

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

Входной файл содержит строку s, состоящую из маленьких букв английского алфавита — черновик меню.

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

Выходной файл должен содержать единственную строку — окончательный вариант меню.

Ограничения

1 ≤ n ≤ 100000;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
olmkoo
moloko

Задача C. Открытый подсчёт 2

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

Условие

Юный робототехник Вася построил робота, который способен перемещаться по неограниченному клетчатому полю согласно заложенной в него программе. Робот занимает ровно одну клетку поля. Программа для робота состоит из последовательности команд, разделённых пробелом. Каждая команда состоит из латинской буквы и натурального числа. Буква задаёт направление движения (U — на север, D — на юг, L — на запад, R — на восток), а число — количество клеток, на которое робот должен сдвинуться.

Робот выполняет команды в бесконечном цикле — т. е. после выполнения последней команды он снова переходит к первой.

На поле задана система координат. Ось ординат направлена не север, ось абсцисс направлена на восток. Робот начинает движение с клетки с координатами (0, 0).

Требуется по данной программе определить количество клеток внутри прямоугольника с координатами (x1, y1) − (x2, y2), которые будут когда-либо посещены роботом.

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

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

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

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

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

Первая строка входного файла содержит целое число N — количество программ. Далее следует N пар строк. В каждой паре первая строка содержит программу, а вторая — целые числа x1 y1 x2 y2.

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
U1 R2
1 1 3 2
L1 R2
100 -10 200 10
4
101

Задача D. Методом тряпки

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

Условие

Школьники плохо написали контрольную работу по признакам делимости на k. Марфа Геннадьевна оставила их после уроков для работы над ошибками. Она написала на доске большое число N и сама на секунду задумалась. А делится ли её число на k?

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

Напишите программу, которая поможет Марфе Геннадьевне определить, какое число будет записано на доске в итоге. В записи числа не должны присутствовать лидирующие нули. Если искомых чисел найдётся несколько, выведите любое из них. Если искомого числа не существует, то Марфе Геннадьевне придётся стереть всё число целиком, а вам  — вывести слово IMPOSSIBLE.

В первом примере необходимо стереть цифры 7 и 6. Если стереть цифры 1, 4, 6, то полученное число 7 будет делиться на 7, но этот ответ не оптимален.

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

В третьем примере ничего нельзя поделать.

Система оценивания

Рекомендуется рассмотреть следующие частные случаи:

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

Входной файл содержит целые числа k N.

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

Выходной файл должен содержать либо число, которое останется на доске, либо слово IMPOSSIBLE, если на доске ничего не останется.

Ограничения

1 ≤ k ≤ 1000;

1 ≤ N ≤ 101000;

в записи числа N нет лидирующий нулей;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7
1746
14
2
3
106
6
3
10
256
IMPOSSIBLE

Задача E. Тест: задания типа ЕГЭ

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

Условие

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

Вопрос 0

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

Вопрос 1

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

вверхвнизвлевовправо
При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

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

сверху свободноснизу свободнослева свободносправа свободно

Цикл

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

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

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

НАЧАЛО

ПОКА < справа свободно > вправо

ПОКА < снизу свободно > вниз

ПОКА < слева свободно > влево

ПОКА < сверху свободно > вверх

КОНЕЦ

Вопрос 2

Каково наименьшее натуральное число X, при котором истинно высказывание (X + 1) ⋅ (X + 1) ≤ 69 → (X − 1) ⋅ X > 99?

Вопрос 3

У исполнителя Калькулятор две команды, которым присвоены номера:
  1. Умножь на 2
  2. Прибавь 8
Выполняя первую из них, Калькулятор умножает число на экране на 2, а выполняя вторую, прибавляет к нему 8. Запишите порядок команд в программе получения из числа 2 числа 68, содержащей не более 5 команд, указывая лишь номера команд (Например, программа 21112 — это программма
  • прибавь 8
  • умножь на 2
  • умножь на 2
  • умножь на 2
  • прибавь 8,
которая преобразует число 1 в число 80)

Вопрос 4

На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Харитон, Ефим, Игнатий, Тимур. Известно, что каждый из них владеет ровно одной из следующих профессий: Горнорабочий, Журналист, Токарь, Хореограф, но неизвестно, кто какой и неизвестно, кто в каком доме живет. Однако, известно, что:

  1. Тимур живёт правее, чем Игнатий
  2. Харитон живет левее, чем Игнатий
  3. Токарь живёт не рядом c Журналистом
  4. Журналист живет левее Токаря
  5. Горнорабочий живет левее, чем Журналист
  6. Ефим работает Журналистом
Выясните, кто какой профессии, и кто где живет, и дайте ответ в виде номеров людей, в порядке слева направо. (Харитон — 1, Ефим — 2, Игнатий — 3, Тимур — 4) Например, если бы в домах жили (слева направо) Ефим, Тимур, Харитон, Игнатий, ответ был бы: 2413.

Вопрос 5

Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа — латинской буквы «A». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется i-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу:
  1. A
  2. AAB
  3. AABAABC
  4. AABAABCAABAABCD

Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ

Имеется задание: «Определить символ, стоящий в n-й строке на позиции 2n−2 − 4, считая от левого края цепочки».

Выполните это задание для n = 10, в ответе укажите номер буквы в алфавите (A — 1, B — 2, и т.д.)

Вопрос 6

У исполнителя Калькулятор две команды:
  1. вычти 3
  2. прибавь 6
Первая из них уменьшает число на экране на 3, вторая – увеличивает его на 6 (отрицательные числа допускаются). Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 3 с помощью программы, которая содержит ровно 5 команд?

Вопрос 7

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8 которые удовлетворяют всем перечисленным ниже условиям?

(((x1x2) ∨ (x3x4)) ∧ (¬ (x1x2) ∨ ¬ (x3x4))) = 1

(((x3x4) ∨ (x5x6)) ∧ (¬ (x3x4) ∨ ¬ (x5x6))) = 1

(((x5x6) ∨ (x7x8)) ∧ (¬ (x5x6) ∨ ¬ (x7x8))) = 1

В ответе не нужно перечислять все различные наборы значений x1, x2, x3, x4, x5, x6, x7, x8, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

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

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


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

Автор:А. Ким, А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб
Максимальный балл: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. jb2
  3. jcc
  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.057s 0.005s 19