시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 13 | 6 | 6 | 46.154% |
In mathematics, a group, G, is an object that consists of a set of elements and an operator (which we will call ×) so that if x and y are in so is x × y. Operations also have the following properties:
Groups have a wide variety of applications including the modeling of quantum states of an atom and the moves in solving a Rubik’s cube puzzle. Clearly the integers under addition from a group (0 is the identity, and the inverse of x is -x, and you can prove associativity as an exercise), though that group is infinite and this problem will deal only with finite groups.
One simple example of a finite group is the integers modulo 10 under the operation addition. That is, the group consists of the integers 0, 1, ..., 9 and the operation is to add two keeping only the least significant digit. Here the identity is 0. This particular group has the property that x times; y = y times; x, but this is not always the case. Consider the group that consists of the elements a, b, c, d, e and i. The “multiplication table” below defines the operations. Note that each of the required properties is satisfied (associativity, identity and inverse) but, for example, c × d = a while d × c = b.
Your task is to write a program which will read a sequence of multiplication tables and determine whether each structure defined is a group.
The input will consist of a number of test cases. Each test case begins with an integer n (0 ≤ n ≤ 100). If the test case begins with n = 0, the program terminates. To simplify the input, we will use the integers 1, ..., n to represent n elements of the candidate group structure; the identity could be any of these (i.e., it is not necessarily the element 1). Following the number n in each test case are n lines of input, each containing n integers in the range [1, ..., n]. The qth integer on the pth line of this sequence is the value p × q.
If the object is a group, output yes (on its own line), otherwise output no (on its own line). You should not output anything for the test case where n = 0.
2 1 2 2 1 6 1 2 3 4 5 6 2 1 5 6 3 4 3 6 1 5 4 2 4 5 6 1 2 3 5 4 2 3 6 1 6 3 4 2 1 5 7 1 2 3 4 5 6 7 2 1 1 1 1 1 1 3 1 1 1 1 1 1 4 1 1 1 1 1 1 5 1 1 1 1 1 1 6 1 1 1 1 1 1 7 1 1 1 1 1 1 3 1 2 3 3 1 2 3 1 2 0
yes yes no no