Run 봄 연습 Mar 18 Mar 24, 2018, Week 3 문제 1. 초코바 입력 파일: 출력 파일: 시간 제한: 메모리 제한: standard input standard output 1 seconds 128 megabytes H W 격자 모양의 초콜릿이 있다.

Size: px

Start display at page:

Download "Run 봄 연습 Mar 18 Mar 24, 2018, Week 3 문제 1. 초코바 입력 파일: 출력 파일: 시간 제한: 메모리 제한: standard input standard output 1 seconds 128 megabytes H W 격자 모양의 초콜릿이 있다."

정희 미
5 years ago
Views:

1 문제. 초코바 H W 격자 모양의 초콜릿이 있다. 이 초콜릿을 개의 직사각형으로 격자를 따라서 잘라서, 최대 넓이의 초콜릿과 최소 넓이의 초콜릿의 넓이 차이를 최소화 하고 싶다. 이 차이의 최솟값을 구하여라. 첫째 줄에 H와 W 가 공백으로 구분되어 주어진다. 초콜릿을 개의 직사각형으로 자를 때, 최대 넓이의 초콜릿과 최소 넓이의 초콜릿의 넓이 차이의 최솟값을 구하여라. 서브태스크 ( 점) H, W 페이지 / 8

2 문제. 초청 강의 어느날, 혜아는 세미나에 초청강사로 두 초청강사를 초빙하였다. 바로 사과와 알렉스다! 교장선생님는 학생들을 사랑하기 때문에, 모든 N 개 반 학생들이 강의를 듣기를 원한다. 하지만 아쉽게도, RUN동방이 공사중이라 모든 N 개 반 학생들이 모여서 강의를 들을 수 없었다. 아쉬운대로, 사과와 알렉스가 N 개의 반을 적절히 돌아다니며, 강의를 하기로 하였다. 당연히, 같은 시간에 두 강사가 동시에 한 반에서 강의할 수 없고, 한 강사는 동시에 여러 반들을 대상으로 강의할 수 없다. N 개의 반은 각각 학생 수, 학생의 학년, 학생의 이해도에 따라 강의를 이해하는데 시간이 다를 수 있다. i 번째 반은 두 강사의 강의를 이해하는데 Ti 시간이 걸린다. 사과와 알렉스가 피곤하지 않게, 혜아는 모든 N 개의 반이 두 강사의 강의를 듣는 최소 시간을 구하고 싶다. N 개의 반의 강의 이해 시간 Ti 가 주어졌을 때, 모든 반이 두 강의를 듣기 위해 필요한 최소시간을 구하여라! 첫째 줄에 정수 N 이 주어진다. 둘째 줄에 공백으로 구분된 N 개의 정수가 주어진다. i번째 숫자는 Ti 이다. 모든 반이 두 강의를 모두 듣기 위해 필요한 최소시간을 구하여라. 서브태스크 (7 점) N 00, 000 Ti 00, 페이지 / 8

3 문제. 간장 공장 공장장 강한필은 간장 공장 공장장이다. 즉, 간장 공장 공장장은 강 공장장이다. 강 공장장은 N 개의 기계를 가지고 있는데, i번째 기계는 간장 한병을 준비하는데에 Ti 의 시간이 걸린다고 한다. 제품 공급을 요구 받은 강 공장장은 M 개의 간장 병들을 납품해야한다. M 개의 간장을 준비하는 최소시간을 구하여라. 첫째 줄에 정수 N 과 M 이 공백으로 구분되어 주어진다. 다음 N 개의 줄의 i번째 줄에 Ti 가 주어진다. M 개의 간장을 준비하는 최소 시간을 출력하여라. 서브태스크 ( 점) N 00, 000 M, 000, 000, 000 Ti, 000, 000, 페이지 / 8

