問題一覧 > 通常問題

No.231 めぐるはめぐる (1)

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 128 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 428
作問者 : LayCurseLayCurse
3 ProblemId : 535 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-25 01:10:48

問題文

ちゃろー、センパイ!
悩んでる顔してるって?
なんかセンパイにしては妙に鋭いですねー…。

今ようやくちょうどぴったりレベル $98$ になったところで経験値 $0$ なんですけど、明日のGvまでにレベルカンストして威厳を保ちたいなって思ってるんですけど、デスペナもきついし、どこの狩場がいいのかなーって…。
例えば、この狩場だと、経験値効率 $200{\rm k}/{\rm h}$ ぐらい出るんですけど、$1$ 時間あたりに $3$ 回ぐらい死んじゃうんですよねー…。
え、何言ってるかわからないですか?
センパイにもわかるように説明しますね!

どのダンジョンでレベル上げするかって話なんですけど、$N$ 個のダンジョンがあって、ダンジョン $i$ だと $1$ 時間あたりに経験値が $G_i$ ぐらいもらえるんです。
それはいいんですけど、死んじゃうとそのたびにレベル $98$ からレベル $99$ になるのに必要な経験値の $1\%$、つまり経験値が $30000$ だけ無くなるんですよー!
で、ダンジョン $i$ だと、多分 $1$ 時間あたりに $D_i$ 回ぐらい死んじゃうんですよね…。
だから、ダンジョン $i$ で $1$ 時間レベル上げしたら $G_i - 30000 D_i$ ぐらい経験値が得られるんですね。
持続時間が $1$ 時間のアイテム使いながらレベル上げするので、$1$ 時間は同じダンジョンでレベル上げをしたいんです。
今日の夜から明日の朝まで、$6$ 時間ぐらいはプレイするつもりなので、$1$ 時間のレベル上げを $6$ セットするつもりなんですけど、どのダンジョンに行けば明日の朝までにレベルが上がりますかね?

必要経験値は、「ちょうど」もしくは「超えれば」OKである。必要経験値は、$30000$が1%であることを利用してください。
複数回同じダンジョンに行ってもOKです。
下の文に出てくる気分転換はしなくても良いです。
6回以内にレベルアップしても6回ダンジョンに行くようにしてください。

入力

$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$

出力

$6$ 時間のレベル上げでレベル $99$ になれるなら、$1$ 行目に $\verb|YES|$ と出力して下さいね。
次の $6$ 行にはどのダンジョンでレベル上げすればいいかっていうダンジョンの番号を出力するんですよ!
$i$ 行目には $i$ 時間目にいくダンジョンの番号で、想定通りの経験値がちょうど得られるんだとしたら、$6$ 時間後にはレベル $99$ になってるような組み合わせじゃないとダメですよ!
同じダンジョンに何回も行くのはいいですけど、できればですけど、めぐるはいろんなダンジョンに行けたほうが気分転換ができていいんですよねー…。

って、ちょっとー、聞いてます、センパイ!?
不可能だったら $\verb|NO|$ と $1$ 行だけ出力すればいいんですからね。

後、この問題はスペシャルジャッジですから、フォーマットの不正は $\verb|WA|$ に直行ですかね…。
ジャッジのテストケースにサンプルも入っているみたいですから、ちゃんとチェックしましょうね!

サンプル

サンプル1
入力
3
1000000 0
1000000 0
1000000 0
出力
YES
1
2
3
1
2
3

最近追加された $3$ 属性のダンジョンですね!
どこも効率いいし、死ににくいし、いいんですよね!

サンプル2
入力
2
30000 1
300000 10
出力
NO

臨時パーティー募集して一発逆転を狙うしかないですかね…。
でもめぐる苦手なんですよね…。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。