Автобус(#1058) Дождик(#1060)

#1059

Задача g6_1059: Электронные часы (II Всероссийская командная олимпиада по информатике)

Циферблат новых электронных часов, установленных на главном здании офиса фирмы Macrohard, состоит из 4 прямоугольных панелей, каждая из которых состоит из 6 рядов по 5 лампочек в каждом. Первые две панели отображают цифры, из которых складываются часы, а следующие две - минуты. (Если сейчас меньше 10 часов, первая панель отображает 0).
К сожалению, лампочки, установленные на панелях, были произведены компанией Sveta.Net, которая известна своим принципом "раньше перегорит - больше спрос", вследствие чего на следующий день люди, проходя мимо офиса компании, видели лишь некоторое подобие цифр, поскольку некоторые лампочки больше не горели.
Петя живет в доме, стоящем прямо напротив офиса компании Macrohard. В первый день после установки часов он зарисовал у себя в блокноте, как выглядят все цифры на панелях (панели однотипные, поэтому одна и та же цифра на различных панелях выглядит одинаково). Теперь Петя хочет узнать, можно ли по текущему изображению на часах однозначно определить, сколько сейчас времени. Помогите ему!
Формат входных данных
При тестировании этой задачи в каталоге, который будет текущим, когда будет запущена Ваша программа, будет находиться два файла. Файл digits.txt содержит 6 строк по 50 символов в каждой. Он будет одинаковым для всех тестов и будет совпадать с приведенным в примере. Вы также можете найти этот файл в каталоге o:\common. Содержимое файла digits.txt задает правильное написание цифр на панелях (первый прямоугольник символов задает число 0, следующий - 1, и т. д. до 9). Не горящая лампочка обозначается символом "." (точка), а горящая - "#" (диез).
Входной файл input.txt содержит 6 строк по 20 символов в каждой - текущее изображение на часах. Первый прямоугольник задает первую панель, следующий - вторую, следующий - третью и последний - четвертую.
Формат выходных данных
Если можно точно определить время, которое сейчас отображается на часах, выведите это время в формате hh:mm. Если время нельзя определить однозначно, выведите AMBIGUITY. Если же в часах точно сломалось еще что-то, например центральный процессор, который управляет лампочками, выведите ERROR.
Примеры
digits.txt

..##.....#..##..####.#..#.####..###.####..##...##.
.#..#...##.#..#....#.#..#.#....#.......#.#..#.#..#
.#..#..#.#....#...#..#..#.###..###....#...##..#..#
.#..#....#...#.....#.####....#.#..#..#...#..#..###
.#..#....#..#......#....#.#..#.#..#..#...#..#....#
..##.....#.####.###.....#..##...##...#....##..###.

input.txt			output.txt
..##..####.#..#.####    	23:45
....#....#..........
....#...#..#..#.###.
...#.....#.##......#
..#......#....#.#..#
.####..##.....#..#..

#.##.....#..##..####	ERROR
.#..#...##.#..#....#
.#.....#......#...#.
.#..#..............#
.#..#.......#......#
..##.....#.####.....

..##........##..####	AMBIGUITY
.#..#....#.#..#....#
.#............#...#.
.#..#..............#
.#..#.......#......#
..##.......####.....

Решение g6_1059: Предоставлено Андреем Станкевичем
Введем понятие "символ" как массив размера 6x5, в котором 1 соответствует горящей лампочке, а 0 - не горящей. Для двух символов A и B введем понятие их пересечения как массив C=A*B, где c[i][j] =a[i][j]*b[i][j]. Тогда верно следующее утверждение: чтобы символ A мог быть цифрой i, должно выполняться A*Di=A, где Di - символ, соответствующий каноническому написанию цифры i.
Помня также, что время лежит в диапазоне 00:00-23:59, получаем следующий алгоритм решения задачи: для каждого возможного времени проверить, может ли оно быть отображено сейчас на табло (для этого каждую цифру на табло надо сравнить с соответствующей канонической цифрой). После этого: если ровно одно время может быть отображено на табло, то это и есть ответ, если более чем одно, то ответ AMBIGUITY, в если ни одно время не подошло, то ответ ERROR.
Программа
Приведем процедуру проверки, что символ a может быть цифрой, содержащейся в символе b (в реализации для простоты не будем заменять . на 0, а # на 1, а оставим как есть):
type
    tdigit = array [1..6, 1..5] of char;

function check(a, b: tdigit): boolean;
var
    i, j: longint;
begin
    check := false;
    for i := 1 to 6 do
        for j := 1 to 5 do
            if (a[i][j] = '.') and (b[i][j] = '#') then
                exit;
    check := true;
end;
Теперь проверяем, какое время может быть на табло: часы и минуты, и выводим ответ:
    for i := 0 to 23 do
    begin
        if can[1][i div 10] and can[2][i mod 10] then
        begin
            inc(ch);
            hh := i;
        end;
    end;

    cm := 0;
    for i := 0 to 59 do
    begin
        if can[3][i div 10] and can[4][i mod 10] then
        begin
            inc(cm);
            mm := i;
        end;
    end;
    
    if (ch = 0) or (cm = 0) then
    begin
        writeln('ERROR');
    end 
    else if (ch = 1) and (cm = 1) then 
    begin
        writeln(hh div 10, hh mod 10, ':', 
            mm div 10, mm mod 10);
    end else begin
        writeln('AMBIGUITY');
    end;
Скачать тесты к задаче

Наверх