Страница: 1 2 >> Отображать по:
#40
Перекраска клеток
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

 

+

+

(4,3)

+

+

Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

  • закрасить клетку (i,j) в черный цвет.
  • для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.

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

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

Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 105), а затем сами команды. Команды записаны по одной в строке в следующем формате:

Colori j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).

1 ≤ i ≤ N, 1 ≤ j ≤ M.

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

На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо. Пример ниже некорректен, первое число "3" должно отсутствовать.

Оценка задачи

1 балл получат решения, верно работающие при N ≤ 20, M ≤ 500, K ≤ 1000.

Примеры
Входные данные
5 5 6
Color 4 2
Neighbors 4 3
Color 2 3
Color 3 3
Neighbors 4 3
Neighbors 5 1
Выходные данные
3
4
4 1
4 4
3 3
5 3
4
4 1
4 4
1 3
5 3
2
5 2
4 1
#45
Контейнеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида — во вторую стопку и т.д.

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

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

В первой строке задается одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число ki — количество контейнеров в стопке, а затем ki чисел — виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).

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

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

Оценка задачи

1 балл будут получать программы, верно работающие при следующих ограничениях: количество стопок не больше 10, в каждой стопке не более 10 контейнеров.

Комментарий к примеру:

Изначально в первой стопке лежат четыре контейнера — снизу контейнер с товаром первого вида, над ним — с товаром второго вида, над ним — третьего, и сверху — еще один контейнер с товаром второго вида.

Одна из правильных последовательностей действий (вместо ответа в примере задачи):

1 2
1 3
1 2

Примеры
Входные данные
3
4 1 2 3 2
0
0
Выходные данные
1
#412
Переключение между окнами
  
Источники: [ Командные олимпиады, ВКОШП, 2006, Задача J ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Дан список вызываемых программ (при вызове программы она добавляется в начало списка активных программ). Также могут осуществляться переключения между программами (задается номер программы в списке и она переходит в начало списка). Требуется вывести название первой программы из списка при каком-либо его изменении.

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

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

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

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

В первой строке вводится целое число n – количество действий пользователя ( 1\( le\)n\( le\)1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

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

Выведите  n строк – последовательность имен приложений, с которыми работал пользователь в порядке, в котором их окна становились активными.

Примеры
Входные данные
6
Run Mozilla Firefox
Run Free Pascal
Alt+Tab
Run Miranda IM
Alt+Tab+Tab
Alt+Tab+Tab+Tab
Выходные данные
Mozilla Firefox
Free Pascal
Mozilla Firefox
Miranda IM
Free Pascal
Free Pascal
#855
Сортировка вагонов
  
Необходимо упорядочить числа с помощью стека.

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).

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

Вводится число N — количество вагонов в поезде (1≤N≤2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:

  • если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число K (K≥1),
  • если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число K (K≥1).

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

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

Примеры

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

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

3

3 2 1

1 3

2 3

4

4 1 3 2

1 2

2 1

1 2

2 3

3

2 3 1

0
#869
Сортировка вагонов
  
Темы: [Стек]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Требуется определить, возможно ли сортировка последовательности чисел с помощью стека.

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.

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

Вводится число N — количество вагонов в поезде (1≤N≤100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

Примеры

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

Комментарии

3

3 2 1

YES

Надо весь поезд завезти в тупик, а затем целиком вывезти его на 2-й путь.

4

4 1 3 2

YES

Сначала надо в тупик завезти два вагона, один из которых оставит в тупике, а второй — вывезти на 2-й путь, после чего завезти в тупик еще два вагона и вывезти 3 вагона, стоящие в тупике, на 2-й путь

3

2 3 1

NO

 
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест