| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 226 | 48 | 44 | 29.333% |
이 문제는「낚시 (Easy)」문제의 어려운 버전으로, 입력 조건, 변수 범위, 문제 상황 등은 동일하지만 정답으로 요구되는 출력 형식이 다릅니다.
”낚시란, 더 큰 것을 얻기 위해 작은 것을 바치는 것이다.”
— 그런 말 한 사람 없음
2025년의 모든 시험과 과제를 끝마친 당신은 마음의 평화를 찾기 위해 낚시터를 찾았다.
현재 낚시터에는 $M$마리의 물고기가 있으며, 당신은 $N$개의 떡밥을 가지고 있다. 각 물고기와 떡밥은 양의 정수 값의 가치를 가진다.
당신은 가지고 있는 떡밥을 활용하여 원하는 만큼 낚시를 할 수 있다. 이때 가지고 있는 떡밥들 중 하나 이상을 골라 낚싯대에 달고 낚시를 하면, 사용한 떡밥을 모두 잃는 대신 낚시터에 있는 물고기들 중 당신이 사용한 떡밥의 가치의 총합보다 큰 가치의 물고기가 잡힌다. 만약 이러한 물고기가 하나 이상이라면 이들 중 가장 낮은 가치의 물고기가 잡히게 되며, 사용한 떡밥의 가치의 총합보다 높은 가치의 물고기가 없다면 물고기가 잡히지 않는다. 잡은 물고기는 당신이 보유하게 된다.
이때, 가지고 온 $N$개의 떡밥 외에 낚시를 통해 얻은 물고기 한 마리를 소모하여 같은 가치의 떡밥 한 개를 만들 수 있다. 떡밥 만들기는 낚시를 진행하는 중이라면 아무 때나 원하는 만큼 진행할 수 있다.
당신은 낚시를 마친 후 보유한 물고기들의 가치의 합을 최대화하려고 한다. 슬기롭게 낚시를 진행하여 최고의 낚시꾼이 되어보자!
첫째 줄에 보유한 떡밥의 수 $N$과 낚시터에 있는 물고기의 수 $M$이 공백으로 구분되어 주어진다.
둘째 줄에 보유한 떡밥 $N$개의 가치 $b_1,ドル $b_2,ドル $\cdots,ドル $b_N$이 공백으로 구분되어 주어진다.
셋째 줄에 낚시터에 있는 물고기 $M$마리의 가치가 $f_1,ドル $f_2,ドル $\cdots,ドル $f_M$이 공백으로 구분되어 주어진다.
첫째 줄에 진행할 낚시와 떡밥 만들기의 횟수의 합 $Q$을 출력한다.
둘째 줄부터 $Q$개의 줄에 걸쳐 진행할 행동을 차례대로 하나씩 출력한다.
fish b1 b2 b3 ... bi와 같이 출력한다.bait f와 같이 출력한다.그 다음 줄에 위 행동의 결과로 최종적으로 보유한 물고기의 가치의 합 $S$를 출력한다.
출력한 모든 행동이 유효하고, $S$보다 더 큰 물고기 가치 합을 얻을 수 있는 방법이 존재하지 않는다면 정답으로 인정된다. 또한, 가능한 방법이 여러 개여도 하나만 출력하면 된다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | $N=1,ドル 즉 초기에 떡밥이 1개이다. |
| 2 | 88 | 추가적인 제한 조건이 없다. |
5 3 2 2 6 7 8 8 10 11
3 fish 2 2 6 fish 8 fish 7 29
2 3 1 9 5 10 11
4 fish 9 fish 1 bait 5 fish 5 21
School > 서울과학고등학교 > SciOI 2025 B2번