4 문제. 문자 게임 혜아와 사과는 게임을 한다. 왼쪽부터 오른쪽까지 차례대로 N 개의 알파벳 소문자가 써 있는 종이가 있다. 각자 턴을 번갈아가면서 임의의 한 알파벳 소문자를 가져가며, 현재 자신의 단어의 뒤쪽에 붙인다. 게임에서 혜아가 먼저 시작하며, 모든 알파벳 소문자가 가져가지면 게임이 종료된다. 혜아는 항상 제일 오른쪽에 있는 알파벳 소문자를 가져간다고 할 때, 사과가 만들 수 있는 가장 사전순으로 앞선 단어를 구하여라. 첫째 줄에 정수 N 이 주어진다. 둘째 줄에 종이에 써있는 문자열 s가 주어진다. 사과가 만들 수 있는 가장 사전순으로 앞선 단어를 출력한다. 서브태스크 ( 점) N 00, 000 s는 알파벳 소문자로만 이루어져 있다. 8 cokolada acko 페이지 / 8

5 문제 5. 도시 연결 N 개의 도시가 있다. 기존에 N 개의 도시에는 서로 연결하는 도로가 M 개 있었다. 당신은 N 개의 도시를 군사적으로 연결하기 위해 도로를 부수거나, 건설하려고 한다. 도로를 군사적으로 연결한다는 것은 임의의 두 도시를 골랐을 때, 두 도시를 통행하는 길이 유일하게 하나 존재하여야 한다는 것이다. (기존에 건설되어 있는) 부술 수 있는 M 개의 도로가 있으며, i번째 도로는 Ai 도시와 Bi 도시를 연결하는 도로이며 부수는데 Ci 비용이 필요하다고 한다. 건설 할 수 있는 K개의 도로 후보가 있으며, i번째 도로 후보는 Di 도시와 Ei 도시를 연결하는 데에 Fi 비용이 필요하다고 한다. 당신은 도로들을 적절히 부수거나 건설하여, N 개의 도시를 군사적으로 연결하는 최소 비용을 구하려 한다. 첫 번째 줄에는 N, M, K가 공백으로 구분되어 주어진다. 두 번째 줄 부터 M 개의 줄에 걸쳐서 이미 건설되어 있는 도로의 정보가 주어진다. 각각의 줄은 Ai, Bi, Ci 가 공백으로 구분되어 주어진다. M + 번째 줄 부터 K개의 줄에 걸쳐서 건설 할 수 있는 도로의 정보가 주어진다. 각각의 줄은 Di, Ei, Fi 가 공백으로 구분되어 주어진다. 도로들을 적절히 부수거나 건설하여, N 개의 도시를 군사적으로 연결하는 최소 비용을 출력한다. 서브태스크 ( 점) N 00, 000 M 00, 000 K 00, 000 Ai, Bi, Di, Ei N Ci, Fi, 000, 000, 000 주어진 입력으로 N 개의 도시를 군사적으로 연결할 수 있음이 보장된다 페이지 5 / 8

6 문제. 고소 너 고소! 종범구단에는 N 명의 야구 선수가 있다. 코치는 경기 능력 향상을 위해 달리기 시합을 시키려 한다. 그런데, 이미 이 구단은 많은 데이터를 쌓아 누구의 달리기 속도가 얼마나 되는지를 이미 파악하고 있었다. 이에 결벽증이 있는 코치는 달리기 시합의 결과가 예쁘게 나오도록 하기 위해 달리기 속도에 따라 가장 빠른 사람을 부터 시작하여 가장 느린 사람을 N 번으로 선수 번호를 재배치하였다. 이러면 번부터 N 번까지의 선수가 차례대로 들어올 것이라고 예상한 것이다. 달리기 시합이 끝난 후, 결과를 보고 너무 놀라 뒷목을 잡고 쓰러지고 말았다. 아니, 예상했던 순서가 맞지 않는 것이 아닌가? 이에 코치는 야구계에 만연히 퍼져 있는 승부조작을 의심하고 이를 완전히 뿌리뽑기 위해 특단의 조치를 내걸었다. 예상과 다르게 나온 선수의 쌍을 모두 고소해 버리는 것이었다. 즉, i번째 선수의 경기 결과(들어온 시간)를 Ai 라고 할 때, i < j 이면서 Ai > Aj 인 모든 쌍을 고소한다는 것이다. 그러나 선수가 너무 많아 이를 일일이 세기 귀찮았던 코치는 이 경기 결과만을 들고 친구 변호사에게 갔다. 이제 이 변호사는 수임료를 계산하기 위해 고소할 선수의 쌍을 세야 한다. 역시 귀찮아하는 변호사는 당신에게 전체 수임료의 0%를 걸고 이 작업을 도와달라고 한다. 변호사를 도와 고소할 선수의 쌍을 빠르게 세는 프로그램을 제작해주자. 첫째 줄에 정수 N 이 주어진다. 둘째 줄에, 공백으로 구분된 N 개의 정수가 주어진다. i번째 수는 Ai 를 의미한다. 고소할 선수의 쌍의 갯수를 출력한다. 서브태스크 ( 점) N 00, 000 Ai N ( i N ) i = j = Ai = Aj ( i, j N ) 페이지 / 8

