2017 AIO(Senior) 赛题

2017 AIO(Senior) 赛题

Concealed Coconut

Input File: cocoin.txt
Output File: cocoout.txt
Time Limit: 1 second
Memory Limit: 1 GB

Ishraq and Clement have lost their coconut and need help finding it again!

Ishraq, Clement and the coconut are standing on a 2d-plane. The locations of Ishraq and Clement are given by their x- and y-coordinates, where x and y are whole numbers.

Both Ishraq and Clement think they know how far away from the coconut they are, but in their sadness their memory may be wrong. Given the location of Ishraq and Clement, and their respective distances to the coconut, figure out whether there is at least one location that the coconut could be. Note that the distance from each person to the coconut will also be a whole number.

Input

The first line will contain Ishraq's location, followed by his distance to the coconut; I_x, I_y and I_d respectively. The second line will contain Clement's location, followed by his distance to the coconut; C_x, C_y and C_d respectively.

Output

If there is at least one location that the coconut could be in, your program should output 'yes', otherwise it should output 'no'.

Snake Charmer

Input File: snakein.txt
Output File: snakeout.txt
Time Limit: 1 second
Memory Limit: 1 GB

You are a snake charmer performing for a travelling circus troupe. For your next act, you will show off your skills by charming your snake to move to a place selected by an audience member. To perform this act, you have created a grid for your snake to move around in. Initially your snake starts off in a square in the middle of this grid facing north, and you will ask the audience for a goal square for your snake to reach. However, your snake is very peculiar: it only likes to move by zigzagging around. More specifically you can only make your snake move in two ways:

• An L move: make it turn left and then move forward by one square.
• An R move: make it turn right and then move forward by one square.

For instance, consider the following grid in a coordinate system.

Your snake will always start off at the square (0,0). In the above grid, the flag square at (-1,2) represents the goal square selected by the audience, and the dots show the path taken. The snake is initially facing north, so the sequence of moves taken by it are:

1. An R move: it turns right to face east and moves forward one square to the square (1,0).
2. An L move: it turns left to face north and moves forward one square to the square (1,1).
3. An L move: it turns left to face west and moves forward one square to the square (0,1).
4. An R move: it turns right to face north and moves forward one square to the square (0,2).
5. An L move: it turns left to face west and moves forward one square to square (-1,2), which is the goal square where it stops.

Now, you realise that the longer it takes for your snake to get to the goal square, the less interested your audience will become. Can you find the shortest path for you to charm your snake to the goal square? If there are multiple shortest paths, you only need to find one of them.

Input

The input file consists of one line with two integers x and y representing the (x,y) coordinates of the goal square.

Output

Your output file should consist of a single line of Ls and Rs, representing a sequence of moves that will charm your snake from the starting point to the goal square.

Chimera II

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

You've just graduated from high school and are ready to start your very own mad science lab. To prove your genius to the world you plan to breed a lion-goat hybrid.

All animals in existence are fundamentally described by their DNA sequence, which is a string of N upper case letters. You've managed to obtain the DNA sequences of a lion and of a goat. To bring your new creature to life, you must produce a specific DNA sequence, called the hybrid sequence.

New DNA sequences can be produced by splicing. This involves picking two DNA sequences from your lab (call these sequences S and T) and an integer x (0 < x < N), called the splicing point. Your state-of-the-art DNA photocopier will then produce a new DNA sequence which consists of the first x characters of S, followed by the last N-x characters of T. This new sequence is then stored in your lab and can be used for future splicing.

For example, say you pick the DNA sequences GOLEM and MOOSE, and take x=2. The splicing will take GO from the start of GOLEM and OSE from the end of MOOSE, and combine these to get the new DNA sequence GOOSE.

There's been a wave of blackouts recently, so to conserve power you want to minimise use of the DNA photocopier. Determine if it is possible to create the hybrid sequence, and if so the minimum number of splices required.

Input

• • The first line of input contains the integer N, the length of DNA sequences.
  • The next two lines each contain a string of length N, the two DNA sequences you already have in your laboratory.

• The fourth line contains a string of length N, the required hybrid sequence.

Each string in the input consists only of upper case letters.

It is guaranteed that all three strings in the input will be different.

Output

If it is impossible to produce the hybrid sequence, your program should output PLAN FOILED. Otherwise, your problem should output two lines. On the first line you should output SUCCESS, and on the second line you should output a single integer: the minimum number of times you must splice to produce the required sequence.

Lollipops, Sweets and Chocolates

Input File: lscin.txt
Output File: lscout.txt
Time Limit: 1 second
Memory Limit: 1 GB

The little boys and little girls of Sydney are excited about the opening of LOLLIPOPS, SWEETS AND CHOCOLATES (LSC), a world renowned candy shop! There are going to be N new branches of LSC opening along the Australian Ice-cream and Oreo Crescent (AIOC). There are L positions on the crescent, each of which can be represented by a number between 1 and L. To promote this, the organisers prepared personalised pamphlets so that for each position on the crescent, the pamphlet lists the N branches in order of how close each shop is to that position. If there are ties, the shops could be listed in any order.

For example, in the diagram above the pamphlet at position 9 could read:

As you were daydreaming about the mouthwatering chlorosulfonic acid sorbet you had last time, you accidentally stepped on a LSC pamphlet! Unfortunately, the stain from your shoe covered up all the distances to the LSCs. In order to satisfy your curiosity, you wish to find a possible position where this pamphlet could have originally been handed out. However LSC is not renowned for their pamphlets' accuracy, so it could be the case that there are no possible positions from where the flyer could have originated.

Input

The first line of input will contain two integers N and L: the number of new LSCs and the number of positions on the crescent respectively.

The next line of input will contain N integers, the ith of which describes the position of the ith shop. For each shop, you are guaranteed that the position of that shop will be an even integer.

The next line of input will contain a permutation of the integers 1 to N: a list of these shops sorted in increasing order based on the distance from the position at which the pamphlet was handed out.

Output

Your program must output a single integer: a possible position where the pamphlet could have been handed out, or -1 if you think this pamphlet is incorrect. If there are multiple correct answers, output any of them. Note that a position is only possible if it lies on the crescent with a position between 1 and L inclusive.