| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 112 | 58 | 46 | 56.098% |
'궁수의 전설'을 즐기는 수학토끼는 '궁수의 전설'을 패러디한 게임인 '토끼의 전설'을 만들었다. 이 게임에는 특이한 캐릭터 업그레이드 시스템이 고안되어 있다.
수학토끼는 마법 주문서의 밸런스를 맞추기 위해 공격력이 체력의 $x$배 이상이 되게 하기 위한 최소 비용을 알아내고 싶다. $Q$개의 캐릭터의 기본 체력 $C$와 기본 공격력 $P$가 주어질 때마다, $N$개의 주문서 중 일부를 활용해 공격력이 체력의 $x$배 이상이 되도록 만들 수 있는지 판별하고, 그것이 가능한 경우 최소 비용을 출력하라. (주문서를 하나도 활용하지 않아도 되고, 주문서를 모두 활용해도 된다.)
엄밀히 말하면, $Q$개의 $(C, P)$ 쌍이 주어질 때마다 다음을 만족시키는 집합 $S \subseteq \{1, 2, \cdots, N\}$들에 대해 가능한 $\sum_{i \in S} {p_i}$의 최솟값을 출력하면 된다.
$$ \frac{P + \sum_{i \in S} p_i}{C + \sum_{i \in S} c_i} \geq x $$
첫 번째 줄에 마법 주문서의 종류의 수 $N$이 주어진다.
두 번째 줄에 $N$개의 정수 $c_1, c_2, \cdots, c_N$가 공백으로 구분되어 주어진다.
세 번째 줄에 $N$개의 정수 $p_1, p_2, \cdots, p_N$가 공백으로 구분되어 주어진다.
네 번째 줄에 $x = \frac{a}{b}$의 분자 $a$와 분모 $b$가 공백으로 구분되어 주어진다.
다섯 번째 줄에 캐릭터의 개수 $Q$가 주어진다.
이후 $Q$개의 줄 중 $j$번째 줄에 $j$번째 캐릭터의 $C$와 $P$의 값이 공백으로 구분되어 주어진다. $(1 \leq j \leq Q)$
각 캐릭터에 대한 최소 비용을 $Q$개의 줄에 걸쳐 한 줄에 하나씩 출력한다. 만약 불가능한 경우 -1을 출력한다.
5 1 2 3 4 5 5 4 3 2 1 1 2 3 500 500 500 1 11 5
0 -1 3
$N=5$이므로 다섯 개의 마법 주문서가 있다. 각 마법 주문서의 체력 증가량과 공격력 증가량은 $(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)$이다. 그리고 $x=\frac{a}{b}=\frac{1}{2}$이다.
$Q=3$이므로 세 개의 캐릭터에 대한 답을 구해야 한다.
첫 번째 캐릭터의 능력치는 $C=500, P=500$이다. 마법 주문서를 하나도 사용하지 않아도 조건을 만족시킬 수 있다. 따라서 답은 0ドル$이다.
두 번째 캐릭터의 능력치는 $C=500,P=1$이다. 모든 경우에 조건을 만족하지 않는다. 따라서 -1을 출력해야 한다.
세 번째 캐릭터의 능력치는 $C=11, P=5$이다. 3번 마법 주문서만 사용하는 것이 최적이다. 따라서 답은 3ドル$이다.
School > 서울과학고등학교 > SciOI 2024 C번