## 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

```#include <stdio.h>
int twoNum = 0, threeNum = 0, fiveNum = 0;
int ugly;

void create()
{
ugly = 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 = {0};
char input;
for (i = 0; i < 4; i++) {
char input = {' '};
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```

```#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```

```#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

```#include <stdio.h>
#include <math.h>
#define N 1000000
bool prime[N];

void generatePrime() {
int i, j;
prime = false;
prime = 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

## 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.

```#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;
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