University of Toronto ACM-ICPC Tryouts 2012
A: The Super Mario Blues
Because you somehow missed out on having a proper childhood, your friends are now forcing you to play a certain game for the first time - Super Mario Brothers. However, as a result of said missing-out, you find that you hate it. Who would want to go around as an Italian plumber, eating mushrooms and jumping on turtles, anyway? Needless to say, you want to get it over with as soon as possible.
From your understanding, there are 8 worlds (numbered from 1 to 8), each with 4 levels (numbered from 1 to 4). The i-th level in the j-th world is referred to by the string "j-i" (without the quotes). A player starts in level 1-1, with the objective of eventually completing level 8-4. In general, after completing each level, the player progress to the next level in the world (or, if it was the last level in the world, then to the first level in the following world). For example, the next level after 3-2 is 3-3, while the next one after 5-4 is 6-1.
However, there are also three hidden warp zones in the game, which allow the player to skip directly to the start of a later world after completing a certain level in a specific way. In particular, there is a warp zone from level 1-2 to worlds 2, 3, and 4, another from level 4-2 to worlds 6, 7, and 8, and a final one from level 4-2 to world 5. Because you're in a hurry, you'll be taking advantage of these whenever possible - this means that, after playing level 1-2, you'll skip to level 4-1, and after level 4-2, you'll skip to level 8-1.
You and your friends have T (1 ≤ T ≤ 50) get-togethers. In each one, your friends play for a while and then hand you the controller, in addition to pointing a gun to your head in case you try to run away. Given which level you initially find yourself in, you'd like to determine how many levels you'll have to complete to get this thing over with.
Line 1: 1 integer, T
For each get-together:
Line 1: 3 characters, describing your starting level
For each get-together:
Line 1: 1 integer, the number of levels you must pass to complete the game
3 6-1 8-3 1-1
12 2 8
Explanation of Sample
In the first scenario, you have no choice but to complete every level in worlds 6, 7, and 8, for a total of 3 × 4 = 12.
In the second scenario, you're already on the second-last level, so you only need to pass 8-3 and 8-4.
In the first scenario, you should play levels 1-1 and 1-2, warp to world 4, play 4-1 and 4-2, warp to world 8, and finally pass all of the stages there to finish the game. This amounts to 8 levels.
Point Value: 5
Time Limit: 5.00s
Memory Limit: 64M
Added: Oct 02, 2012
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3