7 문제 7. RGB 수열 N 개의 숫자가 일렬로 나열 되어있다. 숫자는 부터 N 까지 왼쪽에서 오른쪽으로 차례로 번호가 붙어있다. 혜아는 M 개의 조건을 만족하면서 각 숫자에 빨강, 초록 혹은 파랑색을 칠하려고 한다. i번째 조건은 Li, Li +,, Ri 의 연속된 구간에 칠해진 색이 정확히 xi 종류여야 한다. 색을 칠하는 가짓수를 로 나눈 나머지를 출력하여라. 첫째 줄에 정수 N 과 M 이 공백으로 구분되어 주어진다. 다음 M 개의 줄의 i번째 줄에는 정수 세 정수 Li, Ri, xi 가 공백으로 구분되어 주어진다. 조건에 맞게 색을 칠하는 가짓수를 로 나눈 나머지를 출력하여라. 서브태스크 (8 점) N 00 M 00 li ri N xi 페이지 7 / 8

8 문제 8. 미지수 그래프 혜아는 다음 조건을 만족하는 그래프를 원한다.: 정점의 수인 N 은 00을 넘지 않는다. 루프나 다중간선이 없다. 정점은 부터 N 까지의 번호가 붙어있다. 각 단방향 간선에는 0이상 00이하의 숫자 혹은 X 나 Y 가 적혀 있다. 두 정점 중에 S와 T 가 각각 정해져 있다. x A, y B를 만족하는 모든 (x, y)쌍에 대해, X 라고 적힌 정점의 가중치를 x, Y 라고 적힌 정점의 가중치를 y, 숫자가 적힌 정점의 가중치는 적힌 숫자인 그래프가 있을 때, S에서 T 까지의 최단거리는 dx,y 여야 한다. 이런 그래프를 찾거나, 존재하지 않다면 존재하지 않다고 출력하여라. 첫째 줄에 정수 A와 B가 공백으로 구분되어 주어진다. 다음 A개의 줄에는 공백으로 구분된 B개의 정수가 주어진다. i번째 줄의 j번째 원소는 di,j 이다. 위의 조건을 만족하는 그래프가 존재하지 않으면 Impossible 을 출력하여라. (따옴표는 제외한다.) 만약 조건을 만족하는 그래프가 존재한다면, Possible 을 출력하여라. (따옴표는 제외한다.) 그리고 그 다음 줄에 N 과 M 을 공백으로 구분하여 출력하여라. 여기서 M 은 간선의 갯수이다. 다음 M 개의 줄에는 두 정수 u, v와 문자열 c를 공백으로 구분하여 출력하는데, 이는 u에서 v로 그어진 간선에 c라고 적혀있다는 것을 의미한다. 그 이후 다음 줄에 시작 정점과 끝 정점인 S와 T 를 공백으로 구분하여 출력한다. 서브태스크 (8 점) A, B 0 dx,y Possible X Y Y Impossible 페이지 8 / 8

Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo 단, Answer를 호출 할 때는, 다음의

Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo Problem A. Dungeon Input file: Output file: Time limit: Memory limit: second