Темы
    Информатика(2656 задач)
---> 32 задач <---
Источники --> Личные олимпиады --> Международные олимпиады
    2005(6 задач)
    2006(6 задач)
    2007(6 задач)
    2008(6 задач)
    2009(8 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#3307
Teleporters
  
#111235
Чёрный ящик
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

В игре "Чёрный ящик" используется квадратный чёрный ящик, лежащий на столе. Каждая из его сторон имеет \(n\) отверстий, в каждое из \(4n\) которых можно запустить шарик, который через некоторое время вылетит обратно из одного из отверстий.

Внутренность коробки можно представить в виде сетки \(n \times n\). Отверстия ящика - это границы сетки. Каждая из ячеек сетки либо пуста, либо содержит отражатель

Отражатель - это стенка, направленная под углом 45 градусов к линиям сетки так, что при соударении шарика с отражателем он меняет направление своего полёта на 90 градусов.

Шарик, запущенный внутрь коробки, катится прямолинейно, пока либо он не вылетит из коробки, либо не встретится с отражателем. При попадании в отражатель он отскакивает от него (направление его полёта меняется на 90 градусов), а отражатель поворачивается на 90 градусов.

a) Шарик запущен в отверстие; он ударяется об отражатель и летит вниз.

b) После соударения с шариком отражатель инвертирует своё положение. Новый шарик запущен в чёрный ящик в то же отверстие, что и первый, и после соударения с отражателем он полетит вверх.

c) Отражатель меняет своё состояние после каждого соударения.

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

Коробка имеет две кнопки. Первая кнопка сбрасывает все отражатели - каждый отражатель возвращается в своё исходное положение. Вторая инвертирует все отражатели в коробке.

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

Входные данные

Сначала вам на вход подаётся одно целое число \(n (1 \leq n \leq 30)\). Далее процесс общения программы с чёрным ящиком устроен в форме "запрос-ответ". Возможные запросы:

\(1\) \(s\) \(h\) - после этого запроса запускается шар в отверстие, расположенное на стороне \(s\) (1 - верхняя сторона, 2 - правая сторона, 3 - нижняя сторона, 4 - левая сторона), и имеющее номер \(h (1 \leq h \leq n)\) (отверстия нумеруются сверху вниз и слева направо). Ваша программа должна считать три числа - \(c, s', h'\), разделённых пробелами, соответственно количество соударений и номер стороны и номер отверстия вылета в формате, описанном выше.

\(2\) - после этого запроса все отражатели сбрасываются.

\(3\) - после этого запроса все отражатели инвертируются

\(0\) - после этого запроса вы заканчиваете работу с чёрным ящиком и должны вывести содержимое коробки (см. пример для точного понимания формата).

Обратите внимание, что после каждого запроса вы должны вывести перевод строки и сбросить буфер вывода командой flush(output) в Паскале, fflush(stdout) (cout.flush()) на языках C/C++. В других языках достаточно вывести после команды перевод строки. Следуйте формату общения с чёрным ящиком с точностью до пробела.

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

Входные данные
3

1 4 3

1 1 3


3 1 2


4 2 3


0 3 1
Выходные данные

1 3 3

1 2 1

3
1 2 3

2
1 4 2

2
1 1 1

0
./\
./.
..\

Дополнительная информация

Решение жюри находит содержимое коробки на каждом тесте жюри не более чем за 1.8 секунды. Жюри не гарантируется существование решения на всех возможных тествах.

#111236
aliens
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мирко большой фанат различных узоров на полях, в первую очередь странных кругов предположительно инопланетного происхождения. Одной летней ночью он решил создать свой собственный узор на поле своей бабушки. Так как Мирко патриот своей родной Хорватии, то он решил, что узор на поле будет в форме хорватского герба, который, как известно, представляет собой шахматную доску 5 на 5 c 13 красными и 12 белыми квадратами.

Поле бабушки Мирко разделено на \(N\) рядов по \(N\) клеток в каждом. Левый нижний угол поля обозначается координатами \((1, 1)\), правый верхний - координатами \((N, N)\).

Мирко решил выкосить траву только на тех участках, которые соответствуют красным полям на шахматной доске. Он выбрал нечетное число \(M \geq 3\) и так выкосил траву на поле, что каждый квадрат на шахматной доске соответствует квадрату размером \(M \times M\) клеток на поле, и шахматная доска целиком умещается на поле.

На рисунке (см. английскую версию условия) показан пример поля для \(N = 19\) и \(M = 3\). Клетки, на которых трава была выкошена, отмечены серым. Центр узора имеет координаты \((12, 9)\) и отмечен черной точкой

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

Пришельцы нашли одну клетку с выкошенной травой и теперь хотят найти центральную клетку узора Мирко. Они не знают размера узора \(M\).

Входные данные

Напишите программу, которая по размеру поля \(N\) (\(1 \leq N \leq 2\,000\,000\,000\)), координатам некоторой клетки с выкошенной травой \((X_0, Y_0)\) и способности взаимодействовать с инопланетным устройством, найдет центральную клетку узора Мирко

На каждом тесте устройство не может быть запущено более 300 раз

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

  • При запуске программы ей будут введены разделенные пробелом числа \(N\), \(X_0\), \(Y_0\).
  • Для того, чтобы узнать есть ли трава в клетке \((X, Y)\) выведите на стандартный поток вывода строку "examine \(X\) \(Y\)". Если координаты \((X, Y)\) не будут находиться внутри поля или вы запустите устройство более 300 раз, то космический корабль потеряет управление и врежется в землю. Вы же в этом случае получите 0 баллов за тест.
  • Устройство поместит в ваш стандартный поток ввода строку "true", если трава в указанной клетке выкошена и "false" в противном случае.
  • Когда программа обнаружит центральную клетку, она должна вывести строку "solution \(X_c\) \(Y_c\)" на стандартный поток вывода. Выполнение вашей программы в этот момент будет автоматически завершено.

      • Для корректной работы вашей программы не забывайте вызывать функцию "flush" после каждого вывода данных. Её заменяет endl в С++, print в Python, writeln в Pascal.

Пример диалога
> 20 4 9
< examine 2 9
> false
< examine 3 9
> true
< examine 6 9
> false
< examine 5 9
> true
< examine 4 3
> true
< examine 2 3
> false
< examine 3 3
> true
< examine 3 1
> false
< examine 3 2
> true
< solution 10 9
#111237
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Ссылка на условие.
#111238
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Ссылка на условие.
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест