2019 AIO 赛题

2019 AIO 赛题

Vases

Input File: vasesin.txt
Output File: vasesout.txt
Time Limit: 1 second
Memory Limit: 1 GB

You have bought N identical flowers to arrange into three vases. As an expert in interior design, there are three important rules you must follow:

1. Every flower must go into one of the three vases, since throwing flowers away is wasteful.
2. Each vase must contain at least one flower, since an empty vase looks very odd.
3. Each vase must contain a different number of flowers, so all the vases look different.

Your task is to determine a possible way to arrange the flowers. Note that there may be multiple possible solutions, or none at all.

Input

The only line of input will contain a single integer: the number of flowers N.

Output

Your program should output three space-separated integers, describing how many flowers to put into each vase. If there are multiple possible ways to arrange the flowers, any will do.

If it is impossible to place flowers according to the rules, print 0 0 0 instead.

RPS

Input File: rpsin.txt
Output File: rpsout.txt
Time Limit: 1 second
Memory Limit: 1 GB

‰C Rock. Paper. Scissors. The rules are simple. The game is contested by two people over N rounds. During each round, you and your opponent simultaneously throw either Rock, Paper or Scissors. Rock beats Scissors, Scissors beats Paper, and Paper beats Rock. If your throw beats your opponent’s, you gain one point. Conversely, if their throw beats yours, you lose one point.

Your opponent is very predictable. You know that they will throw Rock in the first R_a rounds, throw Paper in the next P_a rounds, then finally throw Scissors in the last S_a rounds, where R_a + P_a + S_a = N.

You will throw Rock in R_b rounds, Paper in P_b rounds, and Scissors in S_b rounds, where R_b + P_b + S_b = N. However, as you are an experienced player, you may throw these in any order you like.

At the beginning of the game, you start with 0 points. What is the maximum number of points you can finish with?

Input

• The first line of input contains a single integer N, the number of rounds.
• The second line of input contains three space-separated integers: R_a, P_a and S_a.
• The third line of input contains three space-separated integers: R_b, P_b and S_b.

Output

Your program should output a single integer: the maximum number of points you could score after all N rounds have been played. Note that this number may be positive, negative, or zero.

Hiring Monks

Input File: hirein.txt
Output File: hireout.txt
Time Limit: 1 second
Memory Limit: 1 GB

High up in the peaks of Kosciuszko National Park, an elite sect of monks are deciding how to assign jobs to the new monks.

They have hired N new monks, numbered from 1 to N, each possessing a possibly different skill level. The monk i has a skill level of x_i.

There are S student jobs available, numbered from 1 to S, created for monks to learn from their masters. As such, there is a limit on how much skill a monk can have for this job. Student job j is available to monks with a skill level at most s_j.

There are M master jobs available, numbered from 1 to M, created for monks to teach their students. As such, there is a minimum skill level a monk must have for this job. Master job k is available to monks with a skill level at least m_k.

Each monk can be assigned at most one job, and each job can be assigned to at most one monk. What is the largest number of monks you can assign to jobs?

Input

• The first line contains the integer N, the number of monks. Then, N lines follow. The ith of these lines contains the integer x_i, the skill level of monk i.
• The next line contains the integer S, the number of student jobs (which could be zero). Then, S lines follow. The jth of these lines contains the integer s_j.
• The next line contains the integer M, the number of master jobs (which could be zero). Then, M lines follow. The kth of these lines contains the integer m_k.

Output

Your program should output a single integer: the maximum number of monks who can be assigned to jobs.

Medusa's Snakes

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

After the success of your latest research project in mythical DNA, you have gained the attention of a most diabolical creature: Medusa.

Medusa has snakes instead of hair. Each of her snakes' DNA is represented by an uppercase string of letters. Each letter is one of S, N, A, K or E.

Your extensive research shows that a snake's venom level depends on its DNA. A snake has venom level x if its DNA:

• has exactly 5x letters
• begins with x copies of the letter S
• then has x copies of the letter N
• then has x copies of the letter A
• then has x copies of the letter K
• ends with x copies of the letter E.

