제19회

한국정보올림피아드

문     제

카드 게임

제18회 한국 정보올림피아드 (2001.7.7) 초등부 문제 1

제19회 한국 정보올림피아드 (2002.7.6) 초등부 문제 1

운재는 오늘 재미있는 카드 게임을 배우고 있다. 카드는 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있고, 색깔별로 1부터 9까지 숫자가 쓰여진 카드가 9장씩 있다. 카드는 모두 36(=4×9)장이다. 운재가 배운 카드 게임은 36장의 카드에서 5장을 뽑고, 아래와 같은 규칙으로 점수를 계산하는 것이다.

각 카드는 다음과 같이 나타낸다. 카드의 색깔은 영어 대문자 R, B, Y, G로 나타내는데, R은 빨간색, B는 파란색, Y는 노란색, G는 녹색을 뜻한다. 예를 들어서 Y8은 노란색 8을 나타내고, B5는 파란색 5를 나타낸다.

<점수를 정하는 규칙>

① 카드 5장이 모두 같은 색이면서 숫자가 연속적일 때, 점수는 가장 높은 숫자에 900을 더한다. 예를 들어, 카드가 Y4, Y3, Y2, Y5, Y6일 때 점수는 906(=6+900)점이다.

② 카드 5장 중 4장의 숫자가 같을 때 점수는 같은 숫자에 800을 더한다. 예를 들어, 카드가 B3, R3, B7, Y3, G3 일 때 점수는 803(=3+800)점이다.

③ 카드 5장 중 3장의 숫자가 같고 나머지 2장도 숫자가 같을 때 점수는 3장이 같은 숫자에 10을 곱하고 2장이 같은 숫자를 더한 다음 700을 더한다. 예를 들어, 카드가 R5, Y5, G7, B5, Y7일 때 점수는 757(=5×10+7+700)점이다.

④ 5장의 카드 색깔이 모두 같을 때 점수는 가장 높은 숫자에 600을 더한다. 예를 들어, 카드가 Y3, Y4, Y8, Y6, Y7일 때 점수는 608(=8+600)점이다.

⑤ 카드 5장의 숫자가 연속적일 때 점수는 가장 높은 숫자에 500을 더한다. 예를 들어, 카드가 R7, R8, G9, Y6, B5일 때 점수는 509(=9+500)점이다.

⑥ 카드 5장 중 3장의 숫자가 같을 때 점수는 같은 숫자에 400을 더한다. 예를 들어 R7, Y7, R2, G7, R5 일 때 점수는 407(=7+400)점이다.

⑦ 카드 5장 중 2장의 숫자가 같고 또 다른 2장의 숫자가 같을 때 점수는 같은 숫자 중 큰 숫자에 10을 곱하고 같은 숫자 중 작은 숫자를 더한 다음 300을 더한다. 예를 들어, R5, Y5, Y4, G9, B4일 때 점수는 354(=5×10+4+300)점이다.

⑧ 카드 5장 중 2장의 숫자가 같을 때 점수는 같은 숫자에 200을 더한다. 예를 들어, R5, Y2, B5, B3, G4일 때 점수는 205(=5+200)점이다.

⑨ 위의 어떤 경우에도 해당하지 않을 때 점수는 가장 큰 숫자에 100을 더한다. 예를 들어, R1, R2, B4, B8, Y5일 때 점수는 108(=8+100)점이다.

입력으로 카드 5장이 주어질 때, 카드 게임의 점수를 구하는 프로그램을 작성하시오. 두 가지 이상의 규칙을 적용할 수 있는 경우에는 가장 높은 점수가 카드 게임의 점수이다.

실행파일의 이름은 AA.EXE로 하고, 프로그램의 실행시간은 5초를 넘을 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄부터 다섯째 줄까지 한 줄에 카드 하나씩 입력된다. 카드의 색깔과 숫자 사이에는 빈 칸이 하나 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 한 줄에 입력으로 주어진 카드의 점수를 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

B 3

B 7

R 1

B 2

Y 7

출력(OUTPUT.TXT)

207

삼각형 만들기

제19회 한국 정보올림피아드 (2002.7.6) 초등부 문제 2

같은 길이의 성냥개비가 여러 개 주어져 있다. 이것들을 평면에 늘어놓아서 삼각형을 만들려고 한다. 삼각형의 한 변은 여러 개의 성냥개비를 직선으로 이어서 만들 수 있지만, 성냥개비를 꺾거나 잘라서 변의 한 부분을 만들 수는 없다. 성냥개비의 개수가 주어졌을 때, 이들 성냥개비를 사용하여 만들 수 있는 서로 다른 삼각형의 개수를 구하는 프로그램을 작성하시오.

예를 들어서 9개의 성냥개비로 만들 수 있는 서로 다른 삼각형은 그림 1과 같이 3 가지이다.

주의사항

(1) 주어진 성냥개비는 모두 사용하여 하나의 삼각형을 만들어야 한다.

(2) 삼각형을 한 개도 만들 수 없으면 0을 출력한다. 예를 들어서, 주어진 성냥개비의 개수가 1, 2, 또는 4인 경우에는 삼각형을 한 개도 만들 수 없다.

(3) 합동인 삼각형들은 같은 삼각형으로 본다. 예를 들어서 성냥개비 5개를 사용하여 만들 수 있는 그림 2의 삼각형들은 같은 삼각형으로 본다.

그림 2

실행파일의 이름은 BB.EXE로 하고, 프로그램의 실행시간은 2초를 넘을 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에 성냥개비의 개수가 주어진다. 성냥개비의 개수는 1 이상 50,000 이하이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 만들 수 있는 삼각형의 개수를 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

9

출력(OUTPUT.TXT)

3

음악 프로그램

제19회 한국 정보올림피아드 (2002.7.6) 중등부 문제 2

