Vertical Histogram

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 15400 Accepted: 7462

Description

Write a program to read four lines of upper case (i.e., all CAPITAL LETTERS) text input (no more than 72 characters per line) from the input file and print a vertical histogram that shows how many times each letter (but not blanks, digits, or punctuation) appears in the all-upper-case input. Format your output exactly as shown.

Input

* Lines 1..4: Four lines of upper case text, no more than 72 characters per line.

Output

* Lines 1..??: Several lines with asterisks and spaces followed by one line with the upper-case alphabet separated by spaces. Do not print unneeded blanks at the end of any line. Do not print any leading blank lines.

Sample Input

THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!

Sample Output

                            *
                            *
        *                   *
        *                   *     *   *
        *                   *     *   *
*       *     *             *     *   *
*       *     * *     * *   *     * * *
*       *   * * *     * *   * *   * * * *
*     * * * * * *     * * * * *   * * * *     * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
解:
这道题其实挺简单的,大家直接看代码就懂了。
#include"stdio.h"
int main()
{
	int i, max = 0, count[26] = {0};
	char input[72];
	for (i = 0; i < 4; i++) {
		char input[72] = {' '};
		gets(input);
		for (int j = 0; j < 72; j++) {
			int map = input[j] - 65;
			if (map >= 0 && map <= 25) {
				count[map]++;
				if (count[map] > max) {
					max = count[map];
				}
			}
		}
	}
	for (i = max; i > 0; i--) {
		for (int j = 0; j < 26; j++) {
			if (count[j] >= i) {
				count[j]--;
				if (j == 25) {
					printf("*");
				} else {
					printf("* ");
				}
			} else {
				if (j == 25) {
					printf(" ");
				} else {
					printf("  ");
				}
			}
		}
		printf("\n");
	}
	for (i = 0; i < 26; i++) {
		if (i == 25) {
			printf("%c", (char)(i + 65));
		} else {
			printf("%c ", (char)(i + 65));
		}
	}
	printf("\n");
	return 0;
}
Result Memory Time Language Code Length
Accepted 160K 0MS C++ 825B

The Circumference of the Circle

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 6334 Accepted: 4003

Description

To calculate the circumference of a circle seems to be an easy task – provided you know its diameter. But what if you don’t?

You are given the cartesian coordinates of three non-collinear points in the plane.
Your job is to calculate the circumference of the unique circle that intersects all three points.

Input

The input will contain one or more test cases. Each test case consists of one line containing six real numbers x1,y1, x2,y2,x3,y3, representing the coordinates of the three points. The diameter of the circle determined by the three points will never exceed a million. Input is terminated by end of file.

Output

For each test case, print one line containing one real number telling the circumference of the circle determined by the three points. The circumference is to be printed accurately rounded to two decimals. The value of pi is approximately 3.141592653589793.

Sample Input

0.0 -0.5 0.5 0.0 0.0 0.5
0.0 0.0 0.0 1.0 1.0 1.0
5.0 5.0 5.0 7.0 4.0 6.0
0.0 0.0 -1.0 7.0 7.0 7.0
50.0 50.0 50.0 70.0 40.0 60.0
0.0 0.0 10.0 0.0 20.0 1.0
0.0 -500000.0 500000.0 0.0 0.0 500000.0

Sample Output

3.14
4.44
6.28
31.42
62.83
632.24
3141592.65
解:
这道题我使用的是初等几何的知识,设a = AB间的距离,b = BC间的距离,c = CA之间的距离,p = (a + b + c) / 2,根据海伦公式,面积s = sqrt(p * (p – a) * (p – b) * (p – c)),外接圆的直接d = a * b * c / 2 / s,外接圆的周长l = d * π。然后我们在程序中需要将变量设置为double类型,不要设置float,题目给的π太长了,否则会WA。
#include <stdio.h>
#include <math.h>
int main()
{
	double x1, y1, x2, y2, x3, y3, a, b, c, p, s, d, l;
	while (scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3) != EOF) {
		a = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
		b = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
		c = sqrt((x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2));
		p = (a + b + c) / 2;
		s = sqrt(p * (p - a) * (p - b) * (p - c));
		d = a * b * c / 2 / s;
		l = d * 3.141592653589793;
		printf("%.2f\n", l);
	}
	return 0;
}
Result Memory Time Language Code Length
Accepted 180K 0MS C++ 537B

