ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Dance Revolution

Time limit: 1.0 second
Memory limit: 64 MB
Dance Dance Revolution, or DDR (known as Dancing Stage in Europe) is a music video games series produced by Konami. As of 2005, over 90 official versions have been produced, including those for home video game consoles. The game is played on a dance pad with four arrow panels: left, down, up, and right. These panels are pressed using the player's feet, in response to arrows that appear on the screen in front of the player. The arrows are synchronized to the general rhythm or beat of a chosen song, and success is dependent on the player's ability to time and position his or her steps accordingly.
From Wikipedia, the Free Encyclopedia.
DDR machines are extremely popular in Japan. Gradually they have won hearts and feet of admirers all over the world and have already appeared in Ekaterinburg. Especially for severe Ural conditions, the project Dance Dance Revolution Ural Mix (or, simply, DDRUMix) based on DDR 5th Mix, which is widespread only in Japan, has been developed.
DDRUMix operates similarly to other Dance Dance Revolution games: a player must move his or her feet to the beat of a song following instructions on the screen. During a game, arrows scroll upwards from the bottom of the screen. When the scrolling arrows reach the top of the screen, the player must step on the corresponding arrow panels on the dance platform. The actions of the player are estimated by the machine and, after the song, the player is taken to the results screen, which shows the score and bonus points.
Since DDRUMix is a joint project, the Japanese entrusted leading Ural programmers with developing the software for the machine. Your task will be to create the scoring system. For that, you have to know the scoring algorithm.
Each song in DDRUMix has one of the 3 difficulty levels: Easy, Medium, or Hard depending on its rhythm (Easy for 1 beat per second, Medium for 2 beats per second, and Hard for 4 beats per second). A period between two consecutive beats is called a beat-period, for example, a beat-period for the Medium level is 500 milliseconds. Beat-periods during which the player should step on an arrow panel are called step-periods, and there may also be empty beat-periods during which the player isn't expected to make any steps. Each beat-period of a song is assigned a letter: N if it is empty, and U, D, L, or R if the player should step on the “Up”, “Down”, “Left”, or “Right” arrow panel during this beat-period.
The actions of the player during an empty period are not estimated.
The actions of the player during a step-period are estimated as follows:
  1. All non-first steps are not estimated.
  2. If the player has not pressed any panel during the period, then he or she gets “BOO”.
  3. If the first step was wrong, then the player gets “MISS”.
  4. If the first step was correct (i.e., the player has pressed the arrow panel corresponding to this beat-period), then the estimate depends on the time between the start of the step-period and the first step: “PERFECT” if it is less than 40% of the length of the period, “GREAT” if it is no less than 40% but less than 70%, and “GOOD” if it is no less than 70%.
The total score for a game is the sum of the Stage Score, Combo Bonus, and Dance Level Bonus
How to calculate the Stage Score:
Let B = 106 * Diff, where Diff = 1 for the Easy level, 2 for the Medium level, and 3 for the Hard level.
Denote by N the total number of step-periods and let S = (N*(N+1))/2.
Let n be the number of the current step-period (from 1 to N), then the number of points for this step-period
StepScore = p * n * (B div S),
where B div S is the integer part of B/S, and the score multiplier p depends on the estimate of the player's actions in this step-period: p = 10 for “PERFECT”, p = 5 for “GREAT”, and p = 0 in other cases.
The Stage Score is the sum of Step Scores for all step-periods of the song.
How to calculate the Combo Bonus:
A Combo is a series of consecutive step-periods consisting of “PERFECT”, “GREAT”, or “GOOD” step-periods only (of course, there can be empty beat-periods inside a combo, but they are not taken into account and do not increase the length of the combo).
For each step-period in a combo, the player scores q * c combo points, where the step multiplier q = 55 for “PERFECT”, q = 33 for “GREAT”, and q = 0 in other cases, and c is the number of the step-period in the current combo.
The Combo Bonus is the sum of combo points for all step-periods in all combos.
How to calculate the Dance Level Bonus:
The player begins a game with zero Dance Points. Each step-period can add or subtract Dance Points: a “PERFECT” step-period adds 2 Dance Points, a “GREAT” step-period adds 1 Dance Point, a “GOOD” step-period does nothing, a “BOO” step-period subtracts 4 Dance Points, and a “MISS” step-period subtracts 5 Dance Points.
The player is given one of the following Dance Level Bonuses:
AAA = 10,000,000 (all step-periods are “PERFECT”);
AA = 1,000,000 (all step-periods are “PERFECT” or “GREAT”);
A = 100,000 (the player's Dance Points are at least 80% of maximum Dance Points);
B = 10,000 (at least 64% of maximum Dance Points);
C = 1,000 (at least 50% of maximum Dance Points);
D = 100 (less than 50% of maximum Dance Points);
E = 0 (the player's Dance Points went below zero during the game).
Given information about one game, you must calculate the total score and output the game statistics.


The first line contains the duration of the song in the format m:ss (each song is at least 10 seconds and is shorter than 10 minutes) and the difficulty level of the song: Easy, Medium, or Hard. The second line describes beat-periods. There is at least one step-period in the song. The remaining lines of the input contain the log of the player's actions. Each line corresponds to one pressing of an arrow panel and has the following form:
<time> <action>
where <time> is the time in milliseconds from the start of the song, and <action> denotes the panel pressed: U, D, L, or R. Note that it is impossible for any human to press panels more often that one time in 50 milliseconds.


Output the player's statistics. In the first line output the number of “PERFECT” step-periods, in the second line output the number of “GREAT” step-periods, and so on. The sixth line is a separator consisting of 20 hyphens (-). In the next lines output the Stage Score, the Combo Bonus, the Dance Level Bonus, and the total score. For details, see the sample.


0:30 Easy
5201 L
8475 R
8735 L
10000 U
13200 U
17284 D
18355 D
19124 D
22222 U
27543 R
29923 U
Perfect: 7
Great: 2
Good: 1
Boo: 0
Miss: 0
Stage Score: 7181495
Combo Bonus: 2233
Dance Level Bonus: 100000
Total Score: 7283728
Problem Author: Denis Musin
Problem Source: The 11th Urals Collegiate Programing Championship, Ekaterinburg, April 21, 2007
To submit the solution for this problem go to the Problem set: 1543. Dance Revolution