29795번 - 한 대 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 436 | 74 | 60 | 18.927% |
문제
메이플 스토리에는 블레싱 마하, 하울링같이 자신의 공격력을 변화시키는 버프 스킬이 있다. 메이플을 즐겨하는 20년차 고인물 임스는 공격 스킬만 쓰는 메이플에 질려 위의 예시와 같은 버프 스킬을 이용하여 자기만의 독특한 방식으로 보스를 잡아보려고 한다.
임스는 $N$개의 버프 스킬이 있는데, $i$번째 스킬은 공격력을 $a_{i}$ 배로 증가시키고 $b_{i}$ 만큼 더하는 스킬이다. 이때, $b_{i}$가 음수일 수도 있다. 만약 $a_{i} = 3$, $b_{i} = 5$이고 현재 공격력이 $x$라면, $i$번 스킬을 사용한 이후에 공격력이 $x\times3+5$로 변경된다. 스킬은 여러 번 사용이 가능하며, 사용한 순서대로 적용된다.
임스는 오늘도 $Q$개의 던전을 깨려고 한다. 각 던전에는 보스가 존재하는데, 보스마다 체력이 다르다. 또한, 보스마다 레벨과 방어율 등이 달라 임스의 초기 공격력은 임스가 상대하는 보스에 따라 다르다.
임스의 공격력이 보스의 체력과 같거나 높아지면 보스를 한 대에 잡을 수 있다. 이때, 단 한 대에 보스를 잡기 위해선 최소 몇 번의 스킬을 사용해야 할까?
입력
첫째 줄에 스킬의 수 $N$과 던전의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N,Q \le 300\,000)$
둘째 줄부터 $N$개의 줄에 $i$번 스킬의 정보인 $a_{i}$, $b_{i}$가 공백으로 구분되어 주어진다. $(1 \le a_{i} \le 1\,000\,000; -10^{9} \le b_{i} \le 10^{9})$
이후 $Q$개의 줄에 $i$번째 던전에서 초기 공격력을 나타내는 $x_{i}$와 던전 보스의 체력 $y_{i}$가 주어진다. $(1 \le x_{i}, y_{i} \le 10^{12})$
출력
각각의 던전마다 보스를 한 대에 잡기 위해 사용해야 하는 최소 스킬 사용 횟수를 한 줄에 하나씩 출력한다.
주어진 스킬로 보스를 한 대에 잡을 수 없는 경우 -1을 출력한다.
예제 입력 1
3 2 1 8 2 3 3 5 3 14 1 32
예제 출력 1
1 2
예제 입력 2
2 4 2 -3 1 0 6 8 5 8 4 8 3 8
예제 출력 2
1 2 3 -1
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호