레이팅 미적용농부 존은 사랑하는 소 베시와 함께 유명한 전략 카드 게임을 하고 있다. 농부 존은 \(1\)부터 \(N\)까지 편리하게 번호가 매겨진 \(N\) (\(2\le N\le 2\cdot 10^5\))장의 카드를 가지고 있다. \(i\)번째 카드를 내려면 무우릭서 \(a_i\) (\(1 \leq a_i \leq 10^9\))가 든다.
그의 패는 언제나 \(H\)장의 카드로 이루어진다 (\(1\le H
이 게임에서 시간은 정수 초 단위로 측정된다. 게임은 시각 \(0\)에 농부 존이 무우릭서 \(0\)을 가진 상태로 시작한다. 각 정수 시각 \(t=1,2,3,\dots\) 직전에 무우릭서가 \(1\)씩 증가한다. 각 정수 시각에 농부 존은 패에 있는 카드의 비용이 현재 무우릭서 개수를 넘지 않으면 그 카드를 낼 수 있으며, 이때 현재 무우릭서 개수에서 카드의 비용만큼 차감된다.
농부 존은 자신의 카드 중 부분집합 \(s_1, s_2, \ldots, s_k\)를 승리 조건으로 표시한다 (\(1\le k\le N\), \(1\le s_i\le N\)). 농부 존의 패에 승리 조건 카드가 하나라도 있으면, 다음에 내는 카드는 반드시 승리 조건 카드여야 한다.
그는 \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\))개의 쿼리를 묻는다. 각 쿼리는 다음과 같은 형태이다: 시간 \(t\) (\(1 \leq t \leq 10^{18}\)) 안에 낼 수 있었던 승리 조건 카드의 최대 개수는 얼마인가?
문제 제공: Chongtian Ma
채점 방식
- 입력 2-3: \(N,Q\le 100\)
- 입력 4-5: \(H=1\)
- 입력 6-11: 추가 제약 조건이 없다.
문제 제공: Chongtian Ma
첫째 줄에 \(N\)과 \(H\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \ldots, a_N\)이 주어진다.
셋째 줄에 승리 조건 카드의 수인 정수 \(k\)가 주어진다.
넷째 줄에 \(k\)개의 서로 다른 정수 \(s_1, s_2, \ldots, s_k\)가 주어진다.
다섯째 줄에 정수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄 각각에 각 쿼리에서 답해야 할 시간인 정수 \(t\)가 주어진다.
각 쿼리마다, 시간 \(t\) 안에 농부 존이 낼 수 있었던 승리 조건 카드의 최대 개수를 출력한다.
6 3
2 4 3 5 7 6
2
1 4
6
1
2
3
7
10
10000000000000000
1
1
2
2
142857142857143In this case, you start with card 1, a win condition on your hand. You can play
it after you accumulate 2 elixir in 2 seconds. This means that just after t=1
you can play no cards, but after t=2 you can play your first card, which must
be your win condition.
After t=3, it is still most optimal to play card 1 and have 1 elixir remaining,
so the answer here is still 1.
You then draw card 4, which is also a win condition. You play it immediately
after t=7, so you have played 2 win conditions at this time.
You then draw card 5 and have no win conditions in your hand. After t=10, even
if you play card 3 with the 3 elixir you have, your number of win conditions
does not change.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Silver