2014 AIO(Intermediate) 赛题

2014 AIO(Intermediate) 赛题

Pygmy Hippos

Input File: hippoin.txt
Output File: hippoout.txt
Time Limit: 1 second

Your backyard has been overrun by adorably tiny hippos, and they are eating the daisies!

You have a line of N daisies, labelled from 1 to N. There are three hippos standing next to different daisies ...and they are already eating them! If you don't act fast, they will eat all the daisies in your garden.

You have enough plywood to build up to three fences. Each fence will be built between two daisies that are next to each other. Hippos cannot go through fences (or over them, or under them, or around them).

Once you have built your fences, the hippos will roam back and forth along the line of daisies, eating all the daisies they can reach without crossing your fences. What is the greatest number of daisies you can save?

Input

Your program should read from the file hippoin.txt.

• The first line of input will contain one integer N: the number of daisies.
• The next three lines will each contain an integer describing which daisy one hippo is currently eating. These will be in increasing order. No two hippos start at the same daisy.

Output

Your program should write to the file hippoout.txt. Your output file should contain one line with one integer: the greatest number of daisies you can save.

Corey's Party

Input File: partyin.txt
Output File: partyout.txt
Time Limit: 1 second

Your friend Corey wants to organise a party and invite a few mates.

In the past, Corey's parties haven't always ended well. Some guests get bored because they don't know anyone, then start causing trouble. Other guests get bored because they already know everyone, then start causing trouble.

Thus, Corey's new party invitation strategy is to invite a set of people to the party such that every guest already knows at least A other guests (not including Corey), and doesn't know at least B other guests. This way, everyone will have at least A friends to chat to and at least B new people to meet.

Corey will give you a list of the M existing friendships between his N friends. You must write a program to output the largest number of friends he can invite to his party satisfying the above constraints.

Input

Your program should read from the file partyin.txt. The first line of input will contain four space-separated integers in this order:

• N: the number of Corey's friends
• M: the number of friendships between Corey's friends
• A: the number of guests that each guest must already know
• B: the number of guests that each guest must not already know

The following M lines of input will each contain two space-separated integers x and y, representing that Corey's friend x and Corey's friend y are already friends with each other. Friends are represented as integers between 1 and N.

Output

Your program should write to the file partyout.txt. Your output file should contain one line with one integer: the maximum number of friends Corey can invite to his party such that every invited guest knows at least A other guests and doesn't know at least B other guests. Note that it may not always be possible to invite a set of guests that satisfies these constraints, in which case you should output 0.

Chimera

Input File: chimin.txt
Output File: chimout.txt
Time Limit: 1 second

Next week is your school's Mad Science Fair, and everyone is hard at work on their mad science projects. For example, Gru is building a rocket big enough to steal the moon, whilst Elsa is tinkering with her freeze ray. For your project, you are breeding a chimera.

A chimera is a monster that is part lion, part snake, and part goat. Your plan is to take the DNA sequences of each of the three creatures and combine them into a new DNA sequence for the chimera. A DNA sequence is a string of N letters, each one of A, T, C or G.

The list above shows an example of three DNA sequences of length 7 representing lion, snake and goat DNA. The bottom DNA sequence is one possible sequence of chimera's DNA. Letters in bold in the top three lines are the same as the letter in the chimera's DNA at the same position.

The lionishness of your chimera is defined as the number of positions in which the lion DNA and the chimera DNA have the same letter. In the example above, the lionishness of your chimera is 6, as they match in all but the first position. The snakiness and goatism of your chimera are defined similarly. In the example above, the snakiness and goatism of your chimera are both 5.

The task before you is to construct the chimera's DNA sequence. You will be given the DNA sequences for lions, snakes and goats. The mark for your project will be whichever is lowest: the lionishness, snakiness or goatism of your chimera. You must determine the highest mark you can possibly achieve.

Input

Your program should read from the file chimin.txt.

• The first line of input will contain one integer N: the length of each DNA sequence.
• The next three lines will represent lion, snake and goat DNA respectively. Each of these will contain a sequence of N letters, each one of A, T, C, or G.

Output

Your program should write to the file chimout.txt. Your output file should contain one line with one integer: the highest possible mark you can achieve. (Remember, your mark will be whichever is lowest: the lionishness, snakiness or goatism of your chimera.)