問題
당신은 N개의 볼펜을 가지고 있다. 각 볼펜에는 0부터 N-1 사이(포함)의 서로 다른 정수 잉크량(단위)이 들어 있다는 것은 알고 있지만, 볼펜들이 무작위 순서로 주어졌기 때문에 어떤 볼펜이 어떤 잉크량인지 알 수 없다.
당신은 남극(펜이 없는 곳)으로 여행을 떠날 예정이고, 짐에는 펜 두 자루만 넣을 수 있다. 하지만 중요한 엽서 글쓰기를 많이 해야 하므로, 가져갈 두 펜의 남은 잉크량 합이 최소 N 단위가 되어야 한다.
펜에 대한 정보를 얻는 유일한 방법은 하나를 골라 실제로 무언가를 써 보는 것이다. 성공하면 그 펜의 잉크가 1단위 줄어든다(그리고 그 펜은 이제 비었을 수도 있다). 실패하면 그 펜은 원래부터 잉크가 하나도 없었다는 뜻이다. 같은 펜이든 다른 펜이든, 이 과정을 여러 번 반복할 수 있다.
결국 당신은 여행에 가져갈 두 펜을 선택해야 한다. 그 두 펜에 남아 있는 잉크의 합이 최소 N 단위이면 성공이다.
당신은 T개의 테스트 케이스를 받게 되며, 그중 적어도 C개에서 성공해야 한다. 또한 이 문제의 모든 테스트 세트는 Visible임에 유의하라.
例題
2 5 1
1 0
0 1
0 1
4 5
4 3
0 2
0 0
3 4 3 4
다음은 같은 상호작용을 설명한 것이다:
// 다음은 t에 2, n에 5, c에 1을 읽어온다.
t, n, c = readline_int_list()
// 채점기가 각 펜의 잉크량을 비밀리에 선택한다:
// 테스트 케이스 1: 2 0 4 1 3
// 테스트 케이스 2: 1 3 2 4 0
// 테스트 케이스 1에서는 4번 펜, 테스트 케이스 2에서는 5번 펜으로 쓴다.
printline 4 5 to stdout
flush stdout
// 1 0을 읽는다. 테스트 케이스 1의 4번 펜에는 잉크가 남아 있었고,
// 테스트 케이스 2의 5번 펜은 잉크가 없었다.
a1, a2 = readline_int_list()
// 테스트 케이스 1에서는 다시 4번 펜, 테스트 케이스 2에서는 3번 펜으로 쓴다.
printline 4 3 to stdout
flush stdout
// 0 1을 읽는다.
a1, a2 = readline_int_list()
// 이번에는 테스트 케이스 2에서만 쓴다. 2번 펜을 사용한다.
printline 0 2 to stdout
flush stdout
// 0 1을 읽는다.
a1, a2 = readline_int_list()
// 이제 답을 낼 준비가 되었다고 판단한다.
printline 0 0 to stdout
flush stdout
// 두 테스트 케이스 모두에서 3번과 4번 펜을 남극으로 가져간다.
printline 3 4 3 4 to stdout
flush stdout
// 테스트 케이스 1에서는 3번과 4번 펜의 남은 양이 4와 0이고 4+0<5이므로 실패.
// 테스트 케이스 2에서는 남은 양이 1과 4이고 1+4≥5이므로 성공.
// 총 2개 중 1개 성공했으며 c=1이므로 충분하다.
exit
出典
GCJ 2020r3 C
ログインしないとコードを書けません。