問題
한국과 일본의 카드 게임이 내일 진행된다.
두 나라는 각각 N장씩의 카드를 가지고 있다. ( 총 2N 장의 카드 )
각 카드에는 1 부터 10,000 까지의 자연수가 적혀 있다.
게임 규칙은 단순하다.
총 N 회차에 걸쳐 진행되고, 각 회차마다 두 나라는 남아 있는 카드 중 한 장을 낸다. ( 한 번 낸 카드는, 이후에 다시 낼 수 없다. )
숫자가 더 큰 카드를 낸 나라가 1점을 얻는다.
하지만, 만약 두 카드의 숫자가 동일하다면, 일본이 1점을 가져가게 된다 !!
예를 들어, N = 5 이며, 1회차 ~ 5회차 순으로
일본이 내는 카드가 [ 2, 3, 1, 4, 3 ]
한국이 내는 카드가 [ 3, 3, 2, 5, 1 ] 라면,
한국은 3 점을 획득하게 된다. ( 1회차, 3회차, 4회차 )
앞서 언급했듯이, 2회차에서는 두 나라 모두 숫자가 3으로 같지만, 일본이 점수를 가져간다.
이러한 편파 판정에 분노한 정올이.
게임 전날, 미리 일본 숙소에 잠입하여, 일본이 내는 카드의 순서를 미리 알아왔다.
이를 바탕으로 한국이 최대 점수를 얻기 위하여 카드를 어떻게 내면 될 지를 알고 싶다.
정올이를 도와주자.
輸入
첫 줄에 카드의 장수 N이 입력된다. ( 2 ≤ N ≤ 5,000 )
두 번째 줄에 일본이 1회차, 2회차, ... N회차에 낼 카드 숫자가 입력된다.
( 일본 측에서는 이 정보가 새어나간 사실을 모르기에, 이 순서는 바뀌지 않는다. )
세 번째 줄에 한국이 가지고 있는 N 장의 카드 숫자들이 입력된다.
네 번째 줄에 정올이의 질문 Q 가 입력된다. ( Q = 0 또는 1 )
輸出
Q = 0 이라면, 한국이 얻는 최대 점수만 출력한다. ( 카드 제시 순서는 출력하지 않는다. )
Q = 1 이라면, 최대 점수를 얻기 위해 한국이 제시해야 하는 N 장의 카드 순서를 출력한다. ( 최대 점수는 출력하지 않는다. )
( 만일 최대 점수를 얻는 카드 순서가 2가지 이상이라면, 그 중 사전 순으로 가장 뒤에 있는 것을 출력한다. )
(참고)
어떤 수열이 사전 순으로 가장 뒤에 있다는 것은,
첫 번째 숫자가 가장 큰 수열,
그러한 수열이 여러 개라면 그 중 두 번째 숫자가 가장 큰 수열,
그러한 수열이 여러 개라면 그 중 세 번째 숫자가 가장 큰 수열, ... 을 의미한다.
子任務
| 編號 | 分數 | 條件 |
|---|---|---|
| #1 | 20分 | 2 ≤ N ≤ 9 |
| #2 | 20分 | Q = 0 |
| #3 | 25分 | 2 ≤ N ≤ 200 |
| #4 | 35分 | 제약 조건 없음 |
範例 #1
5
2 3 9 3 8
1 6 2 5 8
0
3
Q = 0 이므로 최대 점수만 출력한다.
( 최대 점수는 3점 )
範例 #2
5
2 3 9 3 8
1 6 2 5 8
1
8 6 2 5 1
Q = 1 이므로, 최대 점수를 얻는 카드 배열만 출력한다.
최대 점수는 3점이고, 이를 달성하는 카드 배열은 [ 5, 6, 1, 8, 2 ], [ 6, 8, 2, 5, 1 ], .. 등등 여러 가지가 있지만,
사전 순으로 가장 뒤에 오는 것은 [ 8, 6, 2, 5, 1 ] 이다.
需要登入才能撰寫程式碼。