Build, rather than read, a DFA: one state for each remainder.
What to build
A program that builds the remainder DFA for m and uses it to decide which binary words are divisible by m.
Requirements
- Print
states mfirst. - Then, for each word, print
acceptif its value is divisible by m, elsereject, by running the DFA, not by converting the whole word.
Input
Line 1: m. Line 2: n. Then n binary words (a word may be an empty line).
Output
states m, then n lines.
Constraints
1 ≤ m ≤ 9; words have at most 60 bits.
Example
Input:
3
4
110
111
1001
0
Output:
states 3
accept
reject
accept
accept
Why it works
Appending a bit doubles the value and adds the bit, so only the remainder needs to be remembered: m states suffice.
Examples
Example 1 · Input
3 4 110 111 1001 0
Expected output
states 3 accept reject accept accept
Example 2 · Input
2 3 10 11 0
Expected output
states 2 accept reject accept
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use the remainder as the state: reading bit b turns remainder r into (2r + b) mod m.
Hint 2
The empty word has value 0, which every m divides.
Solution
Show one correct solution (try it yourself first)
m = int(input())
delta = {(r, bit): (2 * r + int(bit)) % m for r in range(m) for bit in "01"}
print("states", m)
for _ in range(int(input())):
state = 0
for bit in input():
state = delta[(state, bit)]
print("accept" if state == 0 else "reject")