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
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:
- All non-first steps are not estimated.
- If the player has not pressed any panel during the period, then he or she gets “BOO”.
- If the first step was wrong, then the player gets “MISS”.
- 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
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
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:
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.
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