2-1

A 输出200-299之间的所有素数

Description

一个整数如果不能被1和自身以外的所有整数所整除，那么这个数是素数。编写程序找出200~299之间的所有素数。

Input

无输入。

Output

200~299之间的所有素数，每8个数就换行。注意：每一行第一个数字（如211 257）前无空格，每一行最后一个数字（如251 293）后面无空格。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>

using namespace std;

//素数判断函数
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int count = 0;
    for (int num = 200; num <= 299; ++num) {
        if (isPrime(num)) {
            if (count == 8) {
                cout << endl;
                count = 0;
            }
            cout << num;
            if (num != 299) {
                cout << " ";
            }
            ++count;
        }
    }
    cout << endl;
    return 0;
}

B 深入浅出学算法002-n个1

深入浅出学算法002-n个1 

Description

由n个1组成的整数能被K（K<10000)整除，n至少为多少？

Input

多组测试数据，第一行输入整数T,表示组数 然后是T行，每行输入1个整数代表K

Output

对于每组测试数据输出1行，值为n

Sample Input

1
2
1
11

Sample Output

1
2

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int K;
        cin >> K;

        int n = 1;
        int remainder = 1 % K;

        while (remainder != 0) {
            n++;
            remainder = (remainder * 10 + 1) % K;
        }

        cout << n << endl;
    }

    return 0;
}

C 深入浅出学算法005-数7

Description

逢年过节，三五好友，相约小聚，酒过三旬，围桌数七。 “数七”是一个酒桌上玩的小游戏。就是按照顺序，某人报一个10以下的数字，然后后面的人依次在原来的数字上加1，并喊出来，当然如果要喊的数包含7或者是7的倍数，那么不能直接喊，可以敲一下筷子，否则就算输，要罚酒一杯。

Input

多组测试数据，先输入整数T表示组数， 每组测试数据输入一个10以下的正整数，

Output

对于每组测试数据，输出在一行，要求从小到大输出所报数（含）到100之间所有不能喊的数字

Sample Input

1
2
1
3

Sample Output

1
7 14 17 21 27 28...

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        for (int i = n; i <= 100; ++i) {
            if (i % 7 == 0 || i % 10 == 7) {
                cout << i << " ";
            }
        }

        cout << endl;
    }

    return 0;
}

D 兑换支票

Problem Description:
There are three kinds of coins:1,2,2,3$.

Given a chique of N$(0<n<=10^9),calculate the number of different ways to exchange the cheque.

Sample Input:1 2 3

Sample Outpt:1 2 3

E Number Sequence

Problem Description

A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).

Input

The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

Output

For each test case, print the value of f(n) on a single line.

Sample Input

1
2
3
1 1 3
1 2 10
0 0 0

Sample Output

1
2
2
5

Author

CHEN, Shunbao

Source

ZJCPC2004

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include<cstdio>

using namespace std;
#define mod 7
int f[50];

int main() {
    int a, b;
    long long n;
    while (scanf("%d%d%lld", &a, &b, &n)) {
        if (!a && !b && !n)
            break;
        f[1] = f[2] = 1;
        for (int i = 3; i <= 49; i++)
            f[i] = (a * f[i - 1] + b * f[i - 2]) % mod;
        printf("%d\n", f[n % 49]);
    }
    return 0;

}

F 水果配载

Description

水果销售公司接了一个单子，现要从公司将货运到火车站。水果都用箱子装好了，现有三种型号的，分别重量为910、462、和235kg的。现在有不同装载量的货车，请根据装载量给不同货车设计配载方案，使装载的重量总和最大。

Input

