0%

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7150 Accepted: 3865

Description

The cows are thrilled because they’ve just learned about encrypting messages. They think they will be able to use secret messages to plot meetings with cows on other farms.

Cows are not known for their intelligence. Their encryption method is nothing like DES or BlowFish or any of those really good secret coding methods. No, they are using a simple substitution cipher.

The cows have a decryption key and a secret message. Help them decode it. The key looks like this:
yrwhsoujgcxqbativndfezmlpk
Which means that an ‘a’ in the secret message really means ‘y’; a ‘b’ in the secret message really means ‘r’; a ‘c’ decrypts to ‘w’; and so on. Blanks are not encrypted; they are simply kept in place.

Input text is in upper or lower case, both decrypt using the same decryption key, keeping the appropriate case, of course.

阅读全文 »

Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 6740 Accepted: 4180

Description

In your job at Albatross Circus Management (yes, it’s run by a bunch of clowns), you have just finished writing a program whose output is a list of names in nondescending order by length (so that each name is at least as long as the one preceding it). However, your boss does not like the way the output looks, and instead wants the output to appear more symmetric, with the shorter strings at the top and bottom and the longer strings in the middle. His rule is that each pair of names belongs on opposite ends of the list, and the first name in the pair is always in the top part of the list. In the first example set below, Bo and Pat are the first pair, Jean and Kevin the second pair, etc.

阅读全文 »

Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 13776 Accepted: 5453

Description

You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.

Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.

阅读全文 »

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3214 Accepted: 2190

Description

A boolean matrix has the parity property when each row and each column has an even sum, i.e. contains an even number of bits which are set. Here’s a 4 x 4 matrix which has the parity property:
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
The sums of the rows are 2, 0, 4 and 2. The sums of the columns are 2, 2, 2 and 2.
Your job is to write a program that reads in a matrix and checks if it has the parity property. If not, your program should check if the parity property can be established by changing only one bit. If this is not possible either, the matrix should be classified as corrupt.

阅读全文 »

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3225 Accepted: 1401

Description

You have bought a car in order to drive from Waterloo to a big city. The odometer on their car is broken, so you cannot measure distance. But the speedometer and cruise control both work, so the car can maintain a constant speed which can be adjusted from time to time in response to speed limits, traffic jams, and border queues. You have a stopwatch and note the elapsed time every time the speed changes. From time to time you wonder, “how far have I come?”. To solve this problem you must write a program to run on your laptop computer in the passenger seat

阅读全文 »

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6674 Accepted: 3383

Description

If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, …, contains infinitely many prime numbers. This fact is known as Dirichlet’s Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837.

For example, the arithmetic sequence beginning with 2 and increasing by 3, i.e.,

2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, … ,

contains infinitely many prime numbers

2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, … .

Your mission, should you decide to accept it, is to write a program to find the nth prime number in this arithmetic sequence for given positive integers a, d, and n.

阅读全文 »

Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 10581 Accepted: 4410

Description

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

阅读全文 »

Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 4458 Accepted: 2799

Description

Snoopy has three coins. One day he tossed them on a table then and tried to flip some of them so that they had either all heads or all tails facing up. After several attempts, he found that regardless of the initial configuration of the coins, he could always achieve the goal by doing exactly two flippings, under the condition that only one coin could be flipped each time and a coin could be flipped more than once. He also noticed that he could never succeed with less than two flippings.

Snoopy then wondered, if he had n coins, was there a minimum number x such that he could do exactly x flippings to satisfy his requirements?

阅读全文 »

Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 5003 Accepted: 2637

Description

The Lab Cup Table Tennis Competition is going to take place soon among laboratories in PKU. Students from the AI Lab are all extreme enthusiasts in table tennis and hold strong will to represent the lab in the competition. Limited by the quota, however, only one of them can be selected to play in the competition.

To make the selection fair, they agreed on a single round robin tournament, in which every pair of students played a match decided by best of 5 games. The one winning the most matches would become representative of the lab. Now Ava, head of the lab, has in hand a form containing the scores of all matches. Who should she decide on for the competition?

阅读全文 »

Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 11362 Accepted: 6442

Description

Julius Caesar lived in a time of danger and intrigue. The hardest situation Caesar ever faced was keeping himself alive. In order for him to survive, he decided to create one of the first ciphers. This cipher was so incredibly sound, that no one could figure it out without knowing how it worked.

阅读全文 »