2014 AIO(Senior) 赛题

2014 AIO(Senior) 赛题

Giant Hippos

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

Your backyard has been overrun by preposterously large hippos, and they are eating the tulips!

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

You have enough plywood to build up to F fences. Each fence will be built between two tulips 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 tulips, eating all the tulips they can reach without crossing your fences. What is the greatest number of tulips you can save?

Input

Your program should read from the file hippoin.txt.

• The first line of input will contain three space-separated integers N, H and F: the number of tulips, hippos, and fences you can build respectively.
• The next H lines will each contain an integer describing which tulip one hippo is eating. These will be in increasing order. No two hippos start at the same tulip.

Output

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

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.)

Wormhole

Input File: wormin.txt
Output File: wormout.txt
Time Limit: 1 second

You are the lead programmer of Wormhole, a widely anticipated computer game. The premise of Wormhole is rather thrilling: test subject Chaz is trapped in a rectangular grid of orange and blue chambers each containing one cupcake. Chaz chooses a chamber to start in, and then needs to collect all the cupcakes by visiting every chamber at least once. If this is possible the level is considered solvable.

The chambers are walled off from each other by thick glass, such that Chaz can only see chambers which are directly north, south, east or west of his current position. Conveniently Chaz has a 'wormhole gun', which he can use to shoot through the glass into any chamber he can see and so be instantly teleported there. However, a wormhole can only be created between two chambers of different colours. This means that if Chaz is standing in a blue chamber, he can only move to an orange chamber, and vice versa.

That is, Chaz can teleport to another chamber if:

• It is of a different colour to his current chamber.
• It is directly north, south, east or west (i.e. in the same row or column) of his current chamber.

You have been stuck in a meeting for hours now where the designers are interested in how modifications to the chamber colours affect a level. Each modification involves changing the colour of one chamber. After each change they make, the designers want to know how many more modifications are needed to make the level solvable - that is, the smallest number of chambers that need to have their colour changed so that Chaz can reach every chamber from a starting chamber of his choosing.

As working everything out by hand gets more and more tedious, you escape from the meeting and whip out your trusty laptop to write a computer program that will answer the designers' questions after each modification.

Input

Your program should read from the file wormin.txt.

• The first line of input contains three space-separated integers, R, C, and Q. There will be R rows and C columns in the grid, and Q modifications made by the designers.
• The next R lines each contain C characters, representing the initial design of the game. An `O' represents an orange chamber, while a `B' represents a blue chamber.
• The following Q lines each contain two integers r_i and c_i. This represents a modification to the grid that changes the colour of the chamber in row r_i and column c_i. Rows are labelled from 1 to R (from top to bottom) and columns are labelled from 1 to C (from left to right).

Output

Your program should write to the file wormout.txt. The output should contain Q+1 lines. The first line should contain the smallest number of modifications required to make the level solvable. The next Q lines should correspond to the Q modifications in input. After each modification has been made (including all previous modifications), your program should write one line containing the smallest number of modifications required to make the level solvable (or 0 if it is already solvable).