Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача H. Взаимное расположение

Задачу добавил: alef

Успешно сдано решений: 28

Ограничения: время на тест - 2с, память - 256 Мб

На планете в системе Антареса Василий познакомился с веселым студентом-историком Диего, который проходил стажировку в музее техники. Диего как раз изучал древние роботы-манипуляторы, и в визите Василия видел замечательную возможность испытать работу такого манипулятора на сборке ноутбука. Однако Василия эта идея совсем не приводила в восторг, он хотел забрать недостающие модули и отправиться на Землю. Диего был напорист, и Василий предложил следующее: он получает модули, а Диего демонстрирует ему работу своих манипуляторов на каком-нибудь образце. Если все проходит хорошо, тогда Василий соглашается доверить Диего сборку ноутбука.

Конечно, Василий был уверен, что все пройдет не слишком хорошо, а даже если и хорошо, то по ходу дела он придумает какое-нибудь возражение. Впрочем, юный Диего явно думал по другому и с радостью согласился. "А пожалуй, ему будет достаточно, если я просто похвалю его работу, - подумал Василий. - Он, наверное, старался, разбирался с этими роботами, а никто не сказал ему, как он хорошо с этим справился". Успокоенный этой мыслью, он направился за Диего, получил в руки большой пакет с самыми разнообразными модулями, которых явно хватило бы на десяток-другой ноутбуков и проследовал за ним в небольшую комнату. Диего переполняла гордость:
- Вот, я его собрал, подключил к нему устройство для изменения микропрограммы, даже нашел самые настоящие программы для него, которые использовались на заводах! Конечно, приходится экспериментировать с муляжами, но я их наловчился делать!

В качестве объекта эксперимента Диего использует прямоугольную доску размером 26 X 26, разбитую на квадратные клетки. В центре каждой клетки имеется штырек. Роль модулей выполняют параллелепипеды шириной в 1 клетку и длиной от 1 до 4 клеток с соответствующим количеством дырочек. Задача манипулятора - прочитать микропрограмму и установить параллелепипеды, надев их на штырьки. Каждая команда микропрограммы имеет вид <буква><число>-<буква><число> и задает позицию параллелепипеда на доске. Гарантируется, что каждая команда в отдельности является корректной записью. Однако для сборки ноутбука важно, чтобы в готовой сборке параллелепипеды не соприкасались ни сторонами, ни даже углами, и уж тем более не накладывались друг на друга.
Ваша задача состоит в том, чтобы по заданной микропрограмме определить, является ли она подходящей для сборки ноутбука.

Формат входного файла input.txt
Первая строка - целое число S (1 <= S <= 1000) - количество команд в микропрограмме
Каждая из следующих S строк содержит запись вида <буква><число>-<буква><число>
<буква> - строчная буква латинского алфавита в диапазоне от a до z
<число> - целое число от 1 до 26

Формат выходного файла output.txt
Первая строка - слово YES или NO - если программа является правильной и если не является
Вторая строка: если первая NO - номер первой команды, нарушающей правильность сборки, если первая - YES, то количество клеток на доске, которые еще могут быть задействованы для размещения параллелепипедов согласно описанным требованиям.

Пример входного файла - 1
4
b2-b2
a4-b4
d1-d4
f2-f4

Пример выходного файла - 1
YES
641

Пример входного файла - 2
6
b2-d2
b4-d4
f2-f4
e4-e4
h2-h4
j2-j4

Пример выходного файла - 2
NO
4

Пример входного файла - 3
4
a2-d2
d4-a4
f1-f4
h4-h1

Пример выходного файла - 3
YES
631

Пример входного файла - 4
7
b2-c2
e2-f2
b4-c4
e4-f4
d3-d3
d3-d3
d3-d3

Пример выходного файла - 4
NO
5

Сдать задачу

Задать вопрос жюри по этой задаче