- 1 -
2013 시도예선중고등부문제 1. 의마지막자리의숫자 (1 의자릿수 ) 는얼마인가? 여기서 이다. 즉, 은 1 부터 까지모든자연수의곱이다. 예를들어, 이다. 1 1 2 3 3 5 4 7 5 9 2. 1 부터 100 까지모든정수의각자리에나타난수를모두더하면얼마인가? 1 899 2 900 3 901 4 902 5 903 3. 철수, 영희, 길동이가점 P에서동시에출발하여철수는경로 A를따라, 영희는경로 B 를따라, 길동은경로 C를따라달린다. 세사람이모두같은빠르기로달린다. 변옆의수는변의길이를나타낸다. 철수가 110바퀴돌았을때세사람이동시에몇번만났는가? 단, 처음출발할때만난것은제외한다. B 7 5 8 5 15 5 C A 7 8 P 7 15 5 8 1 4 2 5 3 6 4 7 5 8 4. 1000개의동전이있다. 이중 999개의동전의무게는각각 10그램이고, 나머지동전하나는 10그램이아니다. 여러동전의무게의합을한번에정확히잴수있는저울을이용하여 10그램이아닌동전하나가무엇인지알아내려고한다. 이를위해필요한저울의최소사용회수는얼마인가? 1 9 2 10 3 11 4 49 5 99 5. 어떤함수 는모든정수 에대하여 을만족한다. 만약 이고 이면, 은얼마인가? 1-3 2-2 3 1 4 2 5 3-2 -
6. 30 명의학생들에게세문제가주어졌다. 1 번문제를푼학생이 25 명이고, 2 번문제를 푼학생이 23 명이며, 3 번문제를푼학생이 18 명이면, 세문제모두푼학생은최소몇 명인가? 1 0 2 5 3 6 4 7 5 12 7. 네명의학생갑, 을, 병, 정이 100m 달리기를하였다. 친구들이달리기결과를다음과같이예측하였다. ( 친구1) 1등 : 갑, 2등 : 을, 3등 : 병 ( 친구2) 1등 : 을, 2등 : 병, 3등 : 정 ( 친구3) 1등 : 병, 2등 : 갑, 3등 : 정경기가끝났을때, 위의친구세명은각각한명의등수만정확하게맞추었다. 또한세명의친구가맞춘등수는모두달랐다. 이때, 2등한학생은누구인가? 1 갑 2 을 3 병 4 정 5 알수없음 8. 1 부터 999 까지모든자연수들을사전적순서로나열할때, 350 번째의수는무엇인가? 예를들어, 10, 11, 21, 100, 101, 111, 120 을사전적순서로나열하면 10, 100, 101, 11, 111, 120, 21 이된다. 1 41 2 350 3 405 4 413 5 514 9. 무게가서로다른구슬세개가있다. 양팔저울을사용하여가장가벼운구슬, 중간무 게의구슬, 가장무거운구슬의순서대로나열하고싶다. 양팔저울을최소몇번사용 하면항상나열할수있는가? 1 2 2 3 3 4 4 5 5 6 10. 열자리십진수 7abcdefg77 은 1900 과 2000 사이의어떤정수의세제곱이다. g 에해 당하는숫자는무엇인가? 1 1 2 2 3 4 4 8 5 9 [11-12] 양의정수 에대하여, 1부터 까지의정수들중에서다음조건을모두만족하도록하나이상을뽑아나열한것을 KOI 수열이라고하자. (1) 두번째수부터는바로이전의수보다반드시커야한다. (2) 홀수번째위치하는수는반드시홀수여야하고, 짝수번째위치하는수는반드시짝수이어야한다. - 3 -
예를들어, = 3 일때 KOI 수열은다음과같은네가지가있다. 11. = 5 일때, KOI 수열은몇가지인가? 1 3 1,2 1,2,3 1 8 2 10 3 12 4 15 5 18 12. = 10 일때, KOI 수열은몇가지인가? 1 140 2 141 3 142 4 143 5 144 13. 0과 1로이루어진길이가 6인두문자열 A, B에대하여 A와 B의거리는첫번째위치부터여섯번째위치까지의각위치에대하여, 대응하는두문자가서로다른위치의개수이다. 예를들어 A = 010010이고, B = 110101에대하여첫번째, 네번째, 다섯번째, 여섯번째위치에서 A와 B의대응하는문자가다르므로, A와 B의거리는 4이다. 0과 1로이루어진길이가 6인여러문자열들의모임에대하여이모임의유사도는모든두문자열의거리의합이다. 예를들어, 세개의문자열 A = 010010, B = 110101, C = 111000의모임의유사도 = A와 B의거리 + A와 C의거리 + B와 C의거리 = 4 + 3 + 3 = 10이다. 길이가 6인 8개의문자열모임이주어져있다. 이문자열모임의유사도를구하기위하여, 각위치에대하여 8개의문자열에있는 1의개수를세었더니첫번째위치부터여섯번째위치까지차례대로 4, 3, 0, 7, 3, 2이었다. 그러면이문자열모임의유사도는얼마인가? 1 57 2 59 3 61 4 63 5 65 [14-15] 선생님께서여섯명의학생들 A, B, C, D, E, F를다음조건을만족하도록한줄로세우는과제를내었다. (1) 학생 A, B, C는연속적으로설수없다. 즉, 연속적으로 ABC, ACB, BAC, BCA, CAB, CBA로설수없다. (2) 학생 D, E, F는연속적으로설수없다. 즉, 연속적으로 DEF, DFE, EDF, EFD, FDE, FED로설수없다. (3) 학생 B는제일처음이나제일마지막에설수없다. (4) 학생 F는 B의바로앞이나바로뒤에설수없다. (5) 학생 A는 E보다앞에서야한다. 14. 학생 E가줄의세번째에서게되고, F가네번째서게된다면, 다음중에서맞는것은? 1 A는줄의두번째에선다. - 4 -
2 B는줄의다섯번째에선다. 3 C는줄의다섯번째에선다. 4 D는줄의첫번째에선다. 5 D는줄의두번째에선다. 15. 학생 C가줄의첫번째에서게되고, A가다섯번째서게된다면, 다음중에서항상옳은것은? 1 D는줄의세번째에선다. 2 F는줄의네번째에선다. 3 B는 A의바로앞에선다. 4 C는 F의바로앞에선다. 5 D는 B의바로앞에선다. [16-40] 문제나프로그램내에명시되지않은모든변수와배열은 int 형이다. 16. 다음프로그램의출력결과는무엇인가? int u = 75, x = 90, y = 85; int m; m = u; if (m < x) { m = x; if (m < y) { m = y; u = u + 100 - m; x = x + 100 - m; y = y + 100 - m; printf("%d\n", y); 1 75 2 85 3 90 4 95 5 100 17. 다음프로그램의출력결과는무엇인가? int i, y = 0; for (i = 2000; i <= 2013; i++) { if ((i % 4 == 0 && i % 100!= 0) i % 400 == 0) { - 5 -
y++; printf("%d\n",y); 1 4 2 5 3 6 4 7 5 8 18. 다음프로그램의출력결과는무엇인가? int i = 1, count = 0; while (i <= 2013) { count++; i = i * 2; printf("%d\n", count); 1 9 2 10 3 11 4 12 5 13 19. 다음프로그램의출력결과는무엇인가? int sum = 0, a = 2013; while (a > 0) { sum += a % 3; a /= 3; printf("%d\n", sum); 1 9 2 10 3 11 4 12 5 13 20. 다음프로그램의출력결과는무엇인가? int i; int count = 0; for (i = 1; i < 125; i++) { if (i % 2 == 0 i % 5 == 0) { count++; - 6 -
printf("%d\n", count); 1 73 2 74 3 75 4 76 5 77 21. 다음프로그램의출력결과는무엇인가? int i = 1, ret = 2; while (i < 2013) { ret = ret + 1; i = i + 2013 / ret; printf("%d\n", ret); 1 4 2 5 3 6 4 7 5 8 22. 다음프로그램의출력결과는무엇인가? int a[4] = {4, 3, 1, 2; int i, j, k, t; t = 0; for (i = 0; i < 4; i++) { for (j = i + 1; j < 4; j++) { if (a[j] < a[i]) { k = a[j]; a[j] = a[i]; a[i] = k; t++; printf("%d\n", t); 1 3 2 4 3 5 4 6 5 10 23. f(10) 의값은무엇인가? - 7 -
int f(int n) { int i, j, ret = 0; for (i = 1; i < n; i++) { for (j = 1; j < 2 * i; j++) { ret = ret + 1; return ret; 1 45 2 55 3 81 4 90 5 100 24. 배열 a 에는다음과같은값이주어진다. int a[] = {1, 37, 3, 10, 13, 23, 4, 8, 17; 아래주어진함수 SomeAverage(a, 9, 5) 를호출했을때출력결과는무엇인가? void SomeAverage(int a[], int n, int m) { int i, j, sum; for (i = 0; i <= n - m; i++) { sum = 0; for (j = i; j < i + m; j++) { sum = sum + a[j]; printf("%d ", sum / m); printf("\n"); 1 13 17 11 12 13 2 12 17 10 11 13 3 12 17 11 12 13 4 12 17 10 12 13 5 12.8 17.2 10.6 11.6 13 25. f(2013) 의값은무엇인가? int f(int n) { int a[2014]; - 8 -
int i, j, cnt; for (i = 1; i <= n; i++) { a[i] = 0; for (i = 1; i <= n; i++) { for (j = i; j <= n; j += i) { a[j] = 1 - a[j]; cnt = 0; for (i = 1; i <= n; i++) { if (a[i] == 1) { cnt++; return cnt; 1 10 2 11 3 22 4 33 5 44 26. f(25, 60) 을실행한후, count 의값은무엇인가? int count = 0; int f(int a, int b) { count++; if (a == b) { return a; else { int mid; mid = (a + b) / 2; return f(a, mid) + f(mid + 1, b); 1 67 2 68 3 69 4 70 5 71 27. f(6, 3) 의값은무엇인가? - 9 -
int f(int n, int k) { if (k <= 0 k >= n) { return 1; return f(n - 1, k - 1) + f(n - 1, k) + f(n - 1, k + 1); 1 53 2 57 3 71 4 29 5 23 28. 다음프로그램의출력결과는무엇인가? int a[20] = {1, 4, 3, 2, 4, 1, 2, 5, 1, 2, 3, 5, 4, 1, 2, 1, 1, 1, 1, 9; int i, s = 0, gr = 0; for (i = 0; i < 20; i++) { if (a[i] + s > 10) { gr++; s = 0; else { s = s + a[i]; if (s > 0) { s = 0; gr++; printf("%d\n", gr); 1 1 2 4 3 5 4 6 5 20 29. 다음프로그램의출력결과는무엇인가? int a[4][4] = {0; int i, j, n, u, v, k, t; i = j = 0; u = 0, v = 1; n = 4; - 10 -
for (k = 1; k <= 16; k++) { a[i][j] = k; if (i + u >= n j + v >= n i + u < 0 j + v < 0 a[i + u][j + v]!= 0) { t = v; v = -u; u = t; i = i + u, j = j + v; printf("%d\n", a[2][2]); 1 12 2 13 3 14 4 15 5 16 30. 다음보기중에서가장큰값은무엇인가? int f(int n, int m) { if (n == 0 && m == 0) return 0; if (n % 2 == 1 && m % 2 == 1) return f(n / 2, m / 2) + 1; if (n % 2 == 0 && m % 2 == 0) return f(n / 2, m / 2) + 1; return f(n / 2, m / 2); 1 f(18, 19) 2 f(11, 25) 3 f(2, 17) 4 f(25, 16) 5 f(11, 29) 31. 다음프로그램의출력결과는무엇인가? int a[4] = {0, 0, 0, 0, b[4] = {6, 2, 1, 1; int k, n, i; k = 14; for (n = 0 ; n < 4 ; n++) { for (i = 0; i < 4; i++) { if (a[i] == 0) { if (b[n] < k) { k -= b[n]; else { a[i] = 1; - 11 -
printf("\n"); printf("%d ", i); break; 1 2 0 1 3 2 2 0 3 1 3 2 1 0 3 4 3 1 4 2 5 3 2 1 4 32. 다음프로그램의출력결과는무엇인가? int c = 0, i, j, k; char str[] = "mississippi"; int len = 11; int p; for (i = 0; i < len; i++) { for (j = i + 1; j < len; j++) { p = j - i + 1; for (k = 0; i + k < j - k; k++) { if (str[i + k]!= str[j - k]) { p = 0; break; c = c + p; printf("%d\n", c); 1 11 2 27 3 33 4 35 5 44 33. 다음프로그램의출력결과는무엇인가? int a[8][8]= { {0,1,1,1,1,0,0,0, {1,1,0,0,0,1,1,1, {0,0,1,1,1,0,0,1, {0,0,1,0,1,0,1,1, - 12 -
{0,0,1,1,1,0,1,0, {0,0,0,0,1,1,1,0, {0,1,1,0,0,0,0,0, {0,1,1,0,0,1,1,1 ; void f(int n, int m) { if (n < 0 m < 0 n >= 8 m >= 8) return; if (a[n][m]!= 1) return; a[n][m] = 2; f(n - 1, m); f(n, m - 1); f(n + 1, m); f(n, m + 1); int main() { int i, j, g; g = 0; for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { if (a[i][j] == 1) { f(i, j); g = g + 1; printf("%d\n", g); return 0; 1 3 2 4 3 5 4 30 5 31 34. f(10) 의값은무엇인가? int f(int n) { int p[11][11]; int i, j, ret; for (i = 0; i <= n; i++) { for (j = 0; j <= n; j++) { p[i][j] = 0; - 13 -
p[0][0] = 1; for (i = 0; i <= n; i++) { p[i][0] = 1; for (j = 1; j <= i; j++) { p[i][j] = p[i - 1][j - 1] + p[i - 1][j]; ret = 0; for (i = 0; i <= n; i++) { ret = ret + p[n][i]; return ret; 1 511 2 512 3 513 4 1023 5 1024 35. 다음보기중에서가장큰값은무엇인가? int f(int n) { int a[10] = {0, t = 0, i; while (n > 0) { a[n % 10] = 1; n = n / 10; for (i = 0; i < 10; i++) { t = t + a[i] * i; return t; 1 f(711587) 2 f(999999) 3 f(614331) 4 f(843211) 5 f(914312) 36. 아래주어진함수 AmicableNumbers() 를호출했을때출력결과는무엇인가? int AN_helper( int num ) { int i, tot = 0; for (i = 1; i < num; i++) { if (num % i == 0) { - 14 -
tot = tot + i; return tot; void AmicableNumbers() { int i, num; for (i = 1; i < 1000; i++) { num = AN_helper(i); if (i < num && i == AN_helper(num)) { printf("%d %d\n", i, num); 1 100 117 2 120 240 3 127 128 4 220 284 5 496 496 37. 다음프로그램의출력결과는무엇인가? int a[10] = {3456, 7, 8976, 54, 53, 456, 7865, 45, 6734, 53; int i, b, cnt = 0; for (i = 0; i < 10; i++) { b = (a[i] & 1) (a[i] & 2); if (b == 0) cnt++; printf("%d\n", cnt); 1 0 2 1 3 2 4 3 5 4 38. 다음프로그램의출력결과에포함되지않는것은무엇인가? char l[10]; void f(int r, int s, int len) { if (r == 0 && s == 0) { printf("%s\n", l); if (r > 0) { l[len] = 'i'; f(r - 1, s + 1, len + 1); - 15 -
if (s > 0) { l[len] = 'o'; f(r, s - 1, len + 1); int main() { int i; for (i = 0; i < 10; i++) { l[i] = '\0'; f(4, 0, 0); return 0; 1 iioooiio 2 ioioioio 3 iiiioooo 4 iioiiooo 5 ioiioioo [39-40] 다음과같은문제를해결하기위해프로그램을작성하였다. 물음에답하시오. KOI 장거리달리기대회가진행되어모든선수가반환점을넘었다. 각선수의입장에서자기보다앞에달리고있는선수들중평소실력이자기보다좋은선수를남은거리동안앞지르는것은불가능하다. 반대로, 평소실력이자기보다좋지않은선수가앞에달리고있으면남은거리동안앞지르는것이가능하다. 이러한가정하에서각선수는자신이앞으로얻을수있는최선의등수를알수있다. 각선수의평소실력은정수로주어지는데더큰값이더좋은실력을의미한다. 현재달리고있는선수를앞에서부터표시했을때평소실력이각각 2, 8, 10, 7, 1, 9, 4, 15 라고하면각선수가얻을수있는최선의등수는 ( 같은순서로 ) 각각 1, 1, 1, 3, 5, 2, 5, 1이된다. 예를들어, 4번째로달리고있는평소실력이 7인선수는그앞에서달리고있는선수들중평소실력이 2인선수만앞지르는것이가능하고평소실력이 8과 10인선수들은앞지르는것이불가능하므로, 최선의등수는 3등이된다. 선수들의평소실력을현재달리고있는순서대로입력받아서각선수의최선의등수를계산하는프로그램을작성하시오. 입력형식 입력파일의이름은 INPUT.TXT이다. 첫째줄에는선수의수를의미하는정수 N이주어진다. N은 3 이상 500,000 이하이다. 다음줄에는 N개의정수가주어진다. 이값들은각선수들의평소실력을앞에서달리고있는선수부터제시한것이다. 각정수는 1 이상 1,000,000,000 이하이다. 단, 참가한선수들의평소실력은모두다르다. - 16 -
출력형식 출력파일의이름은 OUTPUT.TXT 이다. 각선수의최선의등수를나타내는정수 N 개를입 력에주어진선수순서와동일한순서로한줄에출력한다. 모든정수들사이에는하나의 공백을둔다. 입력과출력의예 입력 (INPUT.TXT) 8 2 8 10 7 1 9 4 15 출력 (OUTPUT.TXT) 1 1 1 3 5 2 5 1 프로그램 #include <stdio.h> #define MAXN 500000 struct Info { int value, index, answer; ; struct Info info[maxn], temp[maxn]; int answer[maxn]; int n; void merge(int left, int right) { if (left >= right) return; int i, l, r, mid; mid = (left + right) / 2; merge(left, mid); merge(mid + 1, right); l = left, r = mid + 1; for (i = left; i <= right; i++) { if ( (a) ( (b) && (c) )) { temp[i] = info[l++]; - 17 -
else { temp[i] = info[r++]; temp[i].answer += mid - l + 1; for (i = left; i <= right; i++) { info[i] = temp[i]; int main() { int i; FILE *fi, *fo; fi = fopen("input.txt", "r"); fscanf(fi, "%d", &n); for (i = 0; i < n; i++) { fscanf(fi, "%d", &info[i].value); info[i].index = i; fclose(fi); merge(0, n - 1); for (i = 0; i < n; i++) { answer[info[i].index] = info[i].answer; fo = fopen("output.txt", "w"); for (i = 0; i < n; i++) { fprintf(fo, "%d ", answer[i] + 1); fclose(fo); return 0; 39. 다음중빈칸 (a), (b), (c) 에들어갈내용으로알맞게짝지어진것은? 1 2 3 (a) r > right (b) l <= mid (c) info[l].value > info[r].value (a) r >= right (b) l < mid (c) info[l].value < info[r].value (a) r > right - 18 -
4 5 (b) l <= mid (c) info[l].value < info[r].value (a) l > mid (b) r <= right (c) info[l].value > info[r].value (a) l > mid (b) r <= right (c) info[l].value < info[r].value 40. 입력파일이다음과같이주어졌을때, 위프로그램의출력은무엇인가? 10 3 12 16 1 10 2 11 7 15 13 1 1 1 1 4 3 4 3 5 2 3 2 1 1 1 3 3 5 3 5 2 3 3 1 1 1 4 3 5 4 5 2 3 4 1 1 1 4 3 5 3 5 1 3 5 1 1 1 4 3 5 3 5 2 3-19 -
- 20 -
2013 시도예선중고등부정답 1. 2 2. 3 3. 2 4. 2 5. 1 6. 3 7. 1 8. 4 9. 2 10. 1 11. 3 12. 4 13. 5 14. 3 15. 1 16. 4 17. 1 18. 3 19. 1 20. 2 21. 4 22. 3 23. 3 24. 2 25. 5 26. 5 27. 2 28. 2 29. 4 30. 1 31. 2 32. 3 33. 2 34. 5 35. 1 36. 4 37. 4 38. 1 39. 3 40. 5-21 -