인터넷 방송 KOI (Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 □뮤직 KOI'에서 가수들의 출연 순서를 정하는 일이 골치 아프다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.

그래서 오늘 출연 예정인 여섯 팀의 가수들에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수들의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.

1 4 3

6 2 5 4

2 3

첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정해 왔다. 한 가수를 여러 보조 PD들이 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 정해 왔다.

남일이가 할 일은 이 순서들을 모아서 전체 가수들의 순서를 정하는 것이다. 남일이가 잠시 생각을 하더니 6 2 1 5 4 3으로 순서를 정했다. 이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다. 물론, 1 6 2 5 4 3으로 전체 순서를 정해도 괜찮다.

경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다. 예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다.

이번에 남일이는 우리 나라의 월드컵  4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다. 이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.

보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수들의 순서를 정하는 프로그램을 작성하시오.

실행파일의 이름은 MUSIC.EXE로 하고, 프로그램의 실행시간은 3초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일명은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 가수들의 수 [eqn: N]과 보조 PD들의 수 [eqn: M`]이 주어진다. 가수들은 번호 [eqn: 1,2, ldots ,N`]으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고 그 뒤로는 그 가수들의 순서가 나온다. [eqn: N]은 1이상 1,000이하의 정수이고, [eqn: M]은 1이상 100이하의 정수이다.

출력 형식

출력 파일명은 OUTPUT.TXT로 한다. 출력은 [eqn: N`]개의 줄로 이뤄지며, 한 줄에 하나의 번호를 출력한다. 이들은 남일이가 정한 가수들의 출연 순서를 나타낸다. 답이 여럿일 경우에는 아무거나 하나를 출력한다. 만약 남일이가 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

6 3

3 1 4 3

4 6 2 5 4

2 2 3

출력(OUTPUT.TXT)

6

2

1

5

4

3

동전 바꿔주기

제19회 한국 정보올림피아드 (2002.7.6) 중등부 문제 3

명보네 동네 가게의 현금 출납기에는 [eqn: k] 가지 동전이 각각 [eqn: n_1], [eqn: n_2], [eqn: ldots] ,[eqn: n_k]개 씩 들어있다. 가게 주인은 명보에게 [eqn: T]원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다.

예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

[eqn: 20 = 10 times 2]

[eqn: 20 = 10 times 1 + 5 times 2]

[eqn: 20 = 10 times 1 + 5 times 1 + 1 times 5]

[eqn: 20 = 5 times 3 + 1 times 5]

입력으로 지폐의 금액 [eqn: T], 동전의 가지 수 [eqn: k], 각 동전 하나의 금액 [eqn: p_i]와 개수 [eqn: n_i]가 주어질 때 [eqn: (i=1,2, ldots,k`)] 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 [eqn: 2^31]을 초과하지 않는 것으로 가정한다.

실행 파일의 이름은 COIN.EXE로 하고, 프로그램의 실행시간은 3초를 초과할 수 없다. 부분 점수는 없다.

입력형식

입력 파일명은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 지폐의 금액 [eqn: T] [eqn: (0 < T <= 10,000)], 둘째 줄에는 동전의 가지 수 [eqn: k][eqn: (0 < k <= 100)], 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 [eqn: p_i][eqn: (0 < p_i <=T)]와 개수 [eqn: n_i][eqn: (0 < n_i <= 1,000)]가 주어진다. [eqn: p_i]와 [eqn: n_i] 사이에는 빈칸이 하나씩 있다.

출력형식

출력 파일명은 OUTPUT.TXT로 한다. 첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

20

3

5 3

10 2

1 5

출력(OUTPUT.TXT)

4

DNA 유사도

제19회 한국 정보올림피아드 (2002.7.6) 중등부 문제 1

모든 생물의 DNA 서열은 A, C, G, T 네 개의 문자로만 표현된다. 한 DNA 서열에서 두 문자의 거리는 두 문자 사이에 있는 문자들의 개수이다. DNA 서열의 부분서열은 DNA 서열에서 몇 개의 문자를 제거하여 얻을 수 있는 서열을 말한다. 예로 DNA 서열 AGTCAC에서 두 번째 문자 G와 다섯 번째 문자 A의 사이에는 두 개의 문자 □TC□가 있기 때문에 이 두 문자의 거리는 2이다. 또한 이 DNA 서열에서 세 번째 문자 T와 네 번째 문자 C를 제거하면 부분서열 AGAC를 얻을 수 있다.

K가 0 이상인 정수일 때, K-부분서열이란 부분서열에서 이웃한 모든 두 문자가 원래 DNA 서열에서 거리가 최대 K인 부분서열이다. DNA 서열 AGTCAC의 부분서열 AGAC에서 인접한 두 문자인, 두 번째 문자 G와 세 번째 문자 A는 원래 DNA 서열에서 각각 두 번째와 다섯 번째 문자이고 두 문자 사이에는 두 개의 문자 □TC□가 있으므로 AGCATA의 1-부분서열이 될 수 없으나 2-부분서열은 된다.

두 DNA 서열이 얼마나 비슷한가를 측정하기 위하여 사용하는 방법 중에 하나는 최장 공통 K-부분서열을 찾는 것이다. (놀랍게도 인간과 쥐의 DNA 서열은 90%이상이 동일하다고 한다.) 두 DNA 서열의 최장 공통 K-부분서열이란 두 서열에서 모두 얻을 수 있는 동일한 K-부분서열 중, 가장 길이가 긴 부분서열을 말한다. 최장 공통 K-부분서열은 여러 개 있을 수 있다.

예를 들어서, 위 그림과 같이 두 DNA 서열 AGTCAC와 GATGAGAC가 주어진 경우, AGAC는 최장 공통 2-부분서열은 되지만, 1-부분서열은 될 수 없다. 왜냐하면 DNA 서열 AGTCAC에서 2번째 문자인 G와 5번째 문자인 A사이에 두 개의 문자 □TC□가 있기 때문이다. GTAC도 최장 공통 2-부분서열이다. 최장 공통 1-부분서열은 AGC, GTA, ATA 세 개가 된다. 이 세 개를 사전식(dictionary) 순서로 나열하면  AGC, ATA, GTA가 된다.

두 DNA 서열과 K가 주어진 경우 두 서열의 최장 공통 K-부분서열을 찾는 프로그램을 작성하시오.

실행파일의 이름은 DNA.EXE로 하고, 프로그램의 실행시간은 5초를 초과할 수 없다. 부분점수는 없다.

입력 형식

입력 파일명은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 K (0[eqn: <=]K[eqn: <=]30)가 입력된다. 둘째 줄에는 첫째 DNA 서열의 길이를 나타내는 정수가 입력된다. DNA 서열의 길이는 1,000이하이다. 셋째 줄에는 첫째 DNA 서열이 주어진다. 넷째 줄에는 둘째 DNA 서열의 길이를 나타내는 정수가 주어진다. 다섯 번째 줄에는 둘째 DNA 서열이 주어진다. 단, DNA 서열을 나타내는 문자들 사이에 공백은 없다.

출력 형식

출력 파일명은 OUTPUT.TXT로 한다. 출력 파일은 한 줄로 구성되며 주어진 두 DNA 서열의 최장 공통 K-부분서열을 출력한다. 답이 여러 개이면 사전식 순서로 가장 앞에 있는 서열을 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

1

6

AGTCAC

8

GATGAGAC

