Status:  Past  Start:  20111201 14:00:00  End:  20111201 19:10:00 
The Caribbean Training Contest #29
Problem
1634  Automaton for Divisibility
Created by  UCI X GrundyPC Cup 
Added by  ymondelo20 (20111120) 
Limits 
Total Time: 2000 MS
Memory: 62 MB  Output: 64 MB  Size:
29 KB

Enabled languages  
Available in 
Description
One of the earliest computer models are finite automata, they solve many problems of computer science, computational model is a pattern recognizer languages and is considered a state machine, usually a finite automaton defined as a fivetuple {Σ, Q, F, f, q0}.
Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.
For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:
Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.
q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk1 = K1, remainder K1 on division by K.
Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K1) by 10 columns (symbols). If the element in row i column j of the matrix is x, then it means that being in the state i and reading input symbol j is then transits to the state x.
Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.
For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:
Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.
q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk1 = K1, remainder K1 on division by K.
Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K1) by 10 columns (symbols). If the element in row i column j of the matrix is x, then it means that being in the state i and reading input symbol j is then transits to the state x.
One of the earliest computer models are finite automata, they solve many problems of computer science, computational model is a pattern recognizer languages and is considered a state machine, usually a finite automaton defined as a fivetuple {Σ, Q, F, f, q0}.
Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.
For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:
Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.
q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk1 = K1, remainder K1 on division by K.
Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K1) by 10 columns (symbols). If the element in row i column j of the matrix is x, then it means that being in the state i and reading input symbol j is then transits to the state x.
Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.
For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:
Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.
q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk1 = K1, remainder K1 on division by K.
Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K1) by 10 columns (symbols). If the element in row i column j of the matrix is x, then it means that being in the state i and reading input symbol j is then transits to the state x.
One of the earliest computer models are finite automata, they solve many problems of computer science, computational model is a pattern recognizer languages and is considered a state machine, usually a finite automaton defined as a fivetuple {Σ, Q, F, f, q0}.
Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.
For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:
Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.
q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk1 = K1, remainder K1 on division by K.
Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K1) by 10 columns (symbols). If the element in row i column j of the matrix is x, then it means that being in the state i and reading input symbol j is then transits to the state x.
Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.
For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:
Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.
q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk1 = K1, remainder K1 on division by K.
Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K1) by 10 columns (symbols). If the element in row i column j of the matrix is x, then it means that being in the state i and reading input symbol j is then transits to the state x.
Input specification
In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).
Then will follow N lines with an integer number Ki (1 <= i <= N).
In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).
Then will follow N lines with an integer number Ki (1 <= i <= N).
In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).
Then will follow N lines with an integer number Ki (1 <= i <= N).
Output specification
For each case you should print the matrix (which represents the transition function) with Ki rows and 10 columns.
For each case you should print the matrix (which represents the transition function) with Ki rows and 10 columns.
In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).
Then will follow N lines with an integer number Ki (1 <= i <= N).
Sample input
1
2
Sample output
0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1
Hint(s)
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/