Задача A. Пицца ≡

Условие

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

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

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

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

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

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

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

Далее следует N различных целых чисел a_i — размеры кусочков пиццы, перечисленные в порядке обхода по кругу.

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁹

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

3
1 2 3

1

5
8 5 6 10 3

5

1
1000000000

1000000000

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

Задача C. Карта сокровищ ≡

Условие

У Ильи имеется карта сокровищ размера H × W клеток.

Маленький брат Ильи — Никита, взял эту карту "поиграть". Игра заключалась в следующем: какое-то количество раз карта была сложена вдвое по вертикали или по горизонтали. Складывая карту по вертикали, Никита брал её за нижнюю сторону, по горизонтали — за правую сторону. После этого он соединял взятую сторону с противоположной стороной. При этом верхний левый угол карты всегда оставался неподвижным. Линия сгиба всегда проходила точно по границе между клетками. В итоге сложенная карта оказалось размером N × M клеток.

Но этого Никите было мало, он взял иглу и начал протыкать некоторые клетки насквозь, включая все слои, получившиеся в процессе складывания. Как только Илья увидел это, он немедленно остановил брата. Илья побоялся разворачивать карту, так как она может порваться.

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

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

Первая строка входного файла содержит два целых числа H и W — высоту и ширину исходной карты.

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

Далее следует N строк по M символов в каждой — описание карты. Символом 'X' (ASCII 88) отмечается клетка, которую проткнул Никита, символом '.' (ASCII 46) отмечается нетронутая клетка.

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

Далее в Q строках содержится по четыре числа в каждой. x_i, y_i, u_i, v_i — описание i-й прямоугольной области карты. x_i, y_i — координаты левого верхнего угла прямоугольника, u_i, v_i — координаты правого нижнего угла прямоугольника.

Нумерация клеток по вертикали сверху вниз с 1 до H, нумерация клеток по горизонтали слева направо с 1 до W.

Гарантируется, что свёрнутая карта получена из исходной путём преобразований, описанных в задаче. То есть существую такие целые числа a и b, что N × 2^a = H и M × 2^b = W.

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

Выходной файл должен содержать Q строк, каждая из которых содержит по одному целому числу. Число в строке номер i должно быть равно количеству отверстий, которые попали в i-ю прямоугольную область.

Ограничения

1 ≤ H, W ≤ 10⁹

1 ≤ N, M ≤ 10³

1 ≤ Q ≤ 10⁵

1 ≤ x_i ≤ u_i ≤ H, 1 ≤ y_i ≤ v_i ≤ W

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

6 6
3 3
...
.X.
...
5
2 2 2 2
5 2 5 2
2 5 2 5
5 5 5 5
6 6 6 6

1
1
1
1
0

4 3
2 3
X.X
.X.
12
1 1 1 1
1 2 1 2
1 3 1 3
2 1 2 1
2 2 2 2
2 3 2 3
3 1 3 1
3 2 3 2
3 3 3 3
4 1 4 1
4 2 4 2
4 3 4 3

1
0
1
0
1
0
0
1
0
1
0
1

640 896
5 7
.......
.......
..X....
.......
.......
2
543 782 543 782
543 783 543 783

1
0

10 10
5 5
XX...
.XXX.
...X.
.XX..
XX.X.
5
2 8 10 10
2 10 7 10
4 8 7 10
2 8 7 9
2 4 10 9

14
2
8
8
23

640 960
5 15
.XX..X..XXX..XX
X...X.X..X..X..
X...X.X..X...X.
X...XXX..X....X
.XX.X.X..X..XX.
2
1 1 640 960
333 121 634 932

253952
101336

Задача D. Сумма равна произведению ≡

Условие

Учитель математики придумал игру для развития навыков устного счёта. Учитель записывает на доске таблицу A из N × N натуральных чисел. Затем он вызывает к доске двух учеников, и указывает одно из чисел в таблице (A_ij). Первый ученик должен выбрать другое число в той же строке, что и указанное учителем (A_iq, q ≠ j), и сложить с указанным числом. Второй ученик должен выбрать другое число в той же столбце, что и указанное учителем (A_pj, p ≠ i), и перемножить с указанным числом.

Если результаты вычислений у двух учеников совпали (A_ij + A_iq = A_ij × A_pj), то ученики получают пятёрки. Чтобы игра была честной, учитель указывает только на такие элементы, для которых существует хотя бы одна подходящая пара чисел. Учитель хочет вызвать как можно больше учеников, указывая каждым на ранее не использованный элемент в таблице.

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

По втором примере учитель может выбрать число. 2 (2 + 8 = 2 × 5), 4 (4 + 8 = 4 × 3) либо 3 (3 + 9 = 3 × 4). Если вместо 13 поставить число 5, ответ не изменится, хотя для числа 2 появится второй способ выбора подходящей пары чисел.

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