출력(OUTPUT.TXT)

AGC

경로 찾기

제19회 한국 정보올림피아드 (2002.7.6) 고등부 문제 1

N[eqn: times]N 이차원 배열 A가 있고 A의 각 원소는 -100부터 100 사이의 임의의 정수 값을 갖는다. 이 이차원 배열의 A[1][1]부터 시작하여 인접한 원소들을 방문해 가면서 A[N][N]에 이르는 경로를 선택하려 하는데 아래와 같은 제약 조건이 있다.

1. 위쪽으로는 이동할 수 없고 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있다.

2. 한 번 방문한 원소는 다시 방문할 수 없다.

이러한 제약을 만족하면서 임의의 경로를 따라 A[N][N]에 이르면 이 경로 상에 방문되었던 원소들의 값의 총합이 그 경로의 점수가 된다. 임의의 N[eqn: times]N 이차원 배열이 주어질 때, A[1][1]에서 A[N][N]에 이르는 경로 중 가장 점수가 높은 경로의 점수를 찾는 프로그램을 작성하시오.

<그림 1>은 N=5인 경우 가능한 경로들의 예이다. 왼쪽 그림과 같이 원소들을 방문하는 경우 그 점수는 319가 되고, 오른쪽 그림과 같이 원소들을 방문하는 경우 그 점수는 145가 된다.

10	25	7	8	13
68	24	-78	63	32
12	-69	100	-29	-25
-16	-22	-57	-33	99
7	-76	-11	77	15

10	25	7	8	13
68	24	-78	63	32
12	-69	100	-29	-25
-16	-22	-57	-33	99
7	-76	-11	77	15

<그림 1> 가능한 경로들의 예

<그림 2>는 제약조건을 만족하지 못하는 경로들의 예이다. 첫 번째 예는 위쪽으로 이동함으로써 제약 조건을 어긴 것이고, 두 번째 예는 한 번 방문한 원소를 다시 방문함으로써 제약 조건을 만족하지 못한다.

10	25	7	8	13
68	24	-78	63	32
12	-69	100	-29	-25
-16	-22	-57	-33	99
7	-76	-11	77	15

10	25	7	8	13
68	24	-78	63	32
12	-69	100	-29	-25
-16	-22	-57	-33	99
7	-76	-11	77	15

<그림 2> 부적합한 경로들의 예

실행 파일의 이름은 PATH.EXE로 하고 실행시간은 5초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에는 이차원 배열의 크기를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 다음 N개의 줄에는 각각의 N개의 정수(-100이상 100이하)가 주어진다. 둘째 줄에는 A[1][1]∼A[1][N], 셋째 줄에는 A[2][1]∼A[2][N], …… , N+1번째 줄에는 A[N][1]∼A[N][N]의 값이 주어진다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫 번째 줄에 가장 점수가 높은 경로의 점수를 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

5

10 25 7 8 13

68 24 -78 63 32

12 -69 100 -29 -25

-16 -22 -57 -33 99

7 -76 -11 77 15

출력(OUTPUT.TXT)

319

헬기 착륙장

제19회 한국 정보올림피아드 (2002.7.6) 고등부 문제 2

바다 위에 N개의 섬이 있고, 이 섬들에는 사람들이 살고 있다. 이곳 사람들은 혹시 있을지도 모를 응급 환자들을 위해 병원을 건설하기로 했는데, 각 섬마다 병원을 세우기에는 비용이 너무 많이 들기 때문에 이 섬들의 중간 지점쯤(바다 위 나 섬 위 모두 가능) 한 곳에 병원과 헬기 착륙장을 건설하기로 하였다. 멀리 있는 응급 환자를 빨리 수송해야 하므로 이 헬기 착륙장의 위치는 착륙장으로부터 각 섬까지의 직선 거리들 중에서 최대가 되는 거리를 제일 작게 하려고 한다. 이러한 조건을 만족하는 헬기 착륙장의 위치와 이 착륙장으로부터 가장 멀리 떨어져 있는 섬까지의 거리를 구하는 프로그램을 작성하시오.

실행 파일의 이름은  HEL.EXE로 하고 실행 시간은 10초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 문제를 간단히 하기 위해서 섬의 크기는 무시하고, 섬의 위치를 2차원 정수 좌표로 표시한다. 입력 자료의 첫 줄은 섬의 개수를 나타내는 정수 N(2≤N≤1,000)이다. 그 다음 N개의 줄은 각 줄마다 섬의  x 좌표값, y 좌표값이 각각 정수로 주어지는데, 각 좌표값의 범위는 -30,000 부터 30,000 까지이다.

※ 참고사항

세 점 [eqn: (x sub 1 , y sub 1 ), (x sub 2 , y sub 2 ), (x sub 3 , y sub 3 )]를 지나는 외접원의 중심(외심) (x, y)의 좌표는 아래와 같다.

[eqn: x = - { (x sub 2 sup 2 - x sub 1 sup 2 + y sub 2 sup 2 - y sub 1 sup 2 )(y sub 3 - y sub 2 )-(x sub 2 sup 2 - x sub 3 sup 2 + y sub 2 sup 2 - y sub 3 sup 2 )(y sub 1 - y sub 2 )} over {2(x sub 1 - x sub 2 )(y sub 3 - y sub 2 )-2(x sub 3 - x sub 2 )(y sub 1 - y sub 2 ) }]

[eqn: y = - { (y sub 2 sup 2 - y sub 1 sup 2 + x sub 2 sup 2 - x sub 1 sup 2 )(x sub 3 - x sub 2 )-(y sub 2 sup 2 - y sub 3 sup 2 + x sub 2 sup 2 - x sub 3 sup 2 )(x sub 1 - x sub 2 )} over {2(y sub 1 - y sub 2 )(x sub 3 - x sub 2 )-2(y sub 3 - y sub 2 )(x sub 1 - x sub 2 ) }]

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫 번째 줄에 헬기 착륙장의 위치를 x 좌표, y 좌표 순서로 출력하고, 두 번째 줄에 착륙장으로부터 가장 멀리 떨어져 있는 섬까지의 거리를 출력한다. 단, 각 좌표값과 거리는 소수점 이하 넷째 자리에서 반올림하여 셋째 자리까지 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

5

5 -2

-3 -2

-2 5

1 6

0 2

출력(OUTPUT.TXT)

1.000 1.000

5.000

트리 회전

0-2 이진트리(binary tree)는 다음과 같이 정의된다.

(1) 항상 루트노드(root node)가 지정되어 있다.

(2) 모든 내부노드(internal node)는 반드시 두 개의 자식노드(child node)를 가지며, 왼쪽 자식노드와 오른쪽 자식노드를 구분한다.