For example, a snake with venom level 1 has DNA SNAKE, while a snake that has venom level 3 has DNA SSSNNNAAAKKKEEE. If a snake's DNA does not fit the format described above, it has a venom level of 0.

Medusa would like your help making her snakes venomous, by deleting zero or more letters from their DNA. Given a snake's DNA, can you work out the maximum venom level this snake could have?

Input

The first line contains the integer N: the number of letters in the snake's DNA. The second line contains a string of N uppercase letters, representing the snake's DNA. Each letter is one of S, N, A, K or E.

Output

Your program should output a single integer: the maximum venom level the snake could have, after you delete some (possibly none) of the letters from its DNA.

Evading Capture

Input File: evadingin.txt
Output File: evadingout.txt
Time Limit: 1 second
Memory Limit: 1 GB

It is the year 2077, when androids live among us, cars no longer have wheels and humans are born on blockchain. You are preparing to pull off the greatest heist of all time: stealing the Bitcoin. Stealing the Bitcoin is the easy part; evading capture is much harder.

The world consists of N cities, numbered from 1 to N. E pairs of these cities are adjacent to each other. In a single hop, you can travel from the city you are currently in to any adjacent city.

Your heist will begin in city X where the Bitcoin is located. After stealing the Bitcoin, you will need to make exactly K hops to be safe from capture (too few and the Chaser will catch you, too many and the All-Seeing I will know where you are).

You aren't yet sure which hops you will make on the day of the heist, so you have decided to work out the number of different cities you could finish in after making exactly K hops. You whip out your trusty laptop and begin coding.

Input

The first line contains the integers N, E, X and K, which are the number of cities, the number of adjacent pairs of cities, the starting city and the number of hops you must make, respectively.

Then E lines follow, describing the adjacent pairs of cities. The ith of these lines contains a_i and b_i, indicating that city a_i is adjacent to city b_i.

Output

Your program should output a single integer, the number of different cities you could finish in after making exactly K hops. You are guaranteed that at least one such sequence of hops exists.

Lollipops, Sweets and Chocolates II

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

The grand opening of Lollipops, Sweets and Chocolates (LSC) was a great success! Since then a total of N LSC stores have opened along Australian Ice-cream and Oreo Crescent (AIOC), the most candilicious street in Sydney.

The street is divided into L blocks, spaced 1 metre apart. The blocks are labelled with numbers from 1 to L along the street, so that the distance between any two blocks a and b is |a - b| metres.

Each of the N stores occupies a different block. There are also M houses along the street, each occupying a different block. However, houses and stores may occupy the same block!

To keep the little boys and girls of Sydney excited about the stores, LSC has been distributing personalised pamphlets to the houses on the street. There is one pamphlet for each house. The ith pamphlet contains a message of the form:

There are s_i stores within walking distance of your house!

Wondering how far you have to walk to get your hands on another mouthwatering chlorosulfonic acid sorbet, you decide to investigate how far ‘walking distance’ could be. Walking distance means a distance of at most R metres, and you would like to determine a possible value for R. You know that the street is very long, so R cannot be greater than L.

You have collected all M pamphlets, but in your haste you have forgotten which house each pamphlet came from! Given all the numbers on the pamphlets, your task is to determine a possible value of R. LSC is notorious for distributing inaccurate pamphlets, so it is also possible that no such value of R exists.

Input

• The first line of input will contain three integers N, M and L: the number of stores, the number of houses, and the length of the street, respectively.
• The next line of input will contain N integers, describing the positions of the shops. These will be given in increasing order.
• The next line of input will contain M integers, describing the positions of the houses. These will be given in increasing order.
• The final line of input will contain M integers, describing the numbers on the pamphlets. These will be given in non-decreasing order. Note that this may not necessarily be the same order as the houses.

Output

Your program must output a single integer (whole number): a possible value of R, or âˆ’1 if no such value exists. If there are multiple possible answers, output any one of them. Note that the value of R must not be greater than L.