코알라 게임

코알라는 새로운 게임을 만들고 여러분에게 도전장을 내밀었다! 먼저 0부터 N-1까지 번호가 붙은 N개의 물건을 놓는다. 그다음 각 물건 i에 1과 N 사이의 정수를 하나씩 비밀리에 부여하는데, 두 물건이 같은 값을 받는 일은 없다. 물건 i에는 값 Pi가 부여된다. 코알라는 이 값의 수열 P = P0, P1, ..., PN-1의 몇 가지 성질을 알아내라고 도전한다.

이를 위해 코알라와 여러 라운드를 진행한다. 각 라운드에서 여러분은 파란 돌 W개를, 코알라는 빨간 돌 W개를 받는다. 여러분이 먼저 원하는 물건 몇 개 옆에 자신의 돌을 일부 또는 전부 놓는다. 코알라는 여러분의 배치를 보고 물건 몇 개 옆에 자신의 돌을 일부 또는 전부 비슷하게 놓는다. 그다음 코알라는 자신 옆에 놓인 빨간 돌이 파란 돌보다 엄격히 많은 모든 물건을 가져간다. 코알라는 자신이 가져가는 물건의 값 합이 최대가 되도록 항상 돌을 배치한다. 그런 배치가 여러 가지라면 가져가는 물건 수가 최대가 되도록 고른다. 그래도 여러 가지라면 그중 아무거나 고른다.

코알라는 매우 게으르기 때문에 라운드를 너무 많이 진행하면 잠들어 버린다. 여러분의 임무는 최대한 적은 라운드를 진행해 코알라의 수열 P에서 규칙을 찾아내는 것이다.

이 문제에서는 minValue, maxValue, greaterValue, allValues 네 함수를 구현해야 한다. 각 함수는 수열 P의 서로 다른 성질을 알아내야 한다. 풀이를 시작할 때 각 언어의 템플릿 구현을 출발점으로 삼기를 권한다. 일부 부분문제만 풀더라도 네 함수 모두 구현해야 한다(일부 구현은 비어 있어도 된다). 프로그램은 표준 입력을 읽거나 표준 출력에 쓰거나 파일과 상호작용해서는 안 된다.

각 함수에서 매개변수 N은 게임에 있는 물건 수이고, 매개변수 W는 각 라운드에서 여러분과 코알라가 사용하는 돌의 수이다.

• minValue(N, W) --- 값이 가장 작은 물건 번호 i, 즉 Pi = 1인 물건을 반환한다.
• maxValue(N, W) --- 값이 가장 큰 물건 번호 i, 즉 Pi = N인 물건을 반환한다.
• greaterValue(N, W) --- 물건 0과 1의 값을 비교해 값이 더 큰 물건 번호를 반환한다. 구체적으로 P0 > P1이면 0을, 그렇지 않으면 1을 반환한다.
• allValues(N, W, P) --- 수열 P 전체를 알아내어 주어진 배열 P에 넣는다. 구체적으로, 0 ≤ i ≤ N-1인 모든 i에 대해 P[i]에 물건 i의 값 Pi가 들어가야 한다.

각 테스트케이스에서 채점기는 이 함수 중 정확히 하나를 한 번 이상 호출한다. 각 함수 호출은 별개의 게임으로 취급한다. 어떤 함수가 호출되는지와 최대 몇 번 호출될 수 있는지는 부분문제에 따라 다르다(아래 참고). 각 함수 호출 전에 코알라는 수열 P를 고정하며, 함수가 실행되는 동안 수열은 바뀌지 않는다고 가정해도 된다. 다음 함수 호출 전에는 수열을 바꿀 수 있다.

각 함수의 구현은 playRound를 호출해 코알라의 수열에 대한 정보를 얻어야 한다.

• playRound(B, R) --- 코알라와 라운드를 진행한다.

  • 배열 B는 각 물건 옆에 파란 돌을 몇 개 놓는지 나타낸다. 구체적으로, 0 ≤ i ≤ N-1인 모든 i에 대해 번호 i인 물건 옆에 B[i]개의 파란 돌이 놓인다. 각 B[i]는 음이 아닌 정수여야 하고 합 B[0] + B[1] + ... + B[N-1]은 W를 넘지 않아야 한다.
  • 채점기는 주어진 배열 R을 채워 코알라의 응답을 나타낸다. 구체적으로, 0 ≤ i ≤ N-1인 모든 i에 대해 코알라는 번호 i인 물건 옆에 R[i]개의 빨간 돌을 놓는다.
  • 각 부분문제는 게임마다 playRound를 호출할 수 있는 횟수의 한계를 정한다. 이 한계보다 적게 호출하면 더 높은 점수를 받을 수 있다(아래 참고).