Ugly Numbers

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17500 Accepted: 7757

Description

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n’th ugly number.

Input

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.

Output

For each line, output the n’th ugly number .:Don’t deal with the line with n=0.

Sample Input

1
2
9
0

Sample Output

1
2
10

Source

解:
丑陋数是仅有素因子2、3、5的整数,1 * 2, 1 * 3, 1 * 5, 2 * 2, 2 * 3, 2 * 5……这样算下去,得到的是2, 3, 5, 4, 6, 10,而4应该排在5的前面,也就是说这样计算出来的值还要进行排序,感觉非常耗时间,怎么办呢?我们可以创建一个数组,把丑陋数的列表计算出来,然后通过输入值在数组中快速寻找出对应的值。我们得想办法进行动态排序,我们可以先设置3个变量来记录2的倍数、3的倍数、5的倍数的个数,将这些个数作为索引,找出丑陋数列表数组中对应的值,再乘以对应的2、3、5就可以得到现在需要插入列表的2的倍数、3的倍数、5的倍数的值,找到这三个值的最小的数,将这个数添加到数组的最后面,一直循环这个操作就可以实现动态排序了。可能我上面表达得不是很好,看代码应该就清楚了,代码如下:
#include <stdio.h>
int twoNum = 0, threeNum = 0, fiveNum = 0;
int ugly[1500];

void create()
{
	ugly[0] = 1;
	for (int i = 1; i < 1500; i++) {
		int min = ugly[twoNum] * 2, b = ugly[threeNum] * 3, c = ugly[fiveNum] * 5;
		if (b < min) {
			min = b;
		}
		if (c < min) {
			min = c;
		}
		ugly[i] = min;
		if (ugly[i] == ugly[twoNum] * 2) {
			twoNum++;
		}
		if (ugly[i] == ugly[threeNum] * 3) {
			threeNum++;
		}
		if (ugly[i] == ugly[fiveNum] * 5) {
			fiveNum++;
		}
	}
}

int main()
{
	create();
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			return 0;
		}
		printf("%d\n", ugly[n - 1]);
	}
	return 0;
}
Result Memory Time Language Code Length
Accepted 172K 0MS C++ 661B

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