이러한 0-2 이진트리의 루트노드 혹은 루트노드의 오른쪽 자식노드에서 좌회전 연산과 우회전 연산은 아래 <그림 1>과 같이 표현된다.

(a)

(b)

<그림 1>

<그림 1-(a)> 이진트리의 노드 'a'에서 좌회전 연산은

(1) 노드 'a'의 자리에 노드 'b'를 위치하게 하고,

(2) 노드 'a'를 노드 'b'의 왼쪽 자식노드로 만들며,

(3) 노드 'b'의 왼쪽 부트리(subtree) T2를 노드 'a'의 오른쪽 부트리로 만든다.

<그림 1-(a)> 트리의 노드 'a'에 좌회전 연산을 적용하면 <그림 1-(b)> 이진트리로 변환된다.

이와 유사하게 우회전 연산을 정의할 수 있다. 위 <그림 1-(b)> 이진트리의 노드 'b'에서 우회전 연산은

(1) 노드 'b'의 자리에 노드 'a'를 위치하게 하고,

(2) 노드 'b'를 노드 'a'의 오른쪽 자식노드로 만들며,

(3) 노드 'a'의 오른쪽 부트리 T2를 노드 'b'의 왼쪽 부트리로 만든다.

<그림 1-(b)> 트리의 노드 'b'에 우회전 연산을 적용하면 <그림 1-(a)> 이진트리로 변환된다.

같은 개수의 노드를 가지는 두 개의 0-2 이진트리가 있을 때, 이 두 이진트리의 회전거리는 한 트리의 루트노드 혹은 루트노드의 오른쪽 자식노드에 좌회전 혹은 우회전 연산을 적용하여 다른 트리로 만드는 회전연산의 최소 회수를 나타낸다.

예를 들면, 다음 쪽의 <그림 2-(a)> 트리를 <그림 2-(g)> 트리로 변환하기 위해서는 <그림 2>에서와 같이 6번의 좌/우회전 연산을 적용하면 된다. 또한 6번 이하 회수의 회전 연산을 사용하여서는 변환할 수 없으므로, 두 트리 사이의 회전거리는 6이다.

두 개의 0-2 이진트리가 주어졌을 때, 두 트리 사이의 회전거리를 계산하는 프로그램을 작성하시오.

실행 파일의 이름은  TREE.EXE로 하고 실행시간은 10초를 초과할 수 없다. 부분 점수는 회전거리에 따라 적절하게 주어진다.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

그림 2

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 번째 줄에는 입력되는 두 트리의 노드 개수를 나타내는 정수 N(5≤N≤300)이 주어지며, 각 노드는 1번 부터 N번까지 번호가 부여된다.

두 번째 줄부터 다음 N개의 줄에는 첫 번째 트리의 구조를 나타내는 데이터가 입력된다. 각 줄에는 세 개의 정수가 주어지는데, 두 번째, 세 번째 정수가 나타내는 노드들은 각각 첫 번째 정수가 나타내는 노드의 왼쪽, 오른쪽 자식임을 나타낸다. 첫 번째 정수가 나타내는 노드가 단말 노드(terminal node)인 경우에는, 두 번째, 세 번째 정수는 모두 0이다. 루트노드의 번호는 항상 1번으로 주어지며, 각 줄은 첫 번째 정수가 1부터 N까지 증가하는 순으로 입력된다.

다음 N개의 줄에는 두 번째 트리의 구조를 나타내는 데이터가 첫 번째 트리의 구조를 나타내는 데이터와 같은 형식으로 입력된다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫 번째 줄에 입력되는 두 트리의 회전거리를 나타내는 정수 M을 출력한다. 다음 M개의 줄에는 첫 번째 트리를 두 번째 트리로 변환하는 회전연산에 관한 정보를 회전하는 순서대로 출력한다.

회전정보는 두 개의 문자로 표시한다. 첫 번째 문자는 회전하는 노드를 나타내며, 루트노드에서 회전하는 경우에는 'T'로, 루트노드의 오른쪽 자식노드에서 회전하는 경우에는 'C'로 표시한다.  두 번째 문자는 회전하는 방향을 나타내며, 좌회전 연산은 'L'로, 우회전 연산은 'R'로 표시한다.두 문자 사이에는 공백이 없다.

같은 회전거리를 가지는 회전변환 방법이 여러 가지인 경우는 그 중에서 한 가지 경우만을 출력한다. 입력되는 두 트리가 회전연산을 적용하여 서로 변환될 수 없는 경우에는 첫 번째 줄에 -1을 출력한다.

입력과 출력의 예

입력(INPUT.TXT)

11

1 2 3

2 0 0

3 4 5

4 6 7

5 8 9

6 0 0

7 0 0

8 0 0

9 10 11

10 0 0

11 0 0

1 2 3

2 4 5

3 6 7

4 0 0

5 0 0

6 8 9

7 0 0

8 0 0

9 10 11

10 0 0

11 0 0

출력(OUTPUT.TXT)

6

CR

TL

TL

CL

TR

CL

제19회

한국정보올림피아드

모범 풀이 프로그램

1. AA

제19회 한국 정보올림피아드 (2001.7.7) 초등부  문제풀이

program E1_Card;

{$APPTYPE CONSOLE}

var

Card : array [1..5] of integer;

Number : array [1..9] of integer;

AccNumber : array [-3..9] of integer;

Color : array [1..4] of integer;

MaxScore : Integer;

procedure Input;

var

f:text;

i:integer;

j:integer;

c:char;

begin

assign(f,'input.txt');

reset(f);

for i:=1 to 5 do

begin

repeat

read(f,c);

until c in ['R', 'Y', 'B', 'G'];

case c of

'R': j:=1;

'B': j:=2;

'Y': j:=3;

'G': j:=4;

end;

inc(Color[j]);

readln(f,j);

inc(Number[j]);

end;

for i:=1 to 9 do

if Number[i]>0 then

for j:=-4 to 0 do

inc(AccNumber[i + j]);

close(f);

end;

procedure ChangeScore(v:Integer);

begin

if MaxScore<v then  MaxScore:=v;

end;

procedure CheckScore;

var

Flash : Boolean;

Straight : Boolean;

Four : Boolean;

FourN : Integer;

Three : Boolean;

ThreeN : Integer;

Two : Boolean;

TwoN : Integer;

Two2 : Boolean;

Two2N : Integer;

MaxN : Integer;

i:integer;

begin

Flash := false; Straight := false; Four := false; Three := false;

Two := false; Two2 := false;

