ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Алгоритмы и структуры данных — 2019. Набор задач 7 > задача:


C. Captcha

Алгоритмы и структуры данных — 2019. Набор задач 7

Старт: 27.ноя.2020 в 08:00:00
Финиш: 11.дек.2021 в 08:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• Подсказки к задачам
• A. Граф
• B. Где ключи?
• C. Captcha
• D. Цикл
• E. Топологическая сортировка
• F. Самый сложный предмет
• G. Компоненты сильной связности
• H. Мосты

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Captcha
Captcha
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

В одном из наиболее популярных вариантов капчи нужно определить различные символы (например, цифры) на деформированном изображении. Ваша компания в настоящее время занимается созданием средства для обхода такой капчи. Часть работы уже сделана, а вам поручили реализовать распознавание цифр 7, 8 и 9.

Изображение цифры получено из одного из показанных выше оригинальных изображений (размера 80 × 80 пикселей) путём следующих преобразований:

  • Поворота на угол от 0 до 2π;
  • Скоса вдоль оси абсцисс с относительным смещением противоположных сторон от -100% до 100%;
  • Масштабирования вдоль осей абсцисс и ординат (независимо) с изменением размеров от 20% до 200%.

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

Гарантируется, что цифра на изображении может быть распознана однозначно.

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

Первая строка содержит целые числа N и M (10 ≤ N, M ≤ 200) — высоту и ширину изображения.

Следующие N строк содержат по M символов 'x' или '.', образующих изображение. Символы 'x' соответствуют закрашенным пикселям изображения, символы '.' — незакрашенным.

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

Выведите одно целое число — распознанную цифру.

Примеры

Входные данные
16 20
....................
...xxx..............
..xxxxxx............
..x...xxx...........
..xx...xxx..........
..xx.....x..........
...xx.....xxxx......
....xxx...xxxxxx....
.....xxxxxx..xxxx...
......xxxxx....xx...
.........x.x....xx..
...........xx....x..
............xxx..xx.
.............xxxxxx.
..............xxxx..
....................
Выходные данные
8
Входные данные
17 24
........................
.........xxx............
........xxxxxxxxx.......
........xxxxxxxxxx......
........x....xxxxx......
...............xx.......
..............xxx.......
..............xx........
.............xx.........
............xx..........
...........xxx..........
...........xx...........
..........xx............
.........xxx............
........xxx.............
........xx..............
........................
Выходные данные
7
Входные данные
12 20
....................
.........xxxxxxx....
........xxxx........
.......xxx..........
......xxxxx.........
.....xxx...xx.......
.....xx....xx.......
....xxx....xx.......
....xxx...xxx.......
.....x...xxx........
......xxxxx.........
....................
Выходные данные
9
Для отправки решений необходимо выполнить вход.

www.contester.ru