2016 AIO(Senior) 赛题

2016 AIO(Senior) 赛题

Probe

Time Limit: 1 second
Memory Limit: 1 GB
Input File: probein.txt
Output File: probeout.txt

Earth is the only known planet to harbour life. There are many planets out there that have some of the things needed for life. Let me introduce you to one in particular, Kepler-442b.

Discovered early last year, it is the most Earth-like planet we know about. Although a little bigger than Earth, the conditions are almost perfect for life. Almost. It's missing liquid water.

The Australian Institute for Observing the Cosmos has just sent out a massive probe full of water to crash into the planet. The water will spill out on impact to plant the metaphorical seeds of life, but the shock of the impact will also cause a fissure to form elsewhere, which will spill lava.

Scientists have selected a small, empty desert for the probe which can be represented by a grid of squares with R rows and C columns. They happen to know exactly which square the probe will crash in and also the square where the fissure will form.

The square where the probe crashes is instantly covered in water, while the square where the fissure forms is instantly covered in lava. As time passes, the water and lava spread out over the desert in a simple way. Each minute:

• Any empty square that shares a side with a square covered in water will also become covered in water.
• Any empty square that shares a side with a square covered in lava will also become covered in lava.
• Any empty square that shares a side with both a square covered in lava and one covered in water will form into rocky mountains (probably made of obsidian), over which neither water nor lava will flow.

Lava and water never flow outside the desert.

You have been tasked with helping the scientists figure out what the desert will look like after the water and lava finish flowing. You will be asked Q questions, for each of which you must answer whether a given square will be covered in water, lava or mountains.

Input

The first line of input will contain six integers (separated by spaces), R, C, r_p, c_p, r_f and c_f.

• R and C denote the number of rows and columns in the grid respectively. Rows are labelled from 1 to R (from top to bottom) and columns are labelled from 1 to C (from left to right).
• The probe will crash in the square in the r_pth row and c_pth column.
• The fissure will form in a different square in the r_fth row and c_fth column.

The second line will contain a single integer Q, the number of questions that will be asked. Q lines follow, the ith of which contains two integers r_i and c_i.

Output

You should output Q lines. The ith line should contain a single word describing the state of the square in the r_ith row and c_ith column:

• LAVA if the square is covered in lava.
• WATER if the square is covered in water.
• MOUNTAINS if the square is covered in mountains.

Balancing Aeroplanes II

Input File: balancein.txt
Output File: balanceout.txt
Time Limit: 1 second
Memory Limit: 1 GB

The recent release of AIOC (Autonomous Infinitesimal Omnipresent Creature) GO has taken the world by storm, and the postal networks everywhere are overloaded trying to deliver all the plush toys that excited players have ordered, from the common Owtwem to the legendary Tabuz. Unfortunately, the shipping company you work for has run out of modern cargo planes, and many more boxes remain unshipped to their impatient recipients!

The only plane left in the hangar is very old, and will only fly safely if the weight of the boxes stacked inside is distributed symmetrically -- the boxes must be placed in the plane in a line of stacks such that the leftmost stack is equal in weight to the rightmost stack, the second leftmost is equal to the second rightmost, and so on.

As chief Alignment Imposition Officer, the task falls to you to ensure the safety of the flight. The boxes in the warehouse are already arranged into a line of stacks, and all boxes are the same size and weight. Since you never quite figured out how to use that forklift properly, you decide to save time by repeating the only operation you know: picking up one whole stack of boxes, and placing it on top of an adjacent stack. You do this until the line of stacks is symmetrical.

In order to escape the wrath of impatient customers, you decide to speed up this process. You whip out your trusty laptop and begin to write a program to calculate the minimum number of forklift operations that must be performed to achieve a symmetrical arrangement.

Input

The first line of input will contain a single integer S: the number of stacks in the warehouse.

The second line will contain S space-separated integers, the ith integer n_i representing the number of boxes in the ith stack.

Output

Your program must output a single integer: the minimum number of times you will need to pick up a stack of boxes and place it on top of another stack in order to achieve a symmetrical arrangement. Note that it is always possible to achieve such an arrangement by placing all the boxes into a single stack.

Carmen Sanfrancisco II: Bank Robbing

Input File: wherein.txt
Output File: whereout.txt
Time Limit: 1 second
Memory Limit: 1 GB

After her foiled attempt to steal the Eiffel Tower, Carmen Sanfrancisco is back, and this time the villainess plans to `rob' several high-profile banks. (The whole banks! You get it? She's gonna steal actual entire buildings!) Fortunately, the ACME Detective Agency is well aware of this plot and has requested your services as an elite detective to track down Carmen's current whereabouts.

You have obtained a map of all the cities in which Carmen Sanfrancisco could currently be hiding. These cities are arranged in a line along a single highway, and it takes an hour to travel from any city to the city directly east or west of it. You know which cities have a bank Carmen is interested in stealing, and you know that once in a city, Carmen takes practically no time to steal a bank (she is a well-prepared master criminal after all).

When Carmen starts moving, the highway patrols will mobilise to close the roads between every city. You know how many hours it will take for the highway patrol to close the road between any pair of adjacent cities, and so does Carmen. Since Carmen won't compromise on the banks she intends to steal, her starting point must be in a city where it's possible for her to reach all the banks before the roads close. Your task is to determine from how many different cities Carmen could begin her heist.

Input

The first line of input will consist of two integers N and C, separated by a space. The first integer N specifies the number of cities. The second integer C specifies the number of cities with a bank that Carmen wishes to steal.

Each city is assigned a unique number from 1 to N, numbered from west to east.

The next line of input contains C integers, in ascending order. These are the cities with a bank.

The final line of input contains N - 1 integers, the ith of these t_i, representing how many hours it takes to close the road between city i and city i + 1.

Output

Your program must output a single integer: the number of cities from which Carmen Sanfrancisco can begin.