for i:=9 downto 1 do

if Number[i]<>0 then

begin

MaxN := i;

break;

end;

for i:=1 to 4 do

if Color[i]=5 then

Flash := True;

for i:=1 to 9 do

begin

if AccNumber[i]=5 then

Straight := True;

if Number[i]=4 then

begin

Four := True;

FourN := i;

end

else if Number[i]=3 then

begin

Three := True;

ThreeN := i;

end

else if Number[i]=2 then

begin

if Two then

begin

Two2 := True;

Two2N := i;

end

else

begin

Two := True;

TwoN := i;

end

end;

end;

if Flash and Straight then ChangeScore(MaxN + 900);

if Four               then ChangeScore(FourN + 800);

if Three and Two      then ChangeScore(ThreeN * 10 + TwoN + 700);

if Flash              then ChangeScore(MaxN + 600);

if Straight           then ChangeScore(MaxN + 500);

if Three              then ChangeScore(ThreeN + 400);

if Two and Two2       then ChangeScore(TwoN+Two2N*10+300)

else if Two           then ChangeScore(TwoN + 200);

ChangeScore(MaxN+100);

end;

procedure Output;

var

f:text;

begin

assign(f,'output.txt');

rewrite(f);

writeln(f,MaxScore);

close(f);

end;

begin

Input;

CheckScore;

Output;

end.

2. BB

program Tri2; { O(N)}

{$APPTYPE CONSOLE}

var

n:integer;

solve:integer;

procedure Input;

var

f:text;

begin

assign(f,'input.txt');

reset(f);

read(f,n);

close(f);

end;

procedure Output;

var

f:text;

begin

assign(f,'output.txt');

rewrite(f);

writeln(f,solve);

close(f);

end;

function max(a,b:integer):integer;

begin

if a>b then max:=a else max:=b;

end;

function min(a,b:integer):integer;

begin

if a<b then min:=a else min:=b;

end;

procedure Process;

var

i:integer;

jmax:integer;

jmin:integer;

begin

for i:= 1 to n div 3 do

begin

jmax := n-i;

jmin := max(2*i, n-2*i+1);

inc(solve, jmax div 2 - ( jmin + 1 )div 2 + 1);

end;

end;

begin

Input;

Process;

Output;

end.

1. MUSIC

제19회 한국 정보올림피아드 (2001.7.7) 중등부  문제풀이

#include <stdio.h>

#include <fstream.h>

#define MAX_N 1001

#define INPUT_FILE "input.txt"

#define OUTPUT_FILE "output.txt"

void	input_data();

void	solving_problem();

void	output_data();

int n,m,ans = 0;

int arr[MAX_N][MAX_N];

int t_sort[MAX_N];

int set[MAX_N];

void main()

{

input_data();

solving_problem();

output_data();

}

void input_data()

{

int i,j,l;

int d01,d02;

ifstream indat(INPUT_FILE);

for(i=0;i<MAX_N;i++)

{

t_sort[i]=0;

set[i]=0;

for(j=0;j<MAX_N;j++)

{

arr[i][j]=0;

}

}

indat >> n;

indat >> m;

for(i=1;i<=m;i++)

{

indat >> l;

indat >> d01;

for (j=1; j<=l-1; j++)

{

indat >> d02;

if (arr[d01][d02]==0)

{

arr[d01][d02]=1;

set[d02]++;

}

d01 = d02;

}

}

indat.close();

}

void output_data()

{

int i;

ofstream outdat(OUTPUT_FILE);

if (ans==-1)

{

outdat << 0 << endl;

}

else

{

for (i=1; i<=n; i++) outdat << t_sort[i] << endl;

}

outdat.close();

}

void solving_problem()

{

int i,j;

for (i=1; i<=n; i++)

{

int k = 0;

for (j=1; j<=n; j++) if (set[j]==0) k=j;

if (k==0) { ans = -1; return; }

t_sort[i]=k;

set[k]=-1;

for (j=1; j<=n; j++) if (arr[k][j]==1) set[j]--;

}

}

2. COIN

program E2_coin;

{$APPTYPE CONSOLE}

type

narr = array[1..1000] of integer;

karr = array[0..100000] of int64;

pkarr = ^karr;

var

n, k : integer; { n for kind of coins, k for total amount of money}

s1,s2 : karr; { 1 .. max k }

v, c : narr; { 1 .. max n }

p : array [1..2] of pkarr; { easy change for dynamic }

procedure input;

var

f:text;

i:integer;

begin

assign(f,'input.txt');

reset(f);

read(f, k, n);

for i:=1 to n do

begin

read(f, v[i]);

read(f, c[i]);

end;

close(f);

end;

procedure process;

var

t : pkarr;

i, j, l : integer;

max1, max2 : integer;

begin

p[1] := @s1;

p[2] := @s2;

p[1]^[0] := 1;

max1 := 0;

for i:=1 to n do

begin

max2 := max1 + v[i]*c[i];

if max2>k then max2:=k;

for j:=0 to max2 do

begin

p[2]^[j] := 0;

for l:=0 to c[i] do

if j-l*v[i]>=0 then

inc(p[2]^[j],p[1]^[j-l*v[i]]);

end;

t    := p[1];

p[1] := p[2];

p[2] := t;

max1 := max2;

if (p[1]^[k]<0) then writeln('overflow occur');

end;

end;

procedure output;

var

f:text;

begin

assign(f,'output.txt');

rewrite(f);

writeln(f,p[1]^[k]);

close(f);

end;

begin

input;

process;

output;

end.

3. DNA

#include <stdio.h>

#include <string.h>

#define MAX_N 1001

#define MAX_Q 1000001

#define INPUT_FILE "input.txt"

#define OUTPUT_FILE "output.txt"

#define OUTPUT_FILE2 "num.txt"

void input_data();

void solving_problem();

void output_data();

void lexico_first(int);

int n,m;

int k;

char st1[MAX_N],st2[MAX_N];

int arr[MAX_N][MAX_N];

int from[MAX_N][MAX_N][2];

int max=0;

char max_st[MAX_N];

char f_st[MAX_N];

int f_st_n=0;

int que[MAX_Q][2];

int que2[MAX_Q][2];

int q_n=0;

int used[MAX_N][MAX_N];

int num=0;

int num2=0;

//int q_now=0;

void main()

{

input_data();

solving_problem();

output_data();

}

void input_data()

