COCI 2010/2011 2nd round, November 13rd 2010
There is a snail on the ground. It wants to climb to the top of a wooden pole with the height of V meters, measuring from the ground level. In one day it can climb A meters upwards, however during each night it sleeps, sliding B meters back down. Determine the number of days it needs to climb to the top.
INPUT
The first and only line of input contains three integers parated by a single space: A, B, and V
(1 ≤ B < A ≤ V ≤ 1 000 000 000), with meanings described above.
OUTPUT
The first and only line of output must contain the number of days that the snail needs to reach the top.
SAMPLE TESTS
Little Mirko wasn‟t paying attention in math class, so the teacher has decided to give him a tedious assignment to solve during the weekend.
The teacher has given him a text consisting of N lines, containing only digits and lower ca letters of the English alphabet. Mirko has to find all numbers in the text and print them out in a nondecreasi
ng quence. He also has to omit any leading zeros that the numbers may have in the text.
The numbers can be uniquely determined by scanning through the text and always taking the largest possible number, i.e. delimited only by letters or line beginnings/ends. For example, the solution of 01a2b3456cde478 is 1, 2, 478, 3456.
Since Mirko is as slow as the snail from the previous task, he has asked you to write him a program to quickly solve his assignment, so that he can go play with Slavko as soon as possible.
INPUT
The first line of input contains the integer N (1 ≤ N≤ 100), the number of lines of the text.
The next N lines contain the text, consisting exclusively of lowerca English letters and decimal digits. Each line of the text is at most 100 characters long.
OUTPUT
The output must contain M lines, where M is the number of numbers found in the provided text. Each line must contain a single number from the text. The numbers must be arranged in a nondecreasing quence.
Note: The test data will ensure that M will never exceed 500.
SAMPLE TESTS
Having solved the tedious assignment, Mirko decided to play a game with his good friend Slavko.
They have written a quence of N letters on a piece of paper. Each one of them is trying to put together a word using letters from the quence. They alternate taking turns consisting of removing
a single letter from the quence and appending it to the end of their word. Mirko has the first turn. The game ends when no letters are remaining in the quence.
We define a word to be more beautiful than another word if it comes first alphabetically. The player who has the more beautiful word at the end of the game wins. If both players have equal words, they both lo.
Mirko is a much better player than Slavko, so he has decided to make it easier for Slavko by always lecting the rightmost remaining letter in the quence. Knowing this, Slavko wants to find out if it is possible for him to win and which is the most beautiful word he can end the game with.
INPUT
The first line of input contains an even positive integer N (2 ≤ N≤ 100 000).
The cond line of input contains N characters, the starting letter quence. All characters are lower ca letters from the English alphabet.
OUTPUT
The first line of output must contain “DA” if it is possible for Slavko to win, and “NE” o therwi. The cond line of output must contain the most beautiful word that Slavko can have at the end of the game.
SCORING
In test cas worth 50% of total points the number N will not exceed 1000.
SAMPLE TESTS
Mirko has a home library consisting of N books arranged one on top of the other in a narrow cabinet. Since being well trained in the crets of alphabet in the previous task, he now wishes to arrange the
books alphabetically, so that the book who title comes first alphabetically ends up on top, and the alphabetically last one at the bottom of the pile.
Mirko can easily pull a book out of the cabinet, but it is difficult to push it back into the pile, so the book can only be returned to the top of the pile. Thus, the only available method of sorting the books is repeatedly pulling a book out of the pile and placing it on top of the pile.
The books are labelled with integers from 1 to N, in alphabetical order. Therefore, Mirko wants them to be ordered as (1, 2, ..., N), counting from the top. For example, if N = 3 and the starting order is (3, 2, 1), two moves are sufficient. First, he pulls out the book number 2 and places it on top, so the pile becomes (2, 3, 1). After that, he does the same with book number 1, thus the pile becomes (1, 2, 3). Help Mirko by calculating the minimum number of moves needed to sort a given starting order.
INPUT
The first line of input contains the integer N (N≤ 300 000).
Each of the next N lines contains a single positive integer. The N integers reprent the order of Mirko‟s books from top to bottom of the cabinet. Each of the integers 1, 2, ..., N appears exactly once.
OUTPUT
The first and only line of output must contain the required minimum number of moves.
SAMPLE TESTS
COCI 2010/2011 Task LUNAPARK 2nd round, November 13rd 2010 Author: Stjepan Glavina Mirko has grown tired of all the books, so he decided to go to the amument park with his friends, despite not liking roller coasters. While his friends are having the time of their lives riding the coasters, Mirko is sitting on a bench, waiting and thinking about the possible paths of the coasters.
The amument park‟s area can be reprented as a table of R rows by C columns. A roller coaster has to start from the upper left corner and end at the lower right corner of the table. Each cell can be visited at most once, but not all cells need to be visited. It can continue its path from the current cell to the adjacent one above, below, to the left, or to the right of it.
Each cell has a positive integer value associated with it, specifying how amusing that cell is to visitors. The total amument value of the coaster is the sum of amument values of all cells that the coaster visits. Help Mirko determine any one of the most amusing coasters (ones with the maximum sum).
INPUT
The first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the dimensions of the table. Each of the next R lines contains C positive integers smaller than 1000, specifying the amument values of the respective table cells.
OUTPUT
The first and only line of output must contain a quence of letters with no blanks. The letters specify
the quence of directions that the coaster follows, starting from the upper left and ending at the lower right corner. The directions up, right, down, left are marked by letters …U‟, …R‟, …D‟, …L‟, respectively. Note:The solution isn‟t guaranteed to be unique.
SCORING
Test cas worth 70% of total points the numbers R and C will not exceed 30.
SAMPLE TESTS