Входной файл содержит целое число N — размер таблицы, за которым далее следует N строк по N чисел A_ij.

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

Выходной файл должен содержать единственное целое число — количество элементов A_ij, для которых существуют p ≠ i, q ≠ j, такие что A_ij + A_iq = A_ij × A_pj.

Ограничения

1 ≤ N ≤ 500,

1 ≤ A_ij ≤ 10⁹

Описание подзадач и системы оценивания

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

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

2
2 2
2 2

4

4
2  8  12 4
5  6  7  1
9  10 11 3
13 14 15 16 

3

2
1000 1000
1000 1000

0

Задача E. Отрезок деревьев ≡

Условие

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

После просмотра нескольких документальных фильмов о природе, лесник Шон очень беспокоится о местонахождении деревьев в своём лесу. Дело в том, что в одном из таких фильмов деревья просто так взяли и ушли. Конечно это было необходимо из-за событий, которые происходили в фильме. Но Шон абсолютно уверен, что в реальности такие события не могут случиться по ряду обстоятельств. Поэтому он считает, что у деревьев в его лесу нет никакой уважительной причины, чтобы отлучаться. То есть деревьям нельзя просто так взять и уйти.

В текущий момент у Шона нет никакой информации о том, где растёт каждое из деревьев. Поэтому он не может с полной уверенностью сказать, что деревья в его лесу неподвижны.

Всего в лесу растёт N деревьев. Лес является непрерывным отрезком на прямой от 1 до L. Все деревья растут в разных целочисленных точках.

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

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

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

Сначала на вход программе-решению подаётся целое число L — длина леса.

Для каждого теста жюри зафиксировало числа N и K — количество деревьев и максимальное количество запросов на сканирование участка леса. Гарантируется, что K запросов достаточно, чтобы решить задачу. Эти числа не сообщаются программе-решению. Ограничения на N и K в различных подзадачах приведены в таблице системы оценивания. Если решение делает более K запросов к программе жюри, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы сделать запрос программа-решение должна вывести строку вида "? l r", где l и r (1 ≤ l ≤ r ≤ L) — целые числа, крайние левая и правая точка сканируемого участка леса. В ответ на запрос программа жюри подаёт на вход программе-решению либо строку "Yes", либо строку "No", в зависимости от того, есть ли хотя бы одно дерево в запрашиваемом участке.

Если программа-решение определила ответ на задачу, она должна вывести две строки: в первой "ok?", во второй N целых чисел — список точек, в которых растут деревья в порядке возрастания координат. После этого программа-решение должна завершиться.

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

После каждого запроса и вывода ответа необходимо выполнить сброс буфера. Например, в Pascal необходимо написать flush(output), в C++ — cout.flush().

Ограничения

1 ≤ N ≤ 10³

1 ≤ L ≤ 10⁹

1 ≤ x_i ≤ L

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

5

Yes

No

Yes

No


ok

? 1 5

? 1 2

? 3 3

? 4 5

ok?
3

6

Yes

No

Yes

No

Yes

Yes

Yes


ok

? 1 2

? 1 1

? 2 2

? 3 4

? 5 6

? 5 5

? 6 6

ok?
2 5 6

Задача F. Обработка картинок ≡

Условие

У юного программиста Васи есть младший брат Петя.

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

Тогда Вася решил найти сложную картинку и посоревноваться со своим младшим братом в нахождении геометрических фигур.

Картинка представляет из себя набор из N строк по M символов в каждом. Каждый символ может принимать значения с кодами от 33 до 126 в кодировке ASCII.

Петя и Вася решили искать на картинке ромбы специального вида. Контур таких ромбов можно задать уравнением |x − a| + |y − b| = r, где a  — номер столбца центра фигуры, b — номер строки центра фигуры, а r  — ее радиус. Фигура засчитывается только в том случае, если все клетки ее контура содержат один и тот же символ, а также не вылезают за границы картинки. Также не учитываются фигуры, радиус r которых равен 0.

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

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

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

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

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

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

Первая строка каждого теста содержит два целых числа N, M — размеры картинки.

Следующие N строк содержат M символов — описание картинки.

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

Выходной файл должен содержать T ответов на тесты. Каждый ответ состоит из одной или двух строк.

Первая строка содержит целое число K — количество ромбов на картинке. Вторая строка содержит K четверок a, b, r, c, разделенных пробелами, где целые числа a и b — строка и столбец центра ромба, целое число r — радиус ромба и c — символ, которым заполнен его контур. Четверки, описывающие каждый ромб, можно выводить в любом порядке.

В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с −1.

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

2
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1~A~A~1
1~~A~~1
1111111
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1BA~AB1
B~BAB~B
1B111B1

1
4 4 2 A
3
4 4 2 A 6 2 1 B 6 6 1 B