| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 258 | 69 | 59 | 28.922% |
감옥에 500ドル$명의 죄수가 갇혀 있다. 어느날, 간수는 감옥에서 나갈 수 있는 기회를 주었다. 간수가 방 안에 동전이 든 두 개의 가방 A와 B를 놓았다. 각 가방에는 1ドル$ 개 이상 $N$ 개 이하의 동전이 들어 있다. 두 가방에 든 동전의 개수는 다르다. 간수는 죄수들에게 도전 기회를 준다. 죄수들의 목표는 동전이 적게 든 가방을 찾는 것이다.
방에는 동전이 든 가방 외에도 칠판이 있다. 칠판에는 항상 정수 하나만 쓸 수 있다. 처음에는 칠판에 0ドル$이 쓰여 있다.
간수는 죄수들에게 한명씩 차례로 방에 들어오게 한다. 모든 죄수는 다른 죄수중 누가 자기보다 먼저 이 방에 들어 왔는지 알지 못하고, 또 자기 앞에 몇 명의 죄수가 방에 들어왔는지도 알지 못한다. 매번 죄수가 방에 들어올 때마다, 칠판에 쓰여진 정수를 읽는다. 이 정수를 읽은 다음, 가방 A와 B 중 하나를 골라야 한다. 다음 이 가방을 조사해서 이 가방에 몇 개의 동전이 있는지 알게 된다. 그 다음 죄수는 다음 두 행동 중 하나를 해야 한다.
한번 방을 나간 죄수는 간수가 다시 방에 들여보내지 않는다.
만약 죄수 중 한 명이 동전이 적게 든 가방을 정확히 맞추면 죄수들이 도전에서 이긴다. 만약 죄수 중 한 명이라도 동전이 적게 든 가방을 틀리거나, 500ドル$명의 죄수 모두가 방에 들어갔다 나왔지만 동전이 적게 든 가방을 맞추려고 아무도 시도하지 않았다면 죄수들이 진다.
도전을 시작하기 전에, 죄수들은 강당에 모여서 3단계로 이루어지는 다음 공통 전략을 정했다.
죄수들이 도전에서 이기면, 간수는 죄수들을 $x$일간 더 가둔 다음에 모두 풀어줄 것이다.
당신이 할 일은 죄수들이 이 도전을 이길 수 있는 전략을 고안하는 것이다. (가방 A, B에 있는 동전 개수와 무관하게) 여러분이 제출한 해법의 점수는 $x$의 값에 따라 달라진다. (자세한 내용은 Subtasks 참조)
다음 함수를 구현해야 한다.
int[][] devise_strategy(int N)
다음 호출을 생각해보자.
devise_strategy(3)
$v$가 죄수가 방에 들어왔을 때 칠판에 쓰여진 정수라고 하자. 정답을 내는 전략 중 하나는 다음과 같다.
이 전략을 표현하려면 함수는 [[0, -1, 1, -2], [1, -2, 0, -1]]를 리턴해야 한다. 리턴된 배열의 길이는 2ドル$이고, $x$의 값은 2ドル - 1 = 1$이다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N \le 500,ドル $x$는 500ドル$ 이하여야 한다. |
| 2 | 5 | $N \le 500,ドル $x$는 70ドル$ 이하여야 한다. |
| 3 | 90 | $x$는 60ドル$ 이하여야 한다. |
만약 테스트 케이스 중 어느 경우에서든, devise_strategy가 리턴한 배열이 정확한 전략을 나타내지 않는 경우, 이 서브태스크에 대해서 당신은 0ドル$점을 얻는다.
서브태스크 3은 부분 점수가 있다. 이 서브태스크에 대해서 리턴한 모든 배열에서 $x$ 값의 최대가 $m$이라고 하자. 이 서브태스크에서 당신의 점수는 다음 표와 같다.
| 조건 | 점수 |
|---|---|
| 40ドル \le m \le 60$ | 20ドル$ |
| 26ドル \le m \le 39$ | 25ドル + 1.5 \times (40 - m)$ |
| $m = 25$ | 50ドル$ |
| $m = 24$ | 55ドル$ |
| $m = 23$ | 62ドル$ |
| $m = 22$ | 70ドル$ |
| $m = 21$ | 80ドル$ |
| $m \le 20$ | 90ドル$ |
샘플 그레이더는 다음 양식으로 입력을 읽는다.
첫 줄과 마지막 줄을 제외한 각각의 줄들은 시나리오를 설명한다. 시나리오 $k$는 2ドル+k$ 번째 줄에 설명되어 있다. 시나리오 $k$에서는 가방 A에 $A[k]$개의 동전이 있고, 가방 B에 $B[k]$ 개의 동전이 있다.
샘플 그레이더는 먼저 devise_strategy(N)를 호출한다. $x$의 값은 이 호출에서 리턴한 배열의 길이에서 1을 뺀 값이다. 이때, 샘플 그레이더가 devise_strategy가 리턴한 배열이 Implementation Details에서 설명한 제약 조건을 따르지 않는다면, 다음 에러 메시지 중 하나를 출력하고 종료한다.
s is an empty array: $s$가 길이가 0인 배열이다. (타당한 전략을 표현하지 않는다)s[i] contains incorrect length: $s[i]$의 길이가 $N + 1$가 아닌 인덱스 $i$ (0ドル \le i \le x$)가 있다.First element of s[i] is non-binary: $s[i][0]$의 값이 0ドル$ 또는 1ドル$가 아닌 인덱스 $i$ (0ドル \le i \le x$)가 있다.s[i][j] contains incorrect value: $s[i][j]$의 값이 $-2$ 이상 $x$ 이하가 아닌 인덱스 $i, j$ (0ドル \le i \le x, 1 \le j \le N$)가 있다.그렇지 않다면, 샘플 그레이더는 두 가지 출력을 한다.
먼저, 샘플 그레이더는 다음 양식으로 여러분의 전략의 결과를 출력한다.
A이다. 만약 이 전략을 써서 죄수가 가방 B를 동전이 적은 쪽으로 골랐다면, 출력은 글자 B이다. 만약 이 전략을 썼는데 어느 죄수도 동전이 적은 쪽 가방을 고르지 못했다면, 출력은 글자 X이다.또한, 샘플 그레이더는 현재 디렉토리에 log.txt 파일을 다음 양식으로 출력한다.
1ドル + k$번째 줄에 출력된 수열은 시나리오 $k$에서 칠판에 쓰여지는 정수들이다. 보다 구체적으로, $w[k][l]$는 방에 $l+1$ 번째 들어간 죄수가 칠판에 쓰는 정수이다.
Olympiad > International Olympiad in Informatics > IOI 2022 > Day 1 2번
C++17, C++20, C++17 (Clang), C++20 (Clang)