| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 67 | 39 | 33 | 56.897% |
이 문제는 함수 구현 문제입니다.
경곽이에게 수많은 거짓말을 하도록 강요받아 온 구름이는 마침내 그 배후를 폭로했다. 구름이에게 거짓말을 지시한 단체는 부장 곽경이를 필두로 한 정보과학 모임 너는코더냐이다. 이로 인해 정보과학 모임 너는코더냐의 모든 부원은 협박죄로 감옥에 수감되었다. 너는코더냐의 부원 수는 곽경이를 포함하여 $N$명이며, $N$은 홀수이다. 이들은 교도소에서 $1$번부터 $N$번까지의 번호를 부여받았고, 부장인 곽경이는 $1$번 수감자이다.
어느 날 이들을 감시하던 감시관은 정보과학을 좋아하는 수감자들에게 감동을 받아 가석방의 기회를 주기로 하고, 게임을 하나 제안했다. 감시관은 다음과 같은 방식으로 게임을 진행한다.
너는코더냐 부원 중 가장 정보과학에 능한 부장 곽경이는, 모두를 배신하고 혼자만 가석방되기 위한 계획을 세운다. 곽경이를 제외한 모든 부원은 그를 신뢰하므로, 곽경이가 제시하는 전략을 그대로 따른다. 너는코더냐의 부원들은 모두 충분히 똑똑하여, 곽경이의 전략을 모두 따랐음에도 가석방되지 않는 사람이 생기면 곧바로 눈치챌 수 있다. 따라서 곽경이는 자신을 포함한 모든 부원이 전략을 정확히 따를 때, 단 한 명도 빠짐없이 가석방될 수 있는 전략을 제시해야 한다. 반대로 4에서 곽경이만 자신의 전략과 반대되는 값을 외친다면, 그의 의도대로 곽경이 혼자만 가석방되어야 한다. 곽경이가 부원들에게 제시할 적절한 전략을 설계하자.
여러분은 각 수감자의 역할을 맡아, 해당 수감자가 얻을 수 있는 정보만을 사용하여 채점기에 맞게 전략을 수행해야 한다.
함수 구현에 앞서 #include "liar.h"를 통해 "liar.h" 헤더 파일을 포함해야 한다.
여러분은 아래 함수를 구현해야 한다.
int shout(int N, int a, int b, std::vector<int> S, int l, int r);shout 함수를 호출한 수감자의 번호이다. ($1 \leq a \leq N$)shout 함수에서 호출된 순번이다. $b = 1$이면 해당 수감자부터 게임이 시작되며, $b = N$이면 해당 수감자가 마지막으로 외친다. ($1 \leq b \leq N$)shout 함수가 호출되기 전까지, 이미 shout 함수를 수행한 수감자들의 외침을 담은 길이 $N$의 배열이다. $S[i]$는 이전에 $i + 1$번 수감자가 이전에 외친 값이며, 아직 외치지 않았다면 $0$이다.shout 함수는 각 수감자에 대해 정확히 한 번씩 호출되며, 한 테스트 케이스 내에서는 호출 순서가 $b = 1, \, 2, \, \cdots, \, N$을 따른다.int answer(int N, int a, int b, std::vector<int> T, int l, int r);shout 함수와 동일하다.shout 함수에서 얻은 모든 수감자의 외침을 담은 길이 $N$의 배열이다. $T[i]$는 $i + 1$번 수감자가 shout 함수에서 외친 값이다.answer 함수는 $a$번 수감자가 독방에서 자신의 등에 적힌 수라고 주장할 값으로 $0$ 또는 $1$을 반환해야 한다. 반환값이 $0$ 또는 $1$이 아니면 를 받는다.answer 함수는 각 수감자에 대해 정확히 한 번씩 호출된다.answer 함수는 shout 함수가 총 $N$번 모두 호출된 이후에만 호출됨이 보장된다.채점 과정에서 하나의 데이터에서 최대 $50$개의 테스트 케이스가 실행될 수 있다. 테스트 케이스가 순서대로 실행된다는 보장은 하지 않지만, 한 테스트 케이스만 봤을 때 shout 함수는 순번의 순서대로 호출되며, shout 함수가 모두 실행된 후 answer 함수가 실행됨은 보장한다. answer 함수는 shout 함수가 호출된 순서로 호출됨을 보장하지 않는다.
하나의 테스트 케이스에 대해 채점은 총 두 번 이루어진다.
첫 번째 채점에서는 곽경이가 거짓말을 하지 않는 경우를 가정하며, 모든 수감자의 shout 함수의 반환값을 그대로 다음 수감자들에게 전달한다. 이때 answer 함수의 반환값은 각 수감자의 등에 실제로 적힌 값과 정확히 같아야 한다. 단 한 명이라도 실제 값과 answer 함수의 반환값이 다르면 를 받는다.
두 번째 채점에서는 곽경이가 거짓말을 하는 경우를 가정하며, 곽경이($1$번 수감자)에 한해서만 shout 함수의 반환값을 반전시켜 다음 수감자들에게 전달한다. 이때 answer 함수의 반환값은 곽경이는 자신의 등에 실제로 적힌 값과 같아야 하고, 곽경이를 제외한 모든 수감자는 자신의 등에 실제로 적힌 값과 달라야 한다. 단 한 명이라도 이 조건을 만족하지 않으면 를 받는다.
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
$N = 5$이며, $4$번 수감자부터 게임을 시작하는 상황을 생각해 보자. 그리고 $1$번 수감자부터 $5$번 수감자까지 각 수감자 뒤에 $0$, $1$, $1$, $0$, $1$이 쓰여 있다고 하자.
첫 번째 채점의 경우부터 살펴보자. 먼저, 그레이더는 $4$번 수감자에 대한 shout 함수를 호출한다.
shout(5, 4, 1, [0, 0, 0, 0, 0], 1, 1)shout 함수가 $1$을 반환했다고 하자. 다음으로 그레이더는 $5$번 수감자에 대한 shout 함수를 호출한다. 이때, $4$번 수감자가 이미 대답을 한 상황이므로 $S[3] = 1$이다.
shout(5, 5, 2, [0, 0, 0, 1, 0], 0, 0)shout 함수가 $0$을 반환했다고 하고, 다음으로 그레이더는 $1$번 수감자 곽경이에 대한 shout 함수를 호출한다.
shout(5, 1, 3, [0, 0, 0, 1, 0], 1, 1)shout 함수가 $1$을 반환했다고 하자. 첫 번째 채점이므로 곽경이의 반환값을 그대로 다음 수감자들에게 보낸다.
shout(5, 2, 4, [1, 0, 0, 1, 0], 0, 1) shout(5, 3, 5, [1, 1, 0, 1, 0], 1, 0)shout 함수 호출된 순서대로 $1, \, 0, \, 1, \, 1, \, 0$을 반환했다고 하자. 마지막 수감자까지 모두 shout 함수를 실행했으므로 그 다음으로는 그레이더는 answer 함수들을 실행한다. 이 상황에서 $T = [1, \, 1, \, 0, \, 1, \, 0]$이다.
answer(5, 1, 3, [1, 1, 0, 1, 0], 1, 1) answer(5, 2, 4, [1, 1, 0, 1, 0], 0, 1) answer(5, 3, 5, [1, 1, 0, 1, 0], 1, 0) answer(5, 4, 1, [1, 1, 0, 1, 0], 1, 1) answer(5, 5, 2, [1, 1, 0, 1, 0], 0, 0)첫 번째 채점이므로 곽경이를 포함한 모든 부원이 자신의 등 뒤에 쓰인 숫자를 맞혀야 한다. 즉, answer 함수는 순서대로 $0, \, 1, \, 1, \, 0 , \, 1$을 반환해야 한다.
이제 두 번째 채점을 살펴보자. 곽경이의 순서까지는 첫 번째 채점과 같으며, 곽경이의 순서부터는 곽경이의 반환값을 반전하여 다음 수감자들에게 보낸다. 즉, 다음 순서인 $2$번 수감자는 곽경이의 shout 반환값인 $1$ 대신에 $0$을 받는다.
shout(5, 2, 4, [0, 0, 0, 1, 0], 0, 1) shout(5, 3, 5, [0, 0, 0, 1, 0], 1, 0)shout 함수 호출된 순서대로 $1, \, 0, \, 1, \, 0, \, 1$을 반환했다고 하자. 그 다음으로는 그레이더는 answer 함수들을 실행한다. 이 상황에서 $T = [0, \, 0, \, 1, \, 1, \, 0]$이다. 곽경이의 shout 함수의 반환값은 $1$이지만, $T$에서는 $0$으로 들어가는 것에 유의하라.
answer(5, 1, 3, [0, 0, 1, 1, 0], 1, 1) answer(5, 2, 4, [0, 0, 1, 1, 0], 0, 1) answer(5, 3, 5, [0, 0, 1, 1, 0], 1, 0) answer(5, 4, 1, [0, 0, 1, 1, 0], 1, 1) answer(5, 5, 2, [0, 0, 1, 1, 0], 0, 0)두 번째 채점이므로 곽경이만 자신의 등 뒤에 쓰인 숫자를 맞혀야 한다. 즉, answer 함수는 순서대로 $0, \, 0, \, 0, \, 1 , \, 0$을 반환해야 한다.
Sample grader는 첫 번째 줄에 테스트 케이스의 개수 $T$를 입력받는다. 그 이후 $T$회에 걸쳐 다음과 같은 정보를 입력받는다:
$s$는 처음 게임을 시작하게 되는 수감자의 번호, $e_1, \, e_2, \, \cdots, e_N$는 각 수감자들 등 뒤에 쓰여있는 숫자를 의미한다.
Sample grader는 각 테스트 케이스에 대해 다음을 출력한다.
Invalid Range를 출력한다.shout 함수와 answer 함수의 반환값이 $0$ 또는 $1$이 아니면 Wrong Answer를 출력한다.Wrong Answer [1]을 출력한다.Wrong Answer [2]를 출력한다.Accepted를 출력한다.Invalid Range 또는 Wrong Answer를 출력할 시, Sample grader는 즉시 종료된다.
Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.
School > 경기과학고등학교 > 나는코더다 송년대회 > 나는코더다 2025 송년대회 C번
C++17