시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 17 | 7 | 7 | 46.667% |
We are observing class declarations in an object-oriented programming language similar to C++. Each class declaration is of the form “K : P1 P2 . . . Pk ;” where K is the name of the new class being declared, and P1, P2, . . . , Pk the names of classes being inherited by class K. For example, “shape : ;
” is a declaration of class “shape
” that does not inherit any other class, whereas “square : shape rectangle ;
” is a declaration of class “square
” that inherits classes “shape
” and “rectangle
”.
If class K1 inherits class K2, class K2 inherits class K3, and so on, up to class Km−1 that inherits class Km, then we say that all classes K1, K2, . . . , Km−1 are derived from class Km. The rules of the programming language forbid circular definitions, so it is not allowed to have a class derived from itself. In other words, the class hierarchy forms a directed acyclic graph. Additionally, it is not allowed for a so-called diamond to appear in the class hierarchy. A diamond consists of four different classes A, B, X, Y such that it holds:
Figure 1: A diamond
Figure 2: The hierarchy after processing all declarations from the first sample test
You are given a series of class declarations to be processed sequentially, and determine for each one whether it is correctly declared. The correctly declared classes are added to the hierarchy, while the incorrect ones are discarded. Declaration “K : P1 P2 . . . Pk ;” is correctly declared if the following holds:
Write a programme that will process the declarations respectively as described above and determine the correctness of each one of them.
The first line of input contains the integer n – the number of declarations. Each of the following n lines contains a single declaration in the form of “K : P1 P2 . . . Pk ;” where P1, P2, . . . , Pk is a series of zero, one or more classes that class K inherits. All class names in a single declaration K, P1, P2, . . . , Pk are mutually different. Each class name is a string of at most 10 lower case letters of the English alphabet. All the elements of a declaration (the class names and characters “:
” and “;
”) are separated by exactly one space. In each specific declaration, for the number of classes k it holds 0 ≤ k ≤ 1 000.
You must output n lines. The ith line must contain “ok
” if the ith declaration is correct, and “greska
” if it isn’t.
번호 | 배점 | 제한 |
---|---|---|
1 | 13 | 1 ≤ n ≤ 100, the correctness can be determined by considering only condition 1. |
2 | 14 | 1 ≤ n ≤ 100, the correctness can be determined by considering only conditions 1 and 2. |
3 | 29 | 1 ≤ n ≤ 100. |
4 | 44 | 101 ≤ n ≤ 1 000. |
10 shape : ; rectangle : shape ; circle : shape ; circle : ; square : shape rectangle ; runnable : object ; object : ; runnable : object shape ; thread : runnable ; applet : square thread ;
ok ok ok greska ok greska ok ok ok greska
9 a : ; x : ; b : a x ; c : b ; d : a b c ; e : d a ; f : c e ; y : x ; g : c y e ;
ok ok ok ok ok ok ok ok greska
Clarification of the first example:
Clarification of the second example:
Olympiad > Croatian Highschool Competitions in Informatics > 2016 > Croatian Olympiad in Informatics 2016 1번