2015 AIO(Intermediate) 赛题

2015 AIO(Intermediate) 赛题

Snap Dragons II

Input File: snapin.txt
Output File: snapout.txt
Time Limit: 1 second

Have you ever heard of Melodramia, my friend? It is a land of magic forests and mysterious swamps, of sprinting heroines and dashing heroes. And it is home to two dragons, Rose and Scarlet, who, despite their competitive streak, are the best of friends.

Rose and Scarlet love playing snap tag, a game for two players on an grid. The game goes as follows:

• The two dragons start on different squares.
• It's Rose's turn first. On her turn she must move to an adjacent square (i.e. she must make one step left, right, up, or down).
• It's Scarlet's turn next. On her turn she must move to an adjacent square.
• The two dragons continue alternating turns...
• ...until one dragon lands on the same square as another. When this happens, the dragon who moved last shouts `Snap tag!' and wins the game.

Rose and Scarlet are both snap tag experts and always find a winning strategy if one exists. If it is not possible for either player to gain the upper hand, then the game goes on forever.

In this task, you are given the size of the grid and the starting locations of both dragons. You must write a program to determine how the game ends: Does Rose win? Does Scarlet win? Does the game go on forever?

Input

The input file will contain six space separated integers on a single line, in the format: R C r_ROSE c_ROSE r_SCARLET c_SCARLET where:

• R and C are the number of rows and columns in the grid, respectively;
• r_ROSE and c_ROSE are the row and column of Rose's starting square (rows are numbered 1 to R from top to bottom; columns are numbered 1 to C from left to right); and
• r_SCARLET and c_SCARLET are the row and column of Rose's starting square.

Output

Output should consist of a single upper-case word with no punctuation.

• If Rose can guarantee herself a win, output ROSE.
• If Scarlet can guarantee herself a win, output SCARLET.
• If neither player can guarantee a win, output DRAW.

Wet Chairs

Input File: chairsin.txt
Output File: chairsout.txt
Time Limit: 1 second

Congratulations, contest winner! As a prize for winning the Australian Image Opening Competition you and all your friends are invited to a private concert with the country's finest musical acts.

As luck would have it, it has rained on the morning of the concert. To make matters worse, the staff did a very rushed job drying the seats! Now it is up to you to decide how to seat everyone.

The seats are arranged in a single long line in front of the stage. In particular there are chairs in the line, and each seat is either wet or dry.

However, all is not lost. Out of the N friends you are bringing to the concert K of them are happy to sit on a wet chair. The other N-K of your friends insist on sitting on a dry chair.

Since this concert is best enjoyed with friends, you would also like your group to be seated as close together as possible so that the distance between the leftmost person and rightmost person is as small as possible. Output the smallest distance possible between the leftmost and rightmost friend at the concert.

Your task is to write a program that outputs this smallest possible distance.

Input

The input file will have two lines. The first line of input contains 3 numbers: C N K.

• C is the total number of chairs.
• N is the number of friends to whom you must assign seats.
• K is the number of your friends who are able to sit on either a wet chair or a dry chair.

The second line will have C letters on it, each of which will be either d or w. These letters represent the line of chairs at the concert, giving the order of dry and wet chairs. In particular d is a dry chair, w is a wet chair.

Output

Output should be a single integer, the smallest distance possible between the leftmost and rightmost friend at the concert with no more than K of them sitting on wet chairs.

Ruckus League

Input File: ruckusin.txt
Output File: ruckusout.txt
Time Limit: 1 second

It's that time of year again! The Annual Ruckus World Championships is fast approaching and you are absolutely determined to see Australia victorious. As the name implies, the goal of the competition is to be as loud and obnoxious as possible. Players compete in teams of at least M people (there is no upper limit on team sizes). To make sure teams don't mix, team members must hold hands with each other.

Of course, you've found that there is nothing more obnoxious than spoilt kindergarteners, so you've rounded up N of the loudest ones you could find. You were hoping to send as many teams as possible, but some of the children have already started holding hands with their friends. Being as stubborn as they are, you are finding it rather difficult to convince them to let go of each other, or even to hold hands with anyone else.

Now for any other person, the story would end here; you'd have to send whatever teams their 'friendships' have forged. However, being the social engineering master you are, you've brought K lollipops to use to bribe the children. You can pass a lollipop to the hand of a child, which will make them let go of the hand they are holding.

Using your K lollipops, what is the largest number of teams with at least M children you can form?

Input

The first line of the input file will contain four space separated integers on a single line, in the format: N L K M.

• N is the number of children you have gathered.
• L is the number of pairs of hands that are already joined together.
• K is the number of lollipops you have.
• M is the minimum size of a team. All teams must have at least M people.

The following L lines will each contain two integers, in the format: l_i r_i. This indicates that the l_ith child's left hand is holding the r_ith child's right hand. The children are numbered from 1 to N. No one can hold their own hands.

Output

Output should consist of a single integer: the maximum number of teams with at least M children you can form.