20080429ACM练习题

20080429ACM练习题

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10000 Longest Paths

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

It is a well known fact that some people do not have their social abilities completely enabled. One example is the lack of talent for calculating distances and intervals of time. This causes some people to always choose the longest way to go from one place to another, with the consequence that they are late to whatever appointments they have, including weddings and programming contests. This can be highly annoying for their friends.

César has this kind of problem. When he has to go from one point to

another he realizes that he has to visit many people, and thus always chooses the longest path. One of César's friends, Felipe, has understood the nature of the problem. Felipe thinks that with the help of a computer he might be able to calculate the time that César is going to need to arrive to his destination. That way he could spend his time in something more enjoyable than waiting for César.

Your goal is to help Felipe developing a program that computes the length of the longest path that can be constructed in a given graph from a given starting point (César's residence). You can assume that the graph has no cycles (there is no path from any node to itself), so César will reach his destination in a finite time. In the same line of reasoning, nodes are not considered directly connected to themselves. Input

The input consists of a number of cases. The first line on each case contains a positive number n ( ) that specifies the number of points that César might visit (i.e., the number of nodes in the graph).

A value of n = 0 indicates the end of the input.

After this, a second number s is provided, indicating the starting point in César's journey (

). Then, you are given a list of pairs of places p and

q, one pair per line, with the places on each line separated by white-space. The pair ``\sar can visit q after p. A pair of zeros (``0 0\

As mentioned before, you can assume that the graphs provided will not be cyclic. Output

For each test case you have to find the length of the longest path that begins at the starting place. You also have to print the number of the final place of such longest path. If there are several paths of maximum length, print the final place with smallest number.

Print a new line after each test case. Sample Input 2 1 1 2 0 0 5 3 1 2 3 5 3 1 2 4 4 5 0 0 5 5 5 1 5 2 5 3 5 4 4 1 4 2 0 0 0

Sample Output

Case 1: The longest path from 1 has length 1, finishing at 2. Case 2: The longest path from 3 has length 4, finishing at 5. Case 3: The longest path from 5 has length 2, finishing at 1.

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10004 Bicoloring

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In 1976 the ``Four Color Map Theorem\of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.

Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that

no two adjacent nodes have the same color. To simplify the problem you can assume:

? no node will have an edge to itself.

? the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.

? the graph will be strongly connected. That is, there will be at least one path from any node to any other node. Input

The input consists of several test cases. Each test case starts with a line containing the number n ( 1 < n < 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a ( ). An input with n = 0 will mark the end of the input and is not to be processed. Output

You have to decide whether the input graph can be bicolored or not, and print it as shown below. Sample Input 3 3 0 1 1 2 2 0 9 8 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0

Sample Output NOT BICOLORABLE. BICOLORABLE.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10006 Carmichael Numbers

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

An important topic nowadays in computer science is cryptography. Some people even think that cryptography is the only important field in computer science, and that life would not matter at all without cryptography. ?? Alvaro is one of such persons, and is designing a set of cryptographic procedures for cooking paella. Some of the cryptographic algorithms he is implementing make use of big prime numbers. However, checking if a big number is prime is not so easy. An exhaustive approach can require the division of the number by all the prime numbers smaller or equal than its square root. For big numbers, the amount of time and storage needed for such operations would certainly ruin the paella.

However, some probabilistic tests exist that offer high confidence at low cost. One of them is the Fermat test.

Let a be a random number between 2 and n - 1 (being n the number whose primality we are testing). Then, n is probably prime if the following equation holds:

If a number passes the Fermat test several times then it is prime with a high probability.

Unfortunately, there are bad news. Some numbers that are not prime still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers.

In this problem you are asked to write a program to test if a given number is a Carmichael number. Hopefully, the teams that fulfill the task will one day be able to taste a delicious portion of encrypted paella. As a side note, we need to mention that, according to Alvaro, the main advantage of encrypted paella over conventional paella is that nobody but you knows what you are eating. Input

The input will consist of a series of lines, each containing a small positive number n ( 2 < n < 65000). A number n = 0 will mark the end of the input, and must not be processed. Output

For each number in the input, you have to print if it is a Carmichael number or not, as shown in the sample output. Sample Input 1729 17 561 1109 431

0

Sample Output

The number 1729 is a Carmichael number. 17 is normal.

The number 561 is a Carmichael number. 1109 is normal. 431 is normal.

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10015 Joseph’s Cousin

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The Problem

The Joseph’s problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1,2…n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

Although many good programmers have been saved since Joseph spread out this information, Joseph’s Cousin introduced a new variant of the malignant game. This insane character is known for its barbarian ideas and wishes to clean up the world from silly programmers. We had to infiltrate some the agents of the ACM in order to know the process in this new mortal game. In order to save yourself from this evil practice, you must develop a tool capable of predicting which person will be saved. The Destructive Process

The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the prime numbers’ succession (2,3,5,7…). So in order to kill the ith person, Joseph’s cousin counts up to the ith prime.

NOTE: This problem may have a runtime of up to 4 minutes. The Input

It consists of separate lines containing n [1..3501], and finishes with a 0. The Output

The output will consist in separate lines containing the position of the person which life will be saved. Sample Input 6 0

Sample Output 4

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10036 Divisibility

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical

expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 16 17 + 5 + -21 17 + 5 - -21 17 + 5 - -21 17 - 5 + -21 17 - 5 + -21 17 - 5 - -21 17 - 5 - -21

- 15 = -14 + 15 = 58 - 15 = 28 + 15 = 6 - 15 = -24 + 15 = 48 - 15 = 18

We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.

You are to write a program that will determine divisibility of sequence of integers. Input

The first line of the input file contains a integer M indicating the number of cases to be analyzed. Then M couples of lines follow.

For each one of this couples, the first line contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space. The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value. Output

For each case in the input file, write to the output file the word \if given sequence of integers is divisible by K or \ Sample input 2 4 7

17 5 -21 15 4 5

17 5 -21 15

Sample Output Divisible Not divisible

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10036 Divisibility

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical

expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 16 17 + 5 + -21 17 + 5 - -21 17 + 5 - -21 17 - 5 + -21 17 - 5 + -21 17 - 5 - -21 17 - 5 - -21

- 15 = -14 + 15 = 58 - 15 = 28 + 15 = 6 - 15 = -24 + 15 = 48 - 15 = 18

We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.

You are to write a program that will determine divisibility of sequence of integers. Input

The first line of the input file contains a integer M indicating the number of cases to be analyzed. Then M couples of lines follow.

For each one of this couples, the first line contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space. The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value. Output

For each case in the input file, write to the output file the word \if given sequence of integers is divisible by K or \ Sample input 2 4 7

17 5 -21 15 4 5

17 5 -21 15

Sample Output Divisible Not divisible

本文来源：https://www.bwwdw.com/article/xfno.html