Сломанные сегменты на табло

В подъезде стоит старое электронное табло с 7 сегментами (как на калькуляторе). Сегменты подписаны буквами a b c d e f g.

Некоторые сегменты сломаны и никогда не загораются. Известно, что сломано ровно k сегментов.

Ты посмотрел на табло в момент, когда на нём была показана одна цифра от 0 до 9, и выписал, какие сегменты горели. Остальные сегменты в этот момент не горели (либо потому что не нужны для этой цифры, либо потому что сломаны).

Нужно понять, сколько разных цифр могли быть показаны.

Набор сегментов для цифр:

• 0: a b c e f g
• 1: c f
• 2: a c d e g
• 3: a c d f g
• 4: b c d f
• 5: a b d f g
• 6: a b d e f g
• 7: a c f
• 8: a b c d e f g
• 9: a b c d f g

Формат ввода

В первой строке дано целое число k — сколько сегментов сломано. Во второй строке дана строка s — какие сегменты горели при наблюдении. Это строка из разных букв из множества {a,b,c,d,e,f,g} в произвольном порядке. Если не горело ни одного сегмента, то во второй строке стоит один символ -.

Формат вывода

Выведите одно число — сколько цифр от 0 до 9 могут соответствовать наблюдению.

Ограничения

• 0 ≤ k ≤ 7
• во второй строке: либо -, либо от 1 до 7 разных букв из {a,b,c,d,e,f,g}

Пример

Ввод:

2
cf

Вывод:

3

Ключевое наблюдение: если сегмент горит, он точно не сломан. А если сегмент должен гореть у выбранной цифры, но не горит в наблюдении, то он обязан быть сломан (иначе бы загорелся).

Удобнее работать с множествами букв. Для каждой цифры заранее известен набор сегментов T, которые она пытается зажечь. Наблюдение — это множество seen (если во входе -, то seen = пустое).

Проверка цифры сводится к двум условиям: 1) Нельзя, чтобы горел сегмент, которого у цифры вообще нет: нужно seen ⊆ T. 2) Все «пропавшие» сегменты из T обязаны быть сломаны. Их число need_broken = |T - seen|. Тогда цифра возможна, если need_broken <= k (оставшиеся сломанные сегменты могут быть среди тех, которые эта цифра и так не использует).

План:

• Прочитать k и строку s, собрать seen (особый случай s == '-').
• Задать таблицу из 10 множеств T для цифр.
• Для каждой цифры:
• если seen не подмножество T, пропустить;
• посчитать need_broken = len(T - seen) и сравнить с k.
• Посчитать, сколько цифр прошло проверку.

Сложность: перебор 10 цифр, операции над множествами из 7 букв — фактически O(1).

Частая ошибка: забыть, что - означает «ничего не горело», то есть seen должно быть пустым множеством, а не множество из символа '-'.