No.231 Meguru Goes Around (1)
タグ : / 解いたユーザー数 438
作問者 :
LayCurse
Problem Statement
Charo, Senpai!
You're saying I look troubled?
You're weirdly sharp today, at least for you, Senpai...
I've only just now reached exactly level $98$, so I have $0$ experience points, and I want to hit the level cap before tomorrow's Gv to keep up my dignity, but the death penalty is harsh, so I'm wondering which hunting ground would be good...
For example, this hunting ground gives an experience efficiency of about $200{\rm k}/{\rm h}$, but I end up dying about $3$ times per $1$ hour...
What, you don't get what I'm saying?
I'll explain it so that even you can understand, Senpai!
So this is about which dungeon to level up in. There are $N$ dungeons, and in dungeon $i$ you get about $G_i$ experience points per $1$ hour.
That part is fine, but every time you die, you lose $1\%$ of the experience points required to go from level $98$ to level $99$, that is, you lose $30000$ experience points!
And in dungeon $i$, I'd probably die about $D_i$ times per $1$ hour...
So if I level up in dungeon $i$ for $1$ hour, I'd gain about $G_i - 30000 D_i$ experience points.
I'll be leveling up while using an item whose duration is $1$ hour, so I want to stay in the same dungeon for $1$ hour at a time.
I plan to play for about $6$ hours from tonight until tomorrow morning, so I'm going to do $6$ sets of $1$-hour leveling. Which dungeons should I go to so that I level up by tomorrow morning?
The required experience is satisfied if you reach it "exactly" or "exceed" it. For the required experience, use the fact that $30000$ is 1%.
It is OK to go to the same dungeon multiple times.
You do not have to do the "change of pace" mentioned in the text below.
Even if you level up within 6 visits, make sure to go to dungeons 6 times.
Input
$N$ $G_1$ $D_1$ $G_2$ $D_2$ $\vdots$ $G_N$ $D_N$
$1 \leq N \leq 1000$
$1 \leq G_i \leq 1000000 = 10^6$
$0 \leq D_i \leq 100$
$G_i - 30000 D_i \geq 0$
Output
If I can reach level $99$ with $6$ hours of leveling, please output $\verb|YES|$ on line $1$.
On the next $6$ lines, output the numbers of the dungeons where I should level up!
Line $i$ is the number of the dungeon to go to in hour $i$, and it has to be a combination such that I'd be level $99$ after $6$ hours if I gain exactly the expected experience points!
Going to the same dungeon many times is fine, but, only if possible, I, Meguru, would like to go to various dungeons, since that makes for a nice change of pace...
Hey, wait, are you listening, Senpai!?
If it's impossible, you just output $\verb|NO|$ on $1$ line.
Also, this problem uses a special judge, so a format error probably goes straight to $\verb|WA|$...
It seems the samples are included in the judge's test cases too, so let's check them properly!
Sample
Sample 1
Input
3 1000000 0 1000000 0 1000000 0
Output
YES 1 2 3 1 2 3
These are the recently added dungeons of the $3$ attributes!
They're all efficient, and it's hard to die in them, so they're great!
Sample 2
Input
2 30000 1 300000 10
Output
NO
I guess all that's left is to recruit a temporary party and aim for a big comeback...
But I'm not good at that...
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。