首页 > ACM题库 > HDU-杭电 > hdu 2862 The Crazy O2jamer待解决[解题报告]C++
2014
02-17

hdu 2862 The Crazy O2jamer待解决[解题报告]C++

The Crazy O2jamer

问题描述 :

Dreamwind likes playing O2jam very much.

O2jam is a famous music game. In this game, the player will listen to the music, and many notes will appear on the screen and fall down from the top. When the notes move to the line on the botton of the screen, the player should press the correct keys just on time, and the system will judge your rate and give scores. Sometimes there are some long notes, the player should hold the key down from the beginning and leave from the end, the system will judge one long note as two notes. The notes’ falling speed has some relationship with the the speed of music(BPM, beat per minute). If the player has a good feeling of the music’s beat, his rate will be very high and he will get high scores. Different music has different levels. When the chosen level is very high, the form of the notes will be very strong, and the player will “die” in the game soon if he has not enough skill.

When you beat a note, you may get a “COOL” or a “GOOD”, but if you miss one, you’ll get a “MISS”. every “COOL” will give you 200 scores, and every “GOOD” will give 100. The game also have JAMs and COMBO. When you get a “COOL”, you’ll also get 1/25 JAM, and every “GOOD” will give you 1/50 JAM. After you get one JAM or more, every JAM will add extra 10 scores to every “COOL” and 5 to every “GOOD”, so JAMs is very important for getting scores.
If you beat notes incessantly, you will get COMBO. 2 notes will be 2 COMBO, 3 notes will be 3 COMBO, and so on. But, if you miss one note, the COMBO will back to zero, and all the JAMs you have will be lost.

For example, you get 45 “COOL”s, 65 “GOOD”s, then 1 “MISS”, then 38 “COOL”s, the scores will be 200*25+210*20+105*10+110*50+115*5+200*25+210*13=24055.

Now, Dreamwind will play this game in another style. He wants to get s scores in a game that have n notes (and of course he can get more scores), and let the maximum number of COMBO as small as possible. However, Dreamwind knows he can get at most c “COOL”s during this game, but he can control himself freely to get “GOOD”s and “MISS”s. Can you help him to find out the smallest MAX COMBO he can get?

输入:

There will be several cases in the input. For each ease, there will be one line with 3 integers n, c, s (1<=n<=50000, 0<=c<=n, 0<=s<=1000000000) as described above.

输出:

There will be several cases in the input. For each ease, there will be one line with 3 integers n, c, s (1<=n<=50000, 0<=c<=n, 0<=s<=1000000000) as described above.

样例输入:

5 5 750
5 5 900
6 3 700
10 0 1002
50 30 7982

样例输出:

2
5
2
impossible
37
Hint
HINT first case: COOL+COOL+MISS+COOL+COOL, there will be 800 scores and MAX COMBO will be 2. second case: 5 “COOL”s, there will be 1000 scores and MAX COMBO will be 5. third case: one possible order is COOL+GOOD+MISS+COOL+MISS+COOL, there will be 700 scores and MAX COMBO will be 2. forth case: he can only get at most 1000 scores, so it is impossible. fifth case: 30 “COOL”s + 7 “GOOD”s + MISS + 11 “GOOD”s, there will be 7985 scores and MAX COMBO will be 37.


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。