Dirichlet’s Theorem on Arithmetic Progressions(素数判断算法的探究)

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 12763 Accepted: 6419

Description

If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., aa + da + 2da + 3da + 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 ad, and n.

Input

The input is a sequence of datasets. A dataset is a line containing three positive integers ad, and n separated by a space. a and d are relatively prime. You may assume a <= 9307, d <= 346, and n <= 210.

The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.

Output

The output should be composed of as many lines as the number of the input datasets. Each line should contain a single integer and should never contain extra characters.

The output integer corresponding to a dataset adn should be the nth prime number among those contained in the arithmetic sequence beginning with a and increasing by d.

FYI, it is known that the result is always less than 106 (one million) under this input condition.

Sample Input

367 186 151
179 10 203
271 37 39
103 230 1
27 104 185
253 50 85
1 1 1
9075 337 210
307 24 79
331 221 177
259 170 40
269 58 102
0 0 0

Sample Output

92809
6709
12037
103
93523
14503
2
899429
5107
412717
22699
25673
解:
这道题重点是素数的求法,素数常规有3种方法,设待判断的数x,一种是i = 2; i <= x,第二种是i = 2; i <= x/2,第三种是i = 2; i <= sqrt((float)x)。当然更快的还有筛法,这里使用常规的第三种和筛法做为示例,看看效果如何。
首先是第三种是i = 2; i <= sqrt((float)x)的代码和结果:
#include <stdio.h>
#include <math.h>
bool isPrime(int x) {
	if(x < 2) {
		return false;
	} else {
		for(int i = 2; i <= sqrt((float)x); i++) {
			if(x % i == 0) {
				return false;
			}
		}
		return true;
	}
}

int main()
{
	int a, d, n;
	while (scanf("%d %d %d", &a, &d, &n) != EOF) {
		if (a == 0 && d == 0 && n == 0) {
			return 0;
		}
		int i, count = 0;
		for (i = a; count < n; i += d) {
			if (isPrime(i)) {
				count++;
			}
		}
		printf("%d\n", i - d);
	}
	return 0;
}
Result Memory Time Language Code Length
Accepted 188K 250MS C++ 508B
这个方法内存使用了188K,时间使用了250MS,时间用得还是算较多的。
接下来是筛法来计算素数,代码和结果如下:
#include <stdio.h>
#include <math.h>
#define N 1000000
bool prime[N];

void generatePrime() {
	int i, j;
	prime[0] = false;
	prime[1] = false;
	for (i = 2; i < N; i++) {
		if (i % 2 == 0 && i != 2) {
			prime[i] = false;
		} else {
			prime[i] = true;
		}
	}
	for (i = 3; i <= sqrt((float)N); i++) {
		if (prime[i]) {
			for (j = 3 * i; j < N; j += 2 * i) {
				prime[j] = false;
			}
		}
	}
}

int main()
{
	generatePrime();
	int a, d, n;
	while (scanf("%d %d %d", &a, &d, &n) != EOF) {
		if (a == 0 && d == 0 && n == 0) {
			return 0;
		}
		int i, count = 0;
		for (i = a; count < n; i += d) {
			if (prime[i]) {
				count++;
			}
		}
		printf("%d\n", i - d);
	}
	return 0;
}
Result Memory Time Language Code Length
Accepted 1164K 16MS C++ 719B
这个方法内存使用了1164K,时间使用了16MS,时间用得非常非常少,而内存却用了挺多的,但是我们ACM主要看时间,用空间换取时间,这个排名已经很靠前了。这个方法是从《素数判断算法(高效率)》一文中学习来的,我在它的基础上进行了修改,其实原文的算法是有几个错误的,比如0,1,2没有判断掉,原文的 for (j = i + i; j < N; j += i)被我用for (j = 3 * i; j < N; j += 2 * i),因为i + i = 2i,这个其实在上面的模2的时候已经判断过了,所以可以跳得大步点,j += i这个改成j += 2 * i是配合我改的这个,这样跳得就比之前大步多了,理论上可以少判断很多的数。

