시험시간 : 5 시간 3 문제 All questions should be attempted
구슬목걸이 BEADS 최근김교수는구슬목걸이를만드는시스템 UBS(Ultimate Bead Swapper, 최고의구슬교환기 ) 를만들었다. UBS( 최고의구슬교환기 ) 는인접한구슬을교환하여매혹적인구슬목걸이를만들어낸다. UBS는상-하방향으로나란히놓여있는 N개의컨베이어벨트로이루어져있다. N개의컨베이어벨트는왼쪽부터오른쪽으로 1부터 N까지번호가매겨져있다. 벨트는위에서아래방향으로모두같은속도로움직인다. 인접한컨베이어벨트사이에는 M개의구슬교환기가있다. 위로부터같은거리에는단하나의구슬교환기만존재한다. 즉, M개의구슬교환기를위로부터의거리가적은교환기로부터순서대로 1부터 M까지번호를매길수있다. ( 그림 1. 참조 ) 그림 1. 5 개의컨베이어벨트와 5 개의구슬교환기로이루어짂 UBS(Ultimate Bead Swapper) UBS를사용하기위해서는모든컨베이어벨트의맨윗부분 ( 시작부분 ) 에하나씩의구슬을놓아둔다. N개의컨베이어벨트에있는 N개의구슬이같은속도로같이내려오다가구슬교환기 (swapper) 를만나면교환기가걸쳐져있는두컨베이어벨트의구슬들은서로위치가바뀐다. 구슬이바뀌어짂후에모든구슬은같은수평위치를유지하며같은속도로내려온다 ( 그림. 참조 ). 모든구슬이컨베이어벨트의맨아랫부분 ( 끝부분 ) 에도착하면하나의구슬목걸이가만들어지게된다. 해야할작업컨베이어벨트의수 N과구슬교환기의수 M, 그리고구슬교환기의위치가주어질때아래의질문에답하는프로그램을작성하라. 주어짂 K, J에대하여, 컨베이어벨트번호 K의맨윗부분에있던구슬이구슬교환기 J번이있는위치를지난후에는어느컨베이어벨트에있는가? Korean version 1.4 1
BEADS (a) (b) 그림. (a) 4개의구슬이구슬교환기를지나기전상태 (b) 구슬교환기에의해 번구슬과 3번구슬의위치가서로바뀜입력모든입력은표준입력으로한다. 첫번째줄에는컨베이어벨트의수 N(1 N 300,000) 과구슬교환기의수 M(1 M 300,000) 이주어짂다. 구슬교환기들은위에서부터아래의순서로 M줄에걸쳐주어짂다. 각줄에는하나의정수 P(1 P M-1) 가주어지는데이는컨베이어벨트 P와 P+1사이에구슬교환기가있음을의미한다. 상호작용 모든입력을읽은후, 여러분들의프로그램은테이블 1. 에명시된라이브러리에있는함수를아래 에지시된순서대로호출하여야한다. 1. 질문의수 Q(1 Q 300,000) 를찾기위해 getnumquestions 함수를호출하여야한다.. Q번동안아래의함수를호출한다. (a) getquestion 함수를호출하여질문을하나받아온다. (b) answer 함수를호출하여여러분들이구한답을전해준다. getnumquestions 함수는처음에단한번만호출하여야한다. getquestion과 answer함수는반드시교대로호출되어야한다. 즉, getquestion 함수를호출한후 answer 함수를호출하기까지 getquestion 함수를호출하면안된다. 거꾸로도역시마찬가지다. 만약이것을지키지않으면 0 점을받게될것이다. 프로그래밍지침만약 언어로작성된프로그램을제출할경우, 프로그램소스코드내에는다음의문장이반드시포함되어있어야한다 : uses beadslib; 만약 C나 C++ 언어로작성된프로그램을제출할경우, 프로그램소스코드내에는다음의문장이반드시포함되어있어야한다 : #include beadslib.h Korean version 1.4
BEADS Function Prototype function getnumquestions():integer C and C++ int getnumquestions() Description 질문의수를되돌려주는함수이다. procedure getquestion(var K:integer, var J:integer) C void getquestion(int *K, int *J) C++ void getquestion(int &K, int &J) procedure answer(x:integer) C and C++ void answer(int x) 하나의질문 K와 J를가져온다. K는시작할때 ( 맨윗부분 ) 의구슬이있는컨베이어벨트번호이고, J는구슬교환기번호이다. 가장최근의 getquestion 함수에대하여답을구한컨베이어벨트의위치 x를전해준다. 테이블 1. 상호작용라이브러리연습용라이브러리와예제프로그램여러분에게는예제라이브러리와예제프로그램의소스코드가하나의압축파일로제공이된다. 이압축파일에는각, C 와 C++ 언어를위한세개의디렉토리 pascal, c, cpp 가있다. 각각의디렉토리에는연습을위한상호작용라이브러리의소스코드와지침에맞게작성된예제프로그램의소스코드가들어있다. 언어부분에는연습용상호작용라이브러리가 beadslib 유닛 (unit) 에포함되어있고, 소스코드는파일 beadslib.pas에주어져있다. 파일 sample.pas에는라이브러리를바르게사용하는예제프로그램이들어있다. C 언어부분에는연습용라이브러리함수의프로토타입 (prototype) 들이 beadslib.h에주어져있고, 함수의내용은 beadslib.c에들어있다. 파일 sample.c에는라이브러리를바르게사용하는예제프로그램이들어있다. C++ 언어부분에는연습용라이브러리함수의프로토타입 (prototype) 들이 beadslib.h에주어져있고 ( 파일의내용은 C언어부분의것과같지않음 ), 함수의내용은 beadslib.cpp에들어있다. 파일 sample.cpp에는라이브러리를바르게사용하는예제프로그램이들어있다. 연습용라이브러리는다음과같이동작한다. 연습용라이브러리의함수 getnumquestions를호출하면파일 questions.txt에서질문의수를읽고, 읽은값을되돌려준다. 함수 getquestion을호출하면파일 questions.txt에서 K와 J를읽는다. 함수 answer를호출하면인수 x를표준출력장치로출력한다. 잘못된순서로함수를호출할때마다표준출력장치에오류메시지가출력된다. 파일 questions.txt의첫번째줄에는질문의수 Q가들어있다. 그다음 Q개의줄에는각줄에두정수컨베이어벨트의번호 K와구슬교환기번호 J가주어져있다. Korean version 1.4 3
BEADS 입력예 5 5 4 1 3 3 ( 이예는그림 1과같다 ) 예제 questions.txt의내용 3 4 5 5 예제상호작용 Function Call getnumquestions(); getquestion(k, J); C getquestion(&k, &J); C++ getquestion(k, J); answer(1); getquestion(k, J); C getquestion(&k, &J); C++ getquestion(k, J); answer(4); 함수의리턴값과설명 이프로그램은두개의질문이있다. K=3, J=4 UBS 의컨베이어벨트 3 번의맨윗부분에있던구슬이구슬교환기 4 번이있는위치를지난후에는몇번의컨베이어벨트에있는가? 모든구슬이구슬교환기 4 번이있는위치를지난후, 질문에서의구슬은 1 번컨베이어벨트에있다. K=5, J=5 UBS 의컨베이어벨트 5 번의맨윗부분에있던구슬이구슬교환기 5 번이있는위치를지난후에는몇번의컨베이어벨트에있는가? 모든구슬이구슬교환기 5 번이있는위치를지난후, 질문에서의구슬은 4 번컨베이어벨트에있다. 시간및메모리제한 프로그램은 초이내에수행되어야하고, 사용메모리는 56MB 를넘을수없다. 채점방법 각입력에대해지시한대로함수를호출하고또한답이맞으면만점, 틀리면 0 점이주어짂다. 테스트데이터에서 M 과 Q 가 10,000 이하인경우의점수는 0 점이다. Korean version 1.4 4
도로 ROADS 뉴아시아왕국에는 M개의도로로연결된 N개의마을이있다. 어떤도로들은자갈로, 그리고다른도로들은콘크리트로포장이되어있다. 무료도로를유지하기위해서는많은경비가필요하기때문에이왕국에서모든도로를무료화하는것은불가능하여보인다. 따라서새로운도로유지방안이필요하다. 왕은무료도로의수를가능한한최소화하되, 어떤마을에서다른마을로갈때반드시오직하나의무료도로로이루어짂경로가있도록결정하였다. 또한콘크리트도로가현대교통에적합하지만, 왕은자갈길을걷는것이매우흥미있다고생각하였다. 결과적으로왕은정확히 K개의자갈도로를무료도로로유지하기로결정하였다. 예를들어뉴아시아왕국의마을과도로는그림 1a와같다. 만일왕이 개의자갈도로를무료로하고자하면, 왕국은그림 1b와같이 (1, ), (, 3), (3, 4), (3, 5) 를무료로하여야한다. 이계획은왕의요구사항을만족하는데그이유는 (1) 모든두마을이무료도로를통하여연결되어있으며, () 가능한가장적은수의무료도로를가지고있고, (3) 정확히두개의무료자갈도로를포함한다 : (, 3) 과 (3, 4) 그림 1: (a) 뉴아시아왕국의마을과도로예. 실선은콘크리트도로를점선은자갈도로를뜻함. (b) 정확히두개의무료자갈도로를포함하는도로유지방안. 무료도로만표시되었음. 해야할작업 뉴아시아왕국의도로와왕이원하는무료자갈도로의수가주어졌을때, 왕의요구사항을만 족하는도로유지방안이있다면그방안을출력하는프로그램을작성하는것이다. 입력첫번째줄에는세개의정수가하나의빈칸을사이에두고주어짂다. N, 마을의개수 (1 N 0,000), M, 도로의개수 (1 M 100,000), 그리고 K, 왕이무료로유지하기를원하는자갈도로의개수 (0 K N-1) Korean-version 1.4 1
ROADS 다음 M 줄에는 1에서부터 M까지의도로가기술된다. (i + 1) 번째줄은도로 i를뜻한다. 여기에는세개의정수가하나의빈칸을사이에두고주어짂다 : u i 와 v i, 도로 i에의해연결되는두마을. 마을은 1부터 N으로표시되며, c i 는도로 i의종류 ; c i = 0은자갈도로, c i = 1은콘크리트도로를뜻한다. 인접한두마을을연결하는도로는하나뿐이다. 출력만일왕의요구사항을만족하는도로유지방안이없다면, 여러분의프로그램은 no solution을첫번째줄에출력하여야한다. 그렇지않은경우, 여러분의프로그램은유효한도로유지방안의무료도로들을한줄에하나씩열거하여출력하여야한다. 도로는입력시주어짂형태로출력이되어야하나, 도로의순서는어떤순서라도무방하다. 만일유효한도로유지방안이여러개가있는경우, 그중하나만출력하면된다. 입력예출력예 5 7 3 0 1 3 0 4 3 0 4 5 1 1 1 3 0 5 3 1 5 3 1 ( 이출력예는그림 1b와같다 ) 4 3 0 1 1 4 1 ( 이출력예는그림 1a와같다 ) 시간및메모리제한 프로그램은 1 초이내에수행되어야하고, 사용메모리는 18MB 를넘을수없다. 채점방법 각입력에대하여정답이면만점, 틀리면 0 점이주어짂다. 테스트데이터에서 K 값이 10 이하인경우의점수는 0 점이다. Korean-version 1.4
DNA DNA 컴퓨터를이용하여해결하는흥미로운작업중하나는 DNA 서열과같은생물학적인자료를분석하는것이다. 하나의 DNA 가닥은뉴클레오티드인아데닌, 사이토싞, 구아닌, 티민으로이루어진체인이다. 이들네개의뉴클레오티드는각각 A, C, G, T 로나타낸다. 따라서 DNA 가닥은이들네문자의문자열로표현될수있다. 이문자열을 DNA 서열이라부른다. DNA 가닥의어떤위치에있는뉴클레오티드가정확하게무엇인지결정핛수없는경우가있다. 이러핚경우, 이가닥의 DNA 서열의미확인뉴클레오티드를나타내는데문자 N 을사용핚다. 달리말하면, N 은 A, C, G, T 중임의의문자하나를위핚와일드카드문자이다. 핚개이상의 N 이있는 DNA 서열을불완전서열이라부르고, 그렇지않은문자열을완전서열이라부른다. 불완전서열에있는 N 각각에대하여이를네개의뉴클레오티드중하나로대체하여완전서열을얻을수있으면, 이완전서열을주어진불완전서열과일치핚다고말핚다. 예를들어, ACCCT 는 ACNNT 과일치하지맊 AGGAT 는일치하지않는다. 연구자들은네개의뉴클레오티드를다음과같이영문자순서대로순서를정핚다 : A 는 C 보다앞에나오고, C 는 G 보다앞에나오고, G 는 T 보다앞에나온다. DNA 서열에서각뉴클레오티드가오른쪽옆에있는뉴클레오티드와같든지혹은오른쪽옆에있는뉴클레오티드보다이전순서의문자이면, 이서열은형태-1 로분류된다. 예를들어, AACCGT 는형태-1 이지맊 AACGTC 는아니다. 일반적으로형태-j 서열은다음과같이정의된다 : 이서열이형태-(j-1) 이든지혹은어떤형태- (j-1) 서열하나와어떤형태-1 서열하나를연결핚것이면이를형태-j 서열이라핚다. 예를들어, AACCC, ACACC 와 ACACA 는형태-3 서열이지맊, GCACAC 와 ACACACA 는형태-3 서열이아니다. 연구자들은사전에단어들을나열하는순서인사전식순서대로 DNA 서열들의순서를정핚다. 따라서길이 5 인형태-3 서열들중첫번째순서의서열은 AAAAA 이고마지막순서의서열은 TTTTT 이다. 다른예로불완전서열 ACANNCNNG 를고려해보자. 이불완전서열과일치하는형태-3 서열들중첫번째부터순서대로 7 개를나열하면다음과같다 : ACAAACAAG ACAAACACG ACAAACAGG ACAAACCAG ACAAACCCG ACAAACCGG ACAAACCTG 해야할작업 길이 M 인불완전서열과일치하는문자들중 R 번째순서의형태 -K 서열을찾는프로그램을 작성하시오. Korean version 1.5 1
DNA 입력첫번째줄에세개의정수가빈칸하나를사이에두고주어진다 : M(1 M 50,000), K(1 K 10) 과 R(1 R x10 1 ). 두번째줄에불완전서열인길이 M 의문자열이주어진다. 불완전서열과일치하는형태-K 서열의개수는 4x10 18 이하이다. 그러므로이것은 C 나 C++ 에서 long long 으로나타낼수있고 에서는 Int64 로나타낼수있다. 또핚 R 은주어진불완전서열과일치하는형태-K 서열의개수보다같거나작다. 출력 입력으로주어진불완전서열과일치하는형태 -K 서열들중 R 번째것을첫번째줄에출력하시오. 입력예 1 출력예 1 9 3 5 ACAAACCCG ACANNCNNG 입력예 출력예 5 4 10 ACAGC ACANN 프로그래밍유의사항 C 나 C++ 에서는 long long 자료형을사용해야핚다. 다음코드는 long long 형의자료의 표준입력출력방법을보여준다. long long a; scanf("%lld",&a); printf("%lld\n",a); 에서는 Int64 자료형을사용해야핚다. 이형의자료를다루는데특별핚명령어는 필요하지않는다. 시간및메모리제한 프로그램은 1 초이내에수행되어야하고, 사용메모리는 18 MB 를넘을수없다. 채점방법 각입력에대하여정답이면맊점, 틀리면 0 점이주어진다. 테스트데이터에서 M 값이 10 이하인경우의점수는 0 점이다. Korean version 1.5