2015 AIO(Senior) 赛题

2015 AIO(Senior) 赛题

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: li ri. This indicates that the lith child’s left hand is holding the rith 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.

 

 

Snap Dragons III: Binary Snap

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 forbidden forests and boundless swamps, of sprinting heroes and dashing heroines. 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 Binary Snap, a game for two players. The game is played with a deck of cards, each with a numeric label from 1 to N. There are two cards with each possible label, making 2N cards in total. The game goes as follows:

  • Rose shuffles the cards and places them face down in front of Scarlet.
  • Scarlet then chooses either the top card, or the second-from-top card from the deck and reveals it.
  • Scarlet continues to do this until the deck is empty. If at any point the card she reveals has the same label as the previous card she revealed, the cards are a Dragon Pair, and whichever dragon shouts `Snap!’ first gains a point.

After many millenia of playing, the dragons noticed that having more possible Dragon Pairs would often lead to a more exciting game. It is for this reason they have summoned you, the village computermancer, to write a program that reads in the order of cards in the shuffled deck and outputs the maximum number of Dragon Pairs that the dragons can find.

Input

The first line of input will contain a single integer, N. The following 2N lines will each contain an integer, vi (where 1 ≤ vi ≤ N), representing the label of the ith card from the top of the shuffled deck.

Output

Output should consist of a single integer: the maximum number of Dragon Pairs Scarlet can deal in a game of Binary Snap with the deck in the given order.