основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
IgorTuphanov
энтузиаст
*****

Рег.: 08/02/04
Сообщений: 104
Из: Vladivostok, Russia
SNSS3 - Задача F
      #11868 - 08/17/06 07:26 PM

Приведу условие задачи:
Code:
 

Компания DoubleVision проектирует чернила и шрифты, которые могут легко
читаться и людьми и машинами. Они проектируют свои шрифты на прямоугольной
сетке. Справа показан очень простой 5x3 проект для первых пяти цифр:

.o. .o. oo. oo. o.o
o.o .o. ..o ..o o.o
o.o .o. .o. oo. ooo
o.o .o. o.. ..o ..o
.o. .o. ooo oo. ..o

Чернила выглядят, как нормальные черные чернила, но под ними DoubleVision
добавляет специальный полимер, который может быть распознан инфракрасным
сканером. Человек видит черные чернила вместо полимера, а машина видит полимер
вместо черных чернил. Единственная проблема заключается в том, что полимер
гораздо дороже чернил, поэтому DoubleVision хочет использовать его как можно
меньше. Они обнаружили, что для большинства шрифтов, для того чтобы пометить
каждый символ единственным образом, достаточно не более двух пикселей
полимера. Но добавляя полимер к одному или двум пикселям на символ, они
решительно понижают затраты при обеспечении 100% точности в своих сканерах.
Показанный ниже шрифт отражает это: пиксели, которые определяют каждый символ
единственным образом, отмечены "#". (Имеются и другие варианты, которые
работали бы.) Вы должны написать программу, которая определяет, можно ли
данный шрифт пометить таким способом, и если это так, то пометить его.


.#. .o. #o. oo. o.#
#.o .#. ..o ..o o.o
o.o .o. .o. #o. ooo
o.o .o. #.. ..o ..o
.o. .o. ooo #o. ..o


Input

Входной файл начинается со строки, содержащей три положительных целых числа n,
r и c, разделенных пробелом: n - число символов в шрифте, r - число строк в
сетке, c - число столбцов в сетке. Следующие r строк содержат изображение
каждого символа в формате, используемом в примерах: точка "." означает не
закрашенную часть сетки, а малая "o" означает пиксель, смежные сетки отделяются
пробелом. Длина каждой строки не превышает 79 символов (не считая символа конца
строки), r не превышает 10.



Output

Для теста определяется, можно ли каждый символ пометить единственным образом
одним или двумя пикселями. Если нет, то выходной файл должен содержать строку с
единственным словом "impossible". В противном случае, в выходной файл выводится
шрифт в том же формате, что и входной, но помеченные пиксели отмечаются
символом "#".

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



Примеры:

3 2 2
oo oo .o
o. .o o.
Ответ:
impossible


3 2 2
oo oo .o
o. .o oo
Ответ:
#o #o .o
#. .# ##


5 5 3
.o. .o. oo. oo. o.o
o.o .o. ..o ..o o.o
o.o .o. .o. oo. ooo
o.o .o. o.. ..o ..o
.o. .o. ooo oo. ..o
Ответ:
.#. .o. #o. oo. o.#
#.o .#. ..o ..o o.o
o.o .o. .o. #o. ooo
o.o .o. #.. ..o ..o
.o. .o. ooo #o. ..o


1 2 4
.o..
...o
Ответ:
.#..
...o




Может быть, я один такой непонятливый, но меня очень смутили примеры и правило сравнения символов.
Я даже не говорю, про правило сравнения символов, а вот, например, почему в первом примере ответ impossible? Почему нельзя отметить одним пикселем все символы так: первый (1,1), второй (1,2), третий (2,1)?
Или еще подразумевается что-то такое, чего в условии не написано? Вращения? Смещения? Тогда все еще более непонятно.

А! Начинаю злиться, и поэтому заканчиваю пост.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Michael_Rybak
здесь был не раз
*****

Рег.: 07/09/06
Сообщений: 47
Из: Kyiv, Ukraine
Re: SNSS3 - Задача F [Re: IgorTuphanov]
      #11870 - 08/18/06 06:40 AM

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

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


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: SNSS3 - Задача F [Re: IgorTuphanov]
      #11871 - 08/18/06 09:52 AM

Ну да. Нужно выбрать 1-2 пикселя такие чтоб в остальных символах на этом месте ничего не было.
А вот правило сравнения пикселей меня тоже смутило. Из-за невероятно понятного объяснения этого правила я 6 ВА на дорешивании получил. А правило простое: сравниваются два пикселя: меньший первой пары пары меньше меньшего второй - первая пара меньше, если равны сравниваюится оставшиеся два. Сравниваются два пикселя так: если они на разных строчках то меньший тот который выше, если на одной то тот который левее.
А сама задача - самый убогий перебор.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
IgorTuphanov
энтузиаст
*****

Рег.: 08/02/04
Сообщений: 104
Из: Vladivostok, Russia
Re: SNSS3 - Задача F [Re: Michael_Rybak]
      #11872 - 08/18/06 03:36 PM

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

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 408 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 10553

Rate this topic

Переход в