{

char ist1[MAX_N],ist2[MAX_N];

int i,j;

for(i=0;i<MAX_N;i++)

{

for(j=0;j<MAX_N;j++)

{

arr[i][j]=0;

from[i][j][0]=0;

from[i][j][1]=0;

}

}

FILE *indat;

indat=fopen(INPUT_FILE,"rt");

fscanf(indat,"%d",&k);

fscanf(indat,"%d",&n);

fscanf(indat,"%s",ist1);

fscanf(indat,"%d",&m);

fscanf(indat,"%s",ist2);

k=k+1;

/*  fgets(gbg,MAX_N,indat);

fgets(ist1,MAX_N,indat);

n=strlen(ist1)-2;*/

for(i=1;i<=n;i++)

{

st1[i]=ist1[n-i];

}

/*  fgets(ist2,MAX_N,indat);

m=strlen(ist2)-2;*/

for(i=1;i<=m;i++)

{

st2[i]=ist2[m-i];

}

fclose(indat);

}

void solving_problem()

{

int i,j;

int ki,kj;

int i_,j_;

int d01,d_i,d_j;

for(i=1;i<=n;i++)

{

for(j=1;j<=m;j++)

{

if(st1[i]==st2[j])

{

d01=0;

d_i=0;

d_j=0;

if(i>=k)

ki=i-k;

else

ki=0;

if(j>=k)

kj=j-k;

else

kj=0;

for(i_=ki;i_<=i-1;i_++)

{

for(j_=kj;j_<=j-1;j_++)

{

if(st1[i_]==st2[j_])

{

if(d01<arr[i_][j_])

{

d01=arr[i_][j_];

d_i=i_;

d_j=j_;

}

else if(d01==arr[i_][j_] && d01!=0 && st1[i_]<st1[d_i])

{

d01=arr[i_][j_];

d_i=i_;

d_j=j_;

}

}

}

}

if(d01==0)

{

arr[i][j]=1;

if(arr[i][j]>max)

{

max=arr[i][j];

}

}

else

{

arr[i][j]=d01+1;

if(arr[i][j]>max)

{

max=arr[i][j];

}

from[i][j][0]=d_i;

from[i][j][1]=d_j;

}

}

}

}

for(i=1;i<=max;i++)

{

max_st[i]=127;

}

for(i=1;i<=MAX_Q;i++)

{

que[i][0]=0;

que[i][1]=0;

que2[i][0]=0;

que2[i][1]=0;

}

for(i=1;i<=n;i++)

{

for(j=1;j<=m;j++)

{

if(arr[i][j]==max)

{

q_n++;

que[q_n][0]=i;

que[q_n][1]=j;

used[i][j]=1;

}

}

}

num=q_n;

lexico_first(1);

}

void lexico_first(int q_now)

{

int i,i_,j_;

char min;

int d01;

int d_i,d_j;

min=127;

for(i=1;i<=q_n;i++)

{

if(min>st1[que[i][0]])

{

min=st1[que[i][0]];

}

}

max_st[q_now]=min;

if(q_now<max)

{

d01=0;

for(i=1;i<=q_n;i++)

{

if(min==st1[que[i][0]])

{

if(que[i][0]>k)

d_i=que[i][0]-k;

else

d_i=0;

if(que[i][1]>k)

d_j=que[i][1]-k;

else

d_j=0;

for(i_=d_i;i_<=que[i][0]-1;i_++)

{

for(j_=d_j;j_<=que[i][1]-1;j_++)

{

if(arr[i_][j_]==max-q_now && used[i_][j_]==0)

{

d01++;

que2[d01][0]=i_;

que2[d01][1]=j_;

used[i_][j_]=1;

}

}

}

}

}

q_n=d01;

if(num2<q_n)

{

num2=q_n;

}

for(i=1;i<=q_n;i++)

{

que[i][0]=que2[i][0];

que[i][1]=que2[i][1];

}

lexico_first(q_now+1);

}

}

void output_data()

{

int i;

FILE *outdat,*outdat2;

outdat=fopen(OUTPUT_FILE,"w");

outdat2=fopen(OUTPUT_FILE2,"w");

//fprintf(outdat,"%d \n",max);

for(i=1;i<=max;i++)

{

fprintf(outdat,"%c",max_st[i]);

}

fprintf(outdat,"\n");

fprintf(outdat2,"%d %d\n",num,num2);

fclose(outdat);

fclose(outdat2);

}

1. PATH

제19회 한국 정보올림피아드 (2001.7.7) 고등부  문제풀이

#include <stdio.h>

#define	MAX	10000

#define filename1	"input.txt"

#define filename2	"output.txt"

#define	max2(a,b)	((a>b)?a:b)

#define max3(a,b,c)	max2(a,max2(b,c))

#define max4(a,b,c,d)	max2(a,max3(b,c,d))

FILE	*infile ;

int	n,table[2][3][MAX] ; // 0 : UP 1 : LEFT 2 : RIGHT

void test_output(int t)

{

int i ;

for(i=0 ; i<n ; i++)

printf(" (%3d,%3d,%3d)",table[t][0][i],table[t][1][i],table[t][2][i]);

printf("\n");

}

int process()

{

int i,j,turn=0,current_line[MAX] ;

fscanf(infile,"%d",&current_line[0]);

table[turn][0][0] =table[turn][1][0] =table[turn][2][0] = current_line[0] ;

for(j=1 ; j<n ;j++)	{

fscanf(infile,"%d",&current_line[j]);

table[turn][0][j] = table[turn][1][j] = table[turn][2][j] = current_line[j]+table[turn][1][j-1] ;

}

//test_output(turn);

for(i=1 ; i<n ; i++) {

turn = 1- turn ;

for(j=0 ; j<n ;j++)	fscanf(infile,"%d",&current_line[j]);

for(j=0 ; j<n ;j++)

table[turn][0][j] = current_line[j]+max3(table[1-turn][0][j],table[1-turn][1][j],table[1-turn][2][j]);

table[turn][1][0] = table[turn][0][0];

for(j=1 ; j<n; j++)

table[turn][1][j] = current_line[j]+max2(table[turn][1][j-1],table[turn][0][j-1]);

table[turn][2][n-1] = table[turn][0][n-1] ;

for(j=n-2 ; j>=0 ;j--)

table[turn][2][j]= current_line[j]+max2(table[turn][2][j+1],table[turn][0][j+1]);

//	test_output(turn);

}

return max3(table[turn][0][n-1],table[turn][1][n-1],table[turn][2][n-1]) ;

}

int main()

{

infile = fopen(filename1,"r");

fscanf(infile,"%d",&n);

FILE *outfile = fopen(filename2,"w");

fprintf(outfile,"%d\n",process());

fclose(outfile);

fclose(infile);

return 0;

}

2. HEL

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <conio.h>

