# 标签存档: 解题报告

## 滑雪

Time Limit: 1000MS Memory Limit: 65536K

### Description

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9


### Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9


### Sample Output

25


### Source

SHTSC 2002


[……]

Continue

## Fake Tickets

Time Limit: 1 Seconds Memory Limit: 32768 KB

Your school organized a big party to celebrate your team brilliant win in the prestigious, worldfamous ICPC (International Collegiate Poetry Contest). Everyone in your school was invited for an evening which included cocktail, dinner and a session where your team work was read to the audience. The evening was a success – many more people than you expected showed interested in your poetry – although some critics of yours said it was food rather than words that attracted such an audience.

Whatever the reason, the next day you found out why the school hall had seemed so full: the school director confided he had discovered that several of the tickets used by the guests were fake. The real tickets were numbered sequentially from 1 to N (N <= 10000). The director suspects some people had used the school scanner and printer from the Computer Room to produce copies of the real tickets. The director gave you a pack with all tickets collected from the guests at the party's entrance, and asked you to determine how many tickets in the pack had 'clones', that is, another ticket with the same sequence number.

Input

The input contains data for several test cases. Each test case has two lines. The first line contains two integers N and M which indicate respectively the number of original tickets and the number of persons attending the party (1 <= N <= 10000 and 1 <= M <= 20000). The second line of a test case contains M integers Ti representing the ticket numbers in the pack the director gave you (1 <= Ti <= N). The end of input is indicated by N = M = 0.

Output

For each test case your program should print one line, containing the number of tickets in the pack that had another ticket with the same sequence number.

[……]

Continue

## Gamblers

Time Limit: 1 Seconds Memory Limit: 32768 KB

A group of n gamblers decide to play a game:

At the beginning of the game each of them will cover up his wager on the table and the assitant must make sure that there are no two gamblers have put the same amount. If one has no money left, one may borrow some chips and his wager amount is considered to be negative. Assume that they all bet integer amount of money.

Then when they unveil their wagers, the winner is the one who’s bet is exactly the same as the sum of that of 3 other gamblers. If there are more than one winners, the one with the largest bet wins.

For example, suppose Tom, Bill, John, Roger and Bush bet $2,$3, $5,$7 and $12, respectively. Then the winner is Bush with$12 since $2 +$3 + $7 =$12 and it’s the largest bet.

Input

Wagers of several groups of gamblers, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of gamblers in a group, followed by their amount of wagers, one per line. Each wager is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

Output

For each group, a single line containing the wager amount of the winner, or a single line containing “no solution”.

[……]

Continue

## A Mathematical Curiosity

Time Limit: 1 Seconds Memory Limit: 32768 KB

Given two integers n and m, count the number of pairs of integers (a,b) such that 0 < a < b < n and (a^2+b^2 +m)/(ab) is an integer.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

You will be given a number of cases in the input. Each case is specified by a line containing the integers n and m. The end of input is indicated by a case in which n = m = 0. You may assume that 0 < n <= 100.

Output

For each case, print the case number as well as the number of pairs (a,b) satisfying the given property. Print the output for each case on one line in the format as shown below.

[……]

Continue

## Calendar

Time Limit: 1 Seconds Memory Limit: 32768 KB

A calendar is a system for measuring time, from hours and minutes, to months and days, and finally to years and centuries. The terms of hour, day, month, year and century are all units of time measurements of a calender system.

According to the Gregorian calendar, which is the civil calendar in use today, years evenly divisible by 4 are leap years, with the exception of centurial years that are not evenly divisible by 400. Therefore, the years 1700, 1800, 1900 and 2100 are not leap years, but 1600, 2000, and 2400 are leap years.

Given the number of days that have elapsed since January 1, 2000 A.D, your mission is to find the date and the day of the week.

Input

The input consists of lines each containing a positive integer, which is the number of days that have elapsed since January 1, 2000 A.D. The last line contains an integer -1, which should not be processed. You may assume that the resulting date won’t be after the year 9999.

Output

For each test case, output one line containing the date and the day of the week in the format of “YYYY-MM-DD DayOfWeek”, where “DayOfWeek” must be one of “Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday” and “Saturday”.

[……]

Continue

## Rugby Football

Time Limit: 2 Seconds Memory Limit: 65536 KB

CM is a member of Rugby football club of ZJU. He loves to play the game. Every Friday afternoon there is a club training of skills. CM wants to make it more effective.

In the training, N club members including CM stand at staring line in a row. The maximum velocity of the i-th player is Vi. The distance between the line and touchdown zone is L. The goal is to send the ball to touchdown zone. They can pass the ball to others but forward passing is illegal. If someone reaches touchdown zone with ball, the team scores and it will be an effective training.

This picture illustrate the rule of passing ball.

But the way to scoring is not easy because of crazy opponents. Any player with the ball cannot rush more than T seconds or he will be tackled. And he cannot be passed again because he will be very tired after sprinting; even have not for T seconds enough. At the beginning CM can choose who takes the ball first. Now CM wants to know whether they can score and how fast they can.

[……]

Continue

## Beautiful Number

Time Limit: 1 Seconds Memory Limit: 32768 KB

Mike is very lucky, as he has two beautiful numbers, 3 and 5. But he is so greedy that he wants infinite beautiful numbers. So he declares that any positive number which is dividable by 3 or 5 is beautiful number. Given you an integer N (1 <= N <= 100000), could you please tell mike the Nth beautiful number?

Input

The input consists of one or more test cases. For each test case, there is a single line containing an integer N.

Output

For each test case in the input, output the result on a line by itself.

[……]

Continue

## Semi-Prime

Time Limit: 1 Seconds Memory Limit: 32768 KB

Prime Number Definition

An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For instance, 2, 11, 67, 89 are prime numbers but 8, 20, 27 are not.

Semi-Prime Number Definition

An integer greater than one is called a semi-prime number if it can be decompounded to TWO prime numbers. For example, 6 is a semi-prime number but 12 is not.

Your task is just to determinate whether a given number is a semi-prime number.

Input

There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000)

Output

One line with a single integer for each case. If the number is a semi-prime number, then output “Yes”, otherwise “No”.

[……]

Continue

## Palindromes

Time Limit: 1 Seconds Memory Limit: 32768 KB

A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string “ABCDEDCBA” is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left.

Now give you a string S, you should count how many palindromes in any consecutive substring of S.

Input

There are several test cases in the input. Each case contains a non-empty string which has no more than 5000 characters.Proceed to the end of file.

Output

A single line with the number of palindrome substrings for each case.

[……]

Continue

## SGU 276 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=276

## 276. Andrew’s Troubles

time limit per test: 1 sec.
memory limit per test: 65536 KB

Famous Berland ACM-ICPC team Anisovka consists of three programmers: Andrew, Michael and Ilya. A long time ago, during the first few months the team was founded, Andrew was very often late to the trainings and contests. To stimulate Andrew to be more punctual, Ilya and Andrew decided to introduce a new rule for team participants. If somebody is late (i.e. comes at least one second after appointed time) he owes a cup of tea to other team members. If he is late for 5 minutes, he owes two cups of tea. If he is late for 15 minutes, he owes three cups of tea. And if he is late for 30 minutes or more, he owes 4 cups of tea.

The training starts at the time S (counted in seconds, from some predefined moment of time) and Andrew comes at the time P (also in seconds, counted from the same moment of time).

Your task is to find how many cups of tea Andrew owes.

[……]

Continue