Pascal Library

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4239 Accepted: 2037

Description

Pascal University, one of the oldest in the country, needs to renovate its Library Building, because after all these centuries the building started to show the effects of supporting the weight of the enormous amount of books it houses.

To help in the renovation, the Alumni Association of the University decided to organize a series of fund-raising dinners, for which all alumni were invited. These events proved to be a huge success and several were organized during the past year. (One of the reasons for the success of this initiative seems to be the fact that students that went through the Pascal system of education have fond memories of that time and would love to see a renovated Pascal Library.)

The organizers maintained a spreadsheet indicating which alumni participated in each dinner. Now they want your help to determine whether any alumnus or alumna took part in all of the dinners.

Input

The input contains several test cases. The first line of a test case contains two integers N and D indicating respectively the number of alumni and the number of dinners organized (1 <= N <= 100 and 1 <= D <= 500). Alumni are identified by integers from 1 to N. Each of the next D lines describes the attendees of a dinner, and contains N integers Xi indicating if the alumnus/alumna i attended that dinner (Xi = 1) or not (Xi = 0). The end of input is indicated by N = D = 0.

Output

For each test case in the input your program must produce one line of output, containing either the word `yes’, in case there exists at least one alumnus/alumna that attended all dinners, or the word `no’ otherwise.

Sample Input

3 3
1 1 1
0 1 1
1 1 1
7 2
1 0 1 0 1 0 1
0 1 0 1 0 1 0
0 0

Sample Output

yes
no

Hint

Alumna: a former female student of a particular school, college or university.
Alumnus: a former male student of a particular school, college or university.
Alumni: former students of either sex of a particular school, college or university.
解:
这道题是计算是否至少有一个校友出席每次的宴会,先初始化所有的校友,标识为1,然后如果有一次没出席就把标识改为0,最后判断是否存在标识为1的,这样就可以说明存在至少有一个校友出席了每次的宴会。
#include <stdio.h>
int main()
{
	int x, y;
	while(scanf("%d %d", &x, &y)) {
		if (x == 0 && y == 0) {
			return 0;
		}
		int n;
		int record[100];
		for (int i = 0; i < x; i++) {
			record[i] = 1;
		}
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++) {
				scanf("%d", &n);
				if (n == 0) {
					record[j] = 0;
				}
			}
		}
		bool yesornot = false;
		for (int i = 0; i < x; i++) {
			if (record[i] == 1) {
				yesornot = true;
				break;
			}
		}
		yesornot ? printf("yes\n") : printf("no\n");
	}
	return 0;
}
Result Memory Time Language Code Length
Accepted 164K 16MS C++ 563B

The 3n + 1 problem

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 45447 Accepted: 14278

Description

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.
Consider the following algorithm:

 

		1. 		 input n

		2. 		 print n

		3. 		 if n = 1 then STOP

		4. 		 		 if n is odd then   n <-- 3n+1

		5. 		 		 else   n <-- n/2

		6. 		 GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed before the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 10,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174
解:
这道题需要计算输入的两个数之间所有数值按照题目所给的算法直到1所需要循环的次数,题目不是很容易看懂。虽然样式输入的两个数前面的是小于后面的,但是我们还是需要判断大小的,不然会WA。
#include <stdio.h>
int algorithm(int para) {
    int count = 1;
    while (para != 1) {
        if (para % 2 != 0) {
            para = 3 * para + 1;
        } else {
            para /= 2;
        }
        count++;
    }
    return count;
}
 
int main()
{
    int x, y, max, result, left, right;
    while (scanf("%d %d", &x, &y) != EOF) {
        max = 0;
        if (x <= y) {
            left = x;
            right = y;
        } else {
            right = x;
            left = y;
        }
        for (int i = left; i <= right; i++) {
            result = algorithm(i);
            max = result > max ? result : max;
        }
		printf("%d %d %d\n", x, y, max);
    }
    return 0;
}
Result Memory Time Language Code Length
Accepted 164K 0MS C++ 725B