#define	MAX	1000

#define	filename1	"input.txt"

#define	filename2	"output.txt"

#define	sqr(x)	(((double)x)*((double)x))

class	center {

public:

double x,y ;

double longest ;

bool	find;

}sol ;

class	point {

public:

int	x,y;

/*	center tri_center(point a,point b){

center temp ;

temp.x = (double)( (sqr(x)-sqr(a.x)+sqr(y)-sqr(a.y))*(y-b.y)-(sqr(x)-sqr(b.x)+sqr(y)-sqr(b.y))*(y-a.y) ) /

( 2*(x*a.y-x*b.y+a.x*b.y-a.x*y+b.x*y-b.x*a.y) ) ;

temp.y = (double)(sqr(x)-sqr(b.x)-2*temp.x*(x-b.x)+sqr(y)-sqr(b.y)) /

( 2*(y-b.y) ) ;

return temp ;

}*/

center tri_center2(point a,point b){

center temp ;

if ( ( (_int64)(x-a.x)*(_int64)(b.y-a.y)-(_int64)(b.x-a.x)*(_int64)(y-a.y)  )==0)

{

temp.x =0 ; temp.y=0 ; return temp;

}

temp.x = -(double)( (sqr(a.x)-sqr(x)+sqr(a.y)-sqr(y))*(b.y-a.y) -

(sqr(a.x)-sqr(b.x)+sqr(a.y)-sqr(b.y))*(y-a.y)  ) /

(2*( (double)(x-a.x)*(double)(b.y-a.y)-(double)(b.x-a.x)*(double)(y-a.y)  ) ) ;

if ( ( (_int64)(y-a.y)*(_int64)(b.x-a.x)-(_int64)(b.y-a.y)*(_int64)(x-a.x)  )==0)

{

temp.x =0 ; temp.y=0 ; return temp;

}

temp.y = -(double)( (sqr(a.y)-sqr(y)+sqr(a.x)-sqr(x))*(b.x-a.x) -

(sqr(a.y)-sqr(b.y)+sqr(a.x)-sqr(b.x))*(x-a.x)  ) /

(2*( (double)(y-a.y)*(double)(b.x-a.x)-(double)(b.y-a.y)*(double)(x-a.x)  ) ) ;

return temp ;

}

center bi_center(point a){

center temp ;

temp.x = (double) (x+a.x) / 2 ;

temp.y = (double) (y+a.y) / 2 ;

return temp ;

}

double distance2(center a){

return (sqr(x-a.x)+sqr(y-a.y));

}

int turn(point a,point b){

return ( x*a.y+a.x*b.y+b.x*y-a.x*y-b.x*a.y-x*b.y );

}

} island[MAX] , convex[MAX];

int n,m ;

void read_data()

{

FILE *infile = fopen(filename1,"r");

fscanf(infile,"%d",&n);

int i,j;

for(i=0 ; i<n; i++) {

fscanf(infile,"%d %d",&island[i].x,&island[i].y);

for(j=0;j<i;j++)

if ( island[i].x== island[j].x && island[i].y==island[j].y)

printf("exist coupled data \n");

}

fclose(infile);

}

void test_output(center temp)

{

if ((sol.longest==-1) || (sol.longest>temp.longest)) {

sol = temp ;

}

}

void find_convex_hull()	//  □□□□□□ □□□□ □□□□ □□□□□□□□?

{

m = 1 ;

convex[0] = island[0] ;

int i,start=0,before,next=-1,visit[MAX] ;

for (i=1 ;i<n; i++)

if ( (convex[0].x > island[i].x) ||

(convex[0].x==island[i].x && convex[0].y>island[i].y) ){

start = i ;

convex[0] = island[i] ;

}

for(i=0; i<n; i++)

visit[i] = false ;

before = start ; next = -1 ;

while( start!=next)

{

for(i=0 ; i<n ; i++)

if (before!=i && !visit[i] ) {next = i ; break;}

for(i=0 ; i<n ; i++)

if (before!=i && next!=i && !visit[i]) {

if (convex[m-1].turn(island[next],island[i])>0) {

next = i ;

} else if ( (convex[m-1].turn(island[next],island[i])==0) &&

! ( (island[i].x-convex[m-1].x)*(island[i].x-island[next].x) >=0 &&

(island[i].y-convex[m-1].y)*(island[i].y-island[next].y) >=0 ) ) {

next = i ;

}

}

before = next ;

if (next!=start) {

convex[m++] = island[next] ;

visit[next] = true ;

}

}

}

void process2()

{

sol.longest = -1 ;

int i,j,k,l	;

for(i=0;i<m;i++){

for(j=i+1;j<m;j++)

for(k=j+1;k<m;k++){

center temp = convex[i].tri_center2(convex[j],convex[k]); //,island[k]);

temp.longest=convex[i].distance2(temp);

/*	if( fabs(convex[i].distance2(temp)-convex[j].distance2(temp))>0.0001 ||

fabs(convex[j].distance2(temp)-convex[k].distance2(temp))>0.0001 ) {

printf("%f %f %f %f \n",temp.longest,sqrt(convex[i].distance2(temp)),sqrt(convex[j].distance2(temp)),sqrt(convex[k].distance2(temp)));

printf ("%f %f \n",fabs(convex[i].distance2(temp)-convex[j].distance2(temp)),fabs(convex[j].distance2(temp)-convex[k].distance2(temp)));

printf(" center error \n");

}*/

bool isItokay = true;

for(l=0;l<n;l++)

if (island[l].distance2(temp)>temp.longest+0.00001) {

isItokay = false ;

break;

}

if(isItokay){

test_output(temp);

}

}

}

for(i=0;i<m;i++)

for(j=i+1;j<m;j++){

center temp = convex[i].bi_center(convex[j]); //,island[k]);

temp.longest=convex[i].distance2(temp);

if( fabs(convex[i].distance2(temp)-convex[j].distance2(temp))>0.0001  ) {

printf("%f %f %f \n",temp.longest,sqrt(convex[i].distance2(temp)),sqrt(convex[j].distance2(temp)));

printf ("%f %f \n",fabs(convex[i].distance2(temp)-convex[j].distance2(temp)));

printf(" center error \n");

}

bool isItokay = true;

for(l=0;l<n;l++)

if (island[l].distance2(temp)>temp.longest+0.00001) {

isItokay = false ;

break;

}

if(isItokay){

test_output(temp);

}

}

}

void output()

{

FILE *outfile = fopen(filename2,"w");

fprintf(outfile,"%.3f %.3f\n%.3f\n",sol.x,sol.y,sqrt(sol.longest));

fclose(outfile);

}