多个测试案例，每个一行，输入货车的最大装载量m(m不超过20000），最后一行是0,不需要处理

Output

每个测试案例输出分2行第一行输出"Solution A is:“,然后是三种箱子各多少个，中间用一个空格隔开第二行输出"Load A is:”,然后是总载重量其中A是第几个测试案例。

Sample Input

1
2
8000
0

Sample Output

1
2
Solution 1 is: 7 2 3
Load 1 is: 7999

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstring>
using namespace std;

int f[20001][3];
bool v[20001];

int main()
{
    int i, j, l, n, cas = 0;
    int w[3] = {235, 462, 910};

    while (cin >> n && n != 0)
    {
        cas++;

        if (n < 235)
        {
            cout << "Solution " << cas << " is: 0 0 0" << endl;
            cout << "Load " << cas << " is: 0" << endl;
            continue;
        }

        memset(v, false, sizeof(v));
        memset(f, 0, sizeof(f));
        v[0] = true;

        for (i = 0; i < 3; i++)
        {
            for (j = w[i]; j <= n; j++)
            {
                if (v[j - w[i]] && !v[j])
                {
                    for (l = 0; l < 3; l++)
                    {
                        if (l == i)
                            f[j][l] = f[j - w[i]][l] + 1;
                        else
                            f[j][l] = f[j - w[i]][l];
                    }
                    v[j] = true;
                }
            }
        }

        for (; n >= 235; n--)
        {
            if (v[n])
            {
                cout << "Solution " << cas << " is: " << f[n][2] << " " << f[n][1] << " " << f[n][0] << endl;
                cout << "Load " << cas << " is: " << n << endl;
                break;
            }
        }
    }

    return 0;
}

Delta-wave

Description

A triangle field is numbered with successive integers in the way shown on the picture below.

The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the traveller’s route.

Write the program to determine the length of the shortest route connecting cells with numbers N and M.

Input

Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).

Output

Output should contain the length of the shortest route.

Sample Input

1
6 12

Sample Output

1
3

Source

Ural Collegiate Programming Contest 1998

问题链接：POJ2619 HDU1030 Delta-wave

问题简述：

描述

三角形字段按下图所示的方式用连续整数编号。

旅行者需要从编号为 M 的牢房转到编号为 N 的牢房。旅行者只能通过像元边缘进入像元，他不能通过顶点从一个像元移动到另一个像元。旅行者经过的边数决定了旅行者路线的长度。

编写程序以确定连接数字 N 和 M 的单元格的最短路径的长度。

image.png

输入

输入包含两个整数 M 和 N，范围为 1 到 1000000000，用空格分隔。

输出

输出应包含最短路径的长度。

问题分析：

这是一个数学题，需要找出计算规律。

要想算出m到n的距离，需要从一个地方按行走、按左下方向走和按右下方向走，把这三个距离都加起来就得到了距离。

程序说明：

程序中的数组start[]和dest[]分别用于存储各行的起始值和终止值，然后搜索计算即可。

上述这两个数组最大需要多大，可以通过条件编译语句先算一下。

题记：（略）

参考链接：（略）

AC的C++语言程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/* POJ2619 HDU1030 Delta-wave */
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
 
//#define DEBUG
 
using namespace std;
 
const int N = 1e9;
const int N1 = 32000;
int start[N1], dest[N1];
 
void init()
{
        int t = 1;
        for(int i=1, j=1; ;i+=2, j++)
        {
            start[j] = t;
            dest[j] = (t += i) - 1;
            if(t > N) {
#ifdef DEBUG
                printf("N2=%d\n", j);
#endif
                break;
            }
        }
}
 
int find(int x)
{
    for(int i=1; ;i++)
        if(x <= dest[i])
            return i;
}
 
int main()
{
    init();
 
    int m, n, ans;
    while(scanf("%d%d", &m, &n)==2) {
        int mline = find(m);
        int nline = find(n);
        ans = abs(nline - mline) +
                abs((n - start[nline]) / 2 - (m-start[mline]) / 2) +
                abs((dest[nline] - n) / 2 - (dest[mline] - m) / 2);
 
        printf("%d\n", ans);
    }
 
    return 0;
}