int main()

{

read_data();

find_convex_hull();

process2();

output();

return 0 ;

}

3. TREE

#include<stdio.h>

#include<stdlib.h>

#define INPUT_FILE "input6.txt"

#define OUTPUT_FILE "output.txt"

#define MAX_N 300

#define MAX_RES MAX_N * 12

struct tree

{

int name;

tree* left;

tree* right;

int left_n;

int right_n;

};

int n;

tree *t, *tt;

int m1, m2;

char squ_case[4][3] = {"TL", "CL", "CR", "TR"};

int s1[MAX_RES+1], s2[MAX_RES];

int res_n;

int res[MAX_RES+1];

int lb1;

bool insert(tree* t, int root, int left, int right)

{

bool found;

if (t->name == root)

{

t->left = (tree*) malloc(sizeof(tree));

t->left->name = left;

t->left->left = NULL;

t->left->right = NULL;

t->left->left_n = 0;

t->left->right_n = 0;

t->right = (tree*) malloc(sizeof(tree));

t->right->name = right;

t->right->left = NULL;

t->right->right = NULL;

t->right->left_n = 0;

t->right->right_n = 0;

t->left_n++;	t->right_n++;

return true;

}

else

{

if (t->left != NULL) {

found = insert(t->left, root, left, right);

if (found) {

t->left_n += 2;

return found;

}

found = insert(t->right, root, left, right);

if (found) t->right_n += 2;

return found;

}

return false;

}

}

void initialize(tree* &t)

{

t = (tree*) malloc(sizeof(tree));

t->name = 1;

t->left_n = 0;

t->right_n = 0;

}

void Input_file()

{

FILE *inf;

int i;

int root, left, right;

bool temp;

initialize(t);

initialize(tt);

inf = fopen(INPUT_FILE, "r");

fscanf(inf, "%d", &n);

for (i=0; i<n; i++)

{

fscanf(inf, "%d %d %d", &root, &left, &right);

if (left != 0) temp = insert(t, root, left, right);

}

for (i=0; i<n; i++)

{

fscanf(inf, "%d %d %d", &root, &left, &right);

if (left != 0) temp = insert(tt, root, left, right);

}

fclose(inf);

}

void Move_Left(tree* &t, int sw)

{

tree* temp;

temp = (tree*) malloc(sizeof(tree));

temp->left = (tree*) malloc(sizeof(tree));

temp->left->left = t->left;

temp->left->right = t->right->left;

temp->right = t->right->right;

temp->right_n = t->right->right_n;

temp->left_n = t->left_n + t->right->left_n + 1;

temp->left->right_n = t->right->left_n;

temp->left->left_n = t->left_n;

free(t->right);

free(t);

t = temp;

if (sw == 1) s1[m1++] = 0;

else if (sw == 2) s2[m2++] = 3;

else if (sw == 3) s1[m1++] = 1;

else if (sw == 5) m1--;

}

void Move_Right(tree* &t, int sw)

{

tree* temp;

temp = (tree*) malloc(sizeof(tree));

temp->right = (tree*) malloc(sizeof(tree));

temp->right->right = t->right;

temp->right->left = t->left->right;

temp->left = t->left->left;

temp->left_n = t->left->left_n;

temp->right_n = t->right_n + t->left->right_n + 1;

temp->right->left_n = t->left->right_n;

temp->right->right_n = t->right_n;

free(t->left);

free(t);

t = temp;

if (sw == 1) s1[m1++] = 3;

else if (sw == 2) s2[m2++] = 0;

else if (sw == 3) s1[m1++] = 2;

else if (sw == 4) s2[m2++] = 1;

else if (sw == 5) m1--;

}

bool isSame(tree* t, tree* tt)

{

bool same;

if (tt == NULL) return false;

else

{

if (t->left != NULL)

{

same = isSame(t->left, tt->left);

if (!same) return same;

same = isSame(t->right, tt->right);

return same;

}

if (tt->left == NULL) return true;

return false;

}

}

void Find_upper_bound()

{

int i;

int t_n, tt_n;

while(t->left->left != NULL)

Move_Right(t, 1);

while(tt->left->left != NULL)

Move_Right(tt, 2);

while(t->right->right != NULL)

{

if (isSame(t->right->left, tt->right->left))

{

Move_Left(t, 1);

Move_Left(tt, 2);

}

else

{

t_n = t->right->left_n;

tt_n = tt->right->left_n;

if (t_n >= tt_n) Move_Right(t->right, 3);

if (t_n <= tt_n) Move_Right(tt->right, 4);

}

}

res[0] = 4;

res_n = 0;

for (i=0; i<m1; i++)

if (s1[i] + res[res_n] == 3) res_n--;

else res[++res_n] = s1[i];

for (i=m2-1; i>=0; i--)

if (s2[i] + res[res_n] == 3) res_n--;

else res[++res_n] = s2[i];

for (i=1; i<=res_n; i++)

if ((res[i] == 1) || (res[i] == 2)) lb1++;

}

int lb2(tree* t)

{

return 0;

}

void Search()

{

int i;

if (m1 + lb1 + lb2(t) > res_n) return;

else

{

if (isSame(t, tt))

{

res_n = m1-1;

for (i=1; i<=res_n; i++)

res[i] = s1[i];

}

else

{

if ((t->left->left != NULL) && s1[m1-1] != 0)

{

Move_Right(t, 1);	Search();	Move_Left(t, 5);

}

if (t->right->right != NULL)

{

if (m1 == 1)

m1 = 1;

if (s1[m1-1] != 3)

{

Move_Left(t, 1);	Search();	Move_Right(t, 5);

}

if ((t->right->right->right != NULL) && (s1[m1-1] != 2))

{

Move_Left(t->right, 3);	lb1--;

Search();

Move_Right(t->right, 5);	lb1++;

}

if ((t->right->left->left != NULL) && (s1[m1-1] != 1))

{

Move_Right(t->right, 3);	lb1--;

Search();

Move_Left(t->right, 5);	lb1++;

}

}

}

}

}

void Solve()

{

m1 = 0;	m2 = 0;

Find_upper_bound();

free(t);

free(tt);

Input_file();

m1 = 1;	s1[0] = 4;

Search();

}

void Output_file()

{

FILE *ouf;

int i;

ouf = fopen(OUTPUT_FILE, "w");

fprintf(ouf, "%d\n", res_n);

for (i=1; i<=res_n; i++)

fprintf(ouf, "%s\n", squ_case[res[i]]);

fclose(ouf);

}

void main()

{

Input_file();

Solve();

Output_file();

}