9月 | 2015 | 超客的水墨烟雨

poj1751

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

15 9月 2015

HighwaysThe island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has a very poor system of public highways. The Flatopian government is aware of this problem and has already constructed a number of highways connecting some of the most important towns. However, there are still some towns that you can't reach via a highway. It is necessary to build more highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N and town i has a position given by the Cartesian coordinates (xi, yi). Each highway connects exaclty two towns. All highways (both the original ones and the ones that are to be built) follow straight lines, and thus their length is equal to Cartesian distance between towns. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the cost of building new highways. However, they want to guarantee that every town is highway-reachable from every other town. Since Flatopia is so flat, the cost of a highway is always proportional to its length. Thus, the least expensive highway system will be the one that minimizes the total highways length.Input

The input consists of two parts. The first part describes all towns in the country, and the second part describes all of the highways that have already been built.

The first line of the input file contains a single integer N (1 <= N <= 750), representing the number of towns. The next N lines each contain two integers, xi and yi separated by a space. These values give the coordinates of i^th town (for i from 1 to N). Coordinates will have an absolute value no greater than 10000. Every town has a unique location.

The next line contains a single integer M (0 <= M <= 1000), representing the number of existing highways. The next M lines each contain a pair of integers separated by a space. These two integers give a pair of town numbers which are already connected by a highway. Each pair of towns is connected by at most one highway.

Output

Write to the output a single line for each new highway that should be built in order to connect all towns with minimal possible total length of new highways. Each highway should be presented by printing town numbers that this highway connects, separated by a space.

If no new highways need to be built (all towns are already connected), then the output file should be created but it should be empty.

Sample Input

1 5

0 0

3 2

4 5

5 1

0 4

5 2

1 2

5 3

1 3

9 7

1 2

Sample Output

1 6

3 7

4 9

5 7

8 3

Source

Northeastern Europe 1999

题目类型：MST

算法分析：读入坐标并计算坐标之间的距离(权值)，然后直接使用kruskal算法计算并记录新增加的边的信息。最后直接输出新增加的边的两个节点即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 766 + 66;

struct Node
{
    double x, y;
};

Node ans[maxn];

struct Point
{
    int u, v;
    double w;
};

Point edge[maxn*maxn/2], output[maxn*maxn/2];;

int parent[maxn], len, len_output;
int n, m;

int UnFind (int val)
{
    if (parent[val] == val)
        return val;

return parent[val] = UnFind (parent[val]);
}

bool Cmp (Point a, Point b)
{
    return a.w < b.w;
}


void kruskal ()
{
    len_output = 0;
    int i;
    int remain = n;

    for (i = 0; i < len && remain > 1; i++)
    {
        if (UnFind (edge[i].u) != UnFind (edge[i].v))
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            output[len_output++] = edge[i];
            remain--;
        }
    }
}
int main()
{
//    freopen ("aaa.txt", "r", stdin);



    while (scanf ("%d", &n) != EOF)
    {
        int i;
        for (i = 0; i < n; i++)
            scanf ("%lf%lf", &ans[i].x, &ans[i].y);

        int j;

        len = 0;

        for (i = 0; i < n - 1; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                edge[len].u = i + 1;
                edge[len].v = j + 1;
                edge[len].w = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2));
                len++;
            }
        }

        sort (edge, edge + len, Cmp);

        cin >> m;
        int temp_a, temp_b;

         for (i = 0; i < maxn; i++)
            parent[i] = i;

        for (i = 0; i < m; i++)
        {
            cin >> temp_a >> temp_b;
            if (UnFind (temp_a) != UnFind (temp_b))
            {
                parent[UnFind(temp_a)] = UnFind (temp_b);
            }
        }

        kruskal ();

        for (i = 0; i < len_output; i++)
            printf ("%d %d\n", output[i].u, output[i].v);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 766 + 66;

struct Node

{

double x, y;

};

Node ans[maxn];

struct Point

{

int u, v;

double w;

};

Point edge[maxn*maxn/2], output[maxn*maxn/2];;

int parent[maxn], len, len_output;

int n, m;

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

bool Cmp (Point a, Point b)

{

return a.w < b.w;

}

void kruskal ()

{

len_output = 0;

int i;

int remain = n;

for (i = 0; i < len && remain > 1; i++)

{

if (UnFind (edge[i].u) != UnFind (edge[i].v))

{

parent[UnFind(edge[i].u)] = UnFind (edge[i].v);

output[len_output++] = edge[i];

remain--;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

while (scanf ("%d", &n) != EOF)

{

int i;

for (i = 0; i < n; i++)

scanf ("%lf%lf", &ans[i].x, &ans[i].y);

int j;

len = 0;

for (i = 0; i < n - 1; i++)

{

for (j = i + 1; j < n; j++)

{

edge[len].u = i + 1;

edge[len].v = j + 1;

edge[len].w = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2));

len++;

}

sort (edge, edge + len, Cmp);

cin >> m;

int temp_a, temp_b;

for (i = 0; i < maxn; i++)

parent[i] = i;

for (i = 0; i < m; i++)

{

cin >> temp_a >> temp_b;

if (UnFind (temp_a) != UnFind (temp_b))

{

parent[UnFind(temp_a)] = UnFind (temp_b);

}

kruskal ();

for (i = 0; i < len_output; i++)

printf ("%d %d\n", output[i].u, output[i].v);

}

return 0;

}

poj1738

maksyuki 发表于 oj 分类，标签: 其他-GarsiaWachs算法

15 9月 2015

An old Stone Game

There is an old stone game.At the beginning of the game the player picks n(1<=n<=50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules:
At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile. You are to write a program to determine the minimum of the total score.

Input

The input contains several test cases. The first line of each test case contains an integer n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.
The last test case is followed by one zero.

Output

For each test case output the answer on a single line.You may assume the answer will not exceed 1000000000.

Sample Input

100

3 4 3

1 1 1 1

Sample Output

Source

LouTiancheng@POJ

题目类型：石子合并GarsiaWachs算法

算法分析：直接使用GarsiaWachs算法求解即可，最好使用平衡树优化，否则直接使用O(n ^ 2)的算法很可能会TLE!!!!!!

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 500000 + 66;

int stone[maxn];
int n, t, ans;

void Combine (int k)
{
    int temp = stone[k] + stone[k-1];
    ans += temp;
    for (int i = k; i < t - 1; i++)
        stone[i] = stone[i+1];
    t--;

    int j = 0;
    for(j = k - 1; j > 0 && stone[j-1] < temp; j--)
        stone[j] = stone[j-1];
    stone[j] = temp;

    while (j >= 2 && stone[j] >= stone[j-2])
    {
        int d = t - j;
        Combine (j - 1);
        j = t - d;
    }
}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    while (cin >> n)
    {
        if (n == 0) break ;

        for (int i = 0;i < n; i++)
            cin >> stone[i];

        t = 1, ans = 0;
        for (int i = 1; i < n; i++)
        {
            stone[t++] = stone[i];
            while (t >= 3 && stone[t-3] <= stone[t-1])
                Combine (t - 2);
        }
        while (t > 1) Combine (t - 1);

        cout << ans << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 500000 + 66;

int stone[maxn];

int n, t, ans;

void Combine (int k)

{

int temp = stone[k] + stone[k-1];

ans += temp;

for (int i = k; i < t - 1; i++)

stone[i] = stone[i+1];

t--;

int j = 0;

for(j = k - 1; j > 0 && stone[j-1] < temp; j--)

stone[j] = stone[j-1];

stone[j] = temp;

while (j >= 2 && stone[j] >= stone[j-2])

{

int d = t - j;

Combine (j - 1);

j = t - d;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

while (cin >> n)

{

if (n == 0) break ;

for (int i = 0;i < n; i++)

cin >> stone[i];

t = 1, ans = 0;

for (int i = 1; i < n; i++)

{

stone[t++] = stone[i];

while (t >= 3 && stone[t-3] <= stone[t-1])

Combine (t - 2);

}

while (t > 1) Combine (t - 1);

cout << ans << endl;

}

return 0;

}

poj1703

maksyuki 发表于 oj 分类，标签: 数据结构-并查集

15 9月 2015

Find them, Catch them

The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.) Assume N (N <= 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 10^5) messages in sequence, which are in the following two kinds:

1. D [a] [b]
where [a] and [b] are the numbers of two criminals, and they belong to different gangs.

2. A [a] [b]
where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case begins with a line with two integers N and M, followed by M lines each containing one message as described above.

Output

For each message "A [a] [b]" in each case, your program should give the judgment based on the information got before. The answers might be one of "In the same gang.", "In different gangs." and "Not sure yet."

Sample Input

5 5

A 1 2

D 1 2

A 1 2

D 2 4

A 1 4

Sample Output

Not sure yet.

In different gangs.

In the same gang.

Source

POJ Monthly--2004.07.18

题目类型：带权并查集

算法分析：简化的带权并查集，rel数组中0表示两个人在同一个帮派中，1表示两个人不在同一个帮派中。注意推导出的求两个根节点关系的公式

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 100000 + 66;

int parent[maxn], rel[maxn];

int UnFind (int val)
{
    if (parent[val] != val)
    {
        int temp = parent[val];
        parent[val] = UnFind (parent[val]);
        rel[val] = (rel[val] + rel[temp]) % 2;
    }

return parent[val];
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t;
    scanf ("%d", &t);

    while (t--)
    {
        int n, m;
        scanf ("%d%d", &n, &m);

        int i;
        for (i = 0; i < n + 6; i++)
        {
            parent[i] = i;
            rel[i] = 0;
        }

        for (i = 0; i < m; i++)
        {
            char flag[3];
            int a, b;

            scanf ("%s%d%d", &flag, &a, &b);

            int p_a = UnFind (a);
            int p_b = UnFind (b);

            if (flag[0] == 'A')
            {
                if (p_a != p_b)
                    printf ("Not sure yet.\n");

                else
                {
                    if (rel[a] != rel[b])
                        printf ("In different gangs.\n");

                    else
                        printf ("In the same gang.\n");
                }
            }

            else
            {
                parent[p_b] = p_a;
                rel[p_b] = (rel[a] - rel[b] + 1) % 2;
            }
        }
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 100000 + 66;

int parent[maxn], rel[maxn];

int UnFind (int val)

{

if (parent[val] != val)

{

int temp = parent[val];

parent[val] = UnFind (parent[val]);

rel[val] = (rel[val] + rel[temp]) % 2;

}

return parent[val];

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t;

scanf ("%d", &t);

while (t--)

{

int n, m;

scanf ("%d%d", &n, &m);

int i;

for (i = 0; i < n + 6; i++)

{

parent[i] = i;

rel[i] = 0;

}

for (i = 0; i < m; i++)

{

char flag[3];

int a, b;

scanf ("%s%d%d", &flag, &a, &b);

int p_a = UnFind (a);

int p_b = UnFind (b);

if (flag[0] == 'A')

{

if (p_a != p_b)

printf ("Not sure yet.\n");

else

{

if (rel[a] != rel[b])

printf ("In different gangs.\n");

else

printf ("In the same gang.\n");

}

else

{

parent[p_b] = p_a;

rel[p_b] = (rel[a] - rel[b] + 1) % 2;

}

return 0;

}

poj1700

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

15 9月 2015

Crossing River

A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river. Each case is preceded by a blank line. There won't be more than 1000 people and nobody takes more than 100 seconds to cross.

Output

For each test case, print a line containing the total number of seconds required for all the N people to cross the river.

Sample Input

1 2 5 10

Sample Output

Source

POJ Monthly--2004.07.18

题目类型：贪心

算法分析：如果n比较小则会比较容易得到答案，如果n比较大则对于每一次递推都需要判断两种方案中哪一个更优，其中一种方案是最快的来回运送最慢的，另一种方案是最快的和次快的一起过河，然后最快的回来。然后最慢的和次慢的一起过河，次快的回来

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1000000000 + 7;

const int maxn = 1000 + 666;

int ans[maxn], dp[maxn];

int main()
{
//    ifstream cin ("aaa.txt");
    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n;i++)
            cin >> ans[i];

        sort (ans, ans + n);

        dp[0] = ans[0], dp[1] = ans[1];

        int minvala, minvalb;
        for (int i = 2; i < n; i++)
        {
            minvala = dp[i-1] + ans[0] + ans[i];
            minvalb = dp[i-2] + ans[0] + 2 * ans[1] + ans[i];
            dp[i] = min (minvala, minvalb);
        }

        cout <<  dp[n-1] << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1000000000 + 7;

const int maxn = 1000 + 666;

int ans[maxn], dp[maxn];

int main()

{

// ifstream cin ("aaa.txt");

int t;

cin >> t;

while (t--)

{

int n;

cin >> n;

for (int i = 0; i < n;i++)

cin >> ans[i];

sort (ans, ans + n);

dp[0] = ans[0], dp[1] = ans[1];

int minvala, minvalb;

for (int i = 2; i < n; i++)

{

minvala = dp[i-1] + ans[0] + ans[i];

minvalb = dp[i-2] + ans[0] + 2 * ans[1] + ans[i];

dp[i] = min (minvala, minvalb);

}

cout << dp[n-1] << endl;

}

return 0;

}

poj1679

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

15 9月 2015

The Unique MST

Given a connected undirected graph, tell if its minimum spanning tree is unique. 阅读全文 »

poj1659

maksyuki 发表于 oj 分类，标签: 图论-Havel-Hakimi算法

15 9月 2015

Frogs' Neighborhood

未名湖附近共有N个大小湖泊L₁, L₂, ..., L_n(其中包括未名湖)，每个湖泊L_i里住着一只青蛙F_i(1 ≤ i ≤ N)。如果湖泊L_i和L_j之间有水路相连，则青蛙F_i和F_j互称为邻居。现在已知每只青蛙的邻居数目x₁, x₂, ..., x_n，请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，阅读全文 »

poj1651

maksyuki 发表于 oj 分类，标签: DP-区间DP

15 9月 2015

Multiplication Puzzle

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row. The goal is to take cards in such order as to minimize the total number of scored points. For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring 10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000 If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be 1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

Input

The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.

Output

Output must contain a single integer - the minimal score.

Sample Input

10 1 50 50 20 5

Sample Output

3650

Source

Northeastern Europe 2001, Far-Eastern Subregion

题目类型：区间DP

算法分析：使用dp[i][j]表示区间(i,j)之间的数被拿去所具有的最小乘积值，边界条件是dp[i][i+1] = 0, dp[i][i+2] = a[i] * a[i+1]*a[i+2]，转移方程为dp[i][j] = min (dp[i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]) i < k < j，最后输出dp[1][n]即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define i64 long long

const int INF = 0x7FFFFFFF - 6;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 200 + 13;

int a[maxn], dp[maxn][maxn];

int main()
{
//    CPPFF;

    int n;
    while (cin >> n)
    {
        for (int i = 1; i <= n; i++)
            cin >> a[i];

        for (int i = 1; i <= n - 1; i++)
            dp[i][i+1] = 0;

        for(int i = 1; i <= n - 2; i++)
            dp[i][i+2] = a[i] * a[i+1] * a[i+2];

        for (int l = 2; l <= n; l++)
        {
            for (int i = 1; i + l <= n; i++)
            {
                int j = i + l;
                dp[i][j] = INF;
                for (int k = i + 1; k < j; k++)
                    dp[i][j] = min (dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
            }
        }

        cout << dp[1][n] << endl;
    }

    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define i64 long long

const int INF = 0x7FFFFFFF - 6;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 200 + 13;

int a[maxn], dp[maxn][maxn];

int main()

{

// CPPFF;

int n;

while (cin >> n)

{

for (int i = 1; i <= n; i++)

cin >> a[i];

for (int i = 1; i <= n - 1; i++)

dp[i][i+1] = 0;

for(int i = 1; i <= n - 2; i++)

dp[i][i+2] = a[i] * a[i+1] * a[i+2];

for (int l = 2; l <= n; l++)

{

for (int i = 1; i + l <= n; i++)

{

int j = i + l;

dp[i][j] = INF;

for (int k = i + 1; k < j; k++)

dp[i][j] = min (dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);

}

cout << dp[1][n] << endl;

}

return 0;

}

poj1617

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

15 9月 2015

Crypto Columns

The columnar encryption scheme scrambles the letters in a message (or plaintext) using a keyword as illustrated in the following example: Suppose BATBOY is the keyword and our message is MEET ME BY THE OLD OAK TREE. Since the keyword has 6 letters, we write the message (ignoring spacing and punctuation) in a grid with 6 columns, padding with random extra letters as needed:

MEETME
BYTHEO
LDOAKT
REENTH
Here, we've padded the message with NTH. Now the message is printed out by columns, but the columns are printed in the order determined by the letters in the keyword. Since A is the letter of the keyword that comes first in the alphabet, column 2 is printed first. The next letter, B, occurs twice. In the case of a tie like this we print the columns leftmost first, so we print column 1, then column 4. This continues, printing the remaining columns in order 5, 3 and finally 6. So, the order the columns of the grid are printed would be 2, 1, 4, 5, 3, 6, in this case. This output is called the ciphertext, which in this example would be EYDEMBLRTHANMEKTETOEEOTH. Your job will be to recover the plaintext when given the keyword and the ciphertext.

Input

There will be multiple input sets. Each set will be 2 input lines. The first input line will hold the keyword, which will be no longer than 10 characters and will consist of all uppercase letters. The second line will be the ciphertext, which will be no longer than 100 characters and will consist of all uppercase letters. The keyword THEEND indicates end of input, in which case there will be no ciphertext to follow.

Output

For each input set, output one line that contains the plaintext (with any characters that were added for padding). This line should contain no spacing and should be all uppercase letters.

Sample Input

BATBOY

EYDEMBLRTHANMEKTETOEEOTH

HUMDING

EIAAHEBXOIFWEHRXONNAALRSUMNREDEXCTLFTVEXPEDARTAXNAA

RYIEX

THEEND

Sample Output

MEETMEBYTHEOLDOAKTREENTH

ONCEUPONATIMEINALANDFARFARAWAYTHERELIVEDTHREEBEARSX

XXXXX

Source

East Central North America 2003

题目类型：模拟

算法分析：对于按照字典序遍历的每一个大写字母，遍历关键字串的每一个字符，若找到相同的字符则将关键字串的相应大小的字符以列优先加入到二维数组maps的指定列中。依次类推，最后按照行优先输出maps中的每一个字符

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int maxn1 = 16;
const int maxn2 = 106;

char key[maxn1], cip[maxn2];
char maps[maxn1][maxn2];

int main()
{
	//ifstream cin ("aaa.txt");

    while (cin >> key)
	{
		if (!strcmp (key, "THEEND"))
            break;

        cin >> cip;
        int lenkey = strlen (key), lencip = strlen (cip), col = lencip / lenkey;

        char i;
        int j, p = 0;
        for (i = 'A'; i <= 'Z'; i++)
		{

			for (j = 0; j < lenkey; j++)
			{
				if (key[j] == i)
				{
                     int k;
                     for (k = 0; k < col; k++)
                        maps[k][j] = cip[p*col+k];

					  p++;//important!!!
				}
			}
		}

		for (i = 0; i < col; i++)
			for (j = 0; j < lenkey; j++)
			    printf ("%c", maps[i][j]);

		printf ("\n");
	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn1 = 16;

const int maxn2 = 106;

char key[maxn1], cip[maxn2];

char maps[maxn1][maxn2];

int main()

{

//ifstream cin ("aaa.txt");

while (cin >> key)

{

if (!strcmp (key, "THEEND"))

break;

cin >> cip;

int lenkey = strlen (key), lencip = strlen (cip), col = lencip / lenkey;

char i;

int j, p = 0;

for (i = 'A'; i <= 'Z'; i++)

{

for (j = 0; j < lenkey; j++)

{

if (key[j] == i)

{

int k;

for (k = 0; k < col; k++)

maps[k][j] = cip[p*col+k];

p++;//important!!!

}

for (i = 0; i < col; i++)

for (j = 0; j < lenkey; j++)

printf ("%c", maps[i][j]);

printf ("\n");

}

return 0;

}

poj1603

maksyuki 发表于 oj 分类，标签: 图论-最短路

15 9月 2015

Risk

Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world map broken up into hypothetical countries. During a player's turn, armies stationed in one country are only allowed to attack only countries with which they share a common border. Upon conquest of that country, the armies may move into the newly conquered country. During the course of play, a player often engages in a sequence of conquests with the goal of transferring a large mass of armies from some starting country to a destination country. Typically, one chooses the intervening countries so as to minimize the total number of countries that need to be conquered. Given a description of the gameboard with 20 countries each with between 1 and 19 connections to other countries, your task is to write a function that takes a starting country and a destination country and computes the minimum number of countries that must be conquered to reach the destination. You do not need to output the sequence of countries, just the number of countries to be conquered including the destination. For example, if starting and destination countries are neighbors, then your program should return one.

The following connection diagram illustrates the first sample input.

Input

Input to your program will consist of a series of country configuration test sets. Each test set will consist of a board description on lines 1 through 19. The representation avoids listing every national boundary twice by only listing the fact that country I borders country J when I < J. Thus, the Ith line, where I is less than 20, contains an integer X indicating how many "higher-numbered" countries share borders with country I, then X distinct integers J greater than I and not exceeding 20, each describing a boundary between countries I and J. Line 20 of the test set contains a single integer (1 <= N <= 100) indicating the number of country pairs that follow. The next N lines each contain exactly two integers (1 <= A,B <= 20; A!=B) indicating the starting and ending countries for a possible conquest.

There can be multiple test sets in the input file; your program should continue reading and processing until reaching the end of file. There will be at least one path between any two given countries in every country configuration.

Output

For each input set, your program should print the following message "Test Set #T" where T is the number of the test set starting with 1. The next NT lines each will contain the result for the corresponding test in the test set - that is, the minimum number of countries to conquer. The test result line should contain the start country code A the string " to " the destination country code B ; the string ": " and a single integer indicating the minimum number of moves required to traverse from country A to country B in the test set. Following all result lines of each input set, your program should print a single blank line.

Sample Input

1 3

2 3 4

3 4 5 6

1 6

1 7

2 12 13

1 8

2 9 10

1 11

2 12 17

1 14

2 14 15

2 15 16

1 16

1 19

2 18 19

1 20

2 9

19 5

18 19

16 20

Sample Output

Test Set #1

1 to 20: 7

2 to 9: 5

19 to 5: 6

18 to 19: 2

16 to 20: 2

Source

South Central USA 1997

题目类型：全源最短路(Floyd)

算法分析：直接将读入的数据建成一个无向图，每个边的权值为1，然后调用一次Floyd算法计算全源最短路，然后对于每一个查询，直接输出edge数组中相应的值即可。本题中要求的征服城市的数量(包括目标城市)其实等于求路径中边的数量，也就是求边权为1的最短路，当然本题也可以使用BFS求解，只不过对于每一个查询都要调用一次BFS

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 66;
const int INF = 0x7FFFFFFF;

long long edge[maxn][maxn];

void floyd ()
{
    int i, j, k;
    for (k = 1; k <= 20; k++)
    {
        for (i = 1; i <= 20; i++)
        {
            for (j = 1; j <= 20; j++)
                edge[i][j] = min (edge[i][j], edge[i][k] + edge[k][j]);
        }
    }
}


int main()
{
//    ifstream cin ("aaa.txt");

    int num, val, flag = 1;

    while (cin >> num)
    {
        int i, j;
        for (i = 1; i <= 20; i++)
        {
            for (j = 1; j <= 20; j++)
            {
                if (i == j)
                    edge[i][j] = 0;

                else
                    edge[i][j] = INF;
            }
        }

        for (i = 0; i < num; i++)
        {
            cin >> val;
            edge[1][val] = edge[val][1] = 1;
        }

        for (i = 2; i <= 19; i++)
        {
            cin >> num;
            int j;
            for (j = 0; j < num; j++)
            {
                cin >> val;
                edge[i][val] = edge[val][i] = 1;
            }
        }

        floyd ();

        cout << "Test Set #" << flag++ << endl;
        int q;
        cin >> q;
        for (i = 0; i < q; i++)
        {
            int s, e;
            cin >> s >> e;
            cout << s << " to " << e << ": " << edge[s][e] << endl;
        }
        cout << endl;
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 66;

const int INF = 0x7FFFFFFF;

long long edge[maxn][maxn];

void floyd ()

{

int i, j, k;

for (k = 1; k <= 20; k++)

{

for (i = 1; i <= 20; i++)

{

for (j = 1; j <= 20; j++)

edge[i][j] = min (edge[i][j], edge[i][k] + edge[k][j]);

}

int main()

{

// ifstream cin ("aaa.txt");

int num, val, flag = 1;

while (cin >> num)

{

int i, j;

for (i = 1; i <= 20; i++)

{

for (j = 1; j <= 20; j++)

{

if (i == j)

edge[i][j] = 0;

else

edge[i][j] = INF;

}

for (i = 0; i < num; i++)

{

cin >> val;

edge[1][val] = edge[val][1] = 1;

}

for (i = 2; i <= 19; i++)

{

cin >> num;

int j;

for (j = 0; j < num; j++)

{

cin >> val;

edge[i][val] = edge[val][i] = 1;

}

floyd ();

cout << "Test Set #" << flag++ << endl;

int q;

cin >> q;

for (i = 0; i < q; i++)

{

int s, e;

cin >> s >> e;

cout << s << " to " << e << ": " << edge[s][e] << endl;

}

cout << endl;

}

return 0;

}

poj1573

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

15 9月 2015

Robot Motion

A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are 阅读全文 »

poj1562

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

15 9月 2015

Oil Deposits

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input

The input contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or @', representing an oil pocket.

Output

are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input

1 1

3 5

*@*@*

**@**

*@*@*

1 8

@@****@*

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

0 0

Sample Output

Source

Mid-Central USA 1997

题目类型：DFS/BFS

算法分析：直接统计调用DFS/BFS的次数即可

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int maxn = 110 + 36;

const int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};

char ans[maxn][maxn];
bool visited[maxn][maxn];
int row, col;

inline bool OkMove (int x, int y)
{
	if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && ans[x][y] == '@' && !visited[x][y])
		return true;

return false;
}


void DFS (int x, int y)
{
	int i;
	for (i = 0; i < 8; i++)
	{
		if (OkMove (x + dx[i], y + dy[i]))
		{
			visited[x+dx[i]][y+dy[i]] = true;
			DFS (x + dx[i], y + dy[i]);
		}
	}
}


int main()
{
//	ifstream cin ("aaa.txt");

	

	while (cin >> row >> col)
	{
		if (row == 0 && col == 0)
			break;

		int i;
		for (i = 0; i < row; i++)
			cin >> ans[i];
		
		int sum = 0, j;
		memset (visited, false, sizeof (visited));

		for (i = 0; i < row; i++)
			for (j = 0; j < col; j++)
			{
				if (!visited[i][j] && ans[i][j] == '@')
				{
					DFS (i, j);
					sum++;
				}
			}

		cout << sum << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 110 + 36;

const int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};

char ans[maxn][maxn];

bool visited[maxn][maxn];

int row, col;

inline bool OkMove (int x, int y)

{

if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && ans[x][y] == '@' && !visited[x][y])

return true;

return false;

}

void DFS (int x, int y)

{

int i;

for (i = 0; i < 8; i++)

{

if (OkMove (x + dx[i], y + dy[i]))

{

visited[x+dx[i]][y+dy[i]] = true;

DFS (x + dx[i], y + dy[i]);

}

int main()

{

// ifstream cin ("aaa.txt");

while (cin >> row >> col)

{

if (row == 0 && col == 0)

break;

int i;

for (i = 0; i < row; i++)

cin >> ans[i];

int sum = 0, j;

memset (visited, false, sizeof (visited));

for (i = 0; i < row; i++)

for (j = 0; j < col; j++)

{

if (!visited[i][j] && ans[i][j] == '@')

{

DFS (i, j);

sum++;

}

cout << sum << endl;

}

return 0;

}

poj1555

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

15 9月 2015

Polynomial Showdown

Given the coefficients of a polynomial from degree 8 down to 0, you are to format the polynomial in a readable format with unnecessary characters removed. For instance, given the coefficients 0, 0, 0, 1, 22, -333, 0, 1, and -1, you should generate an output line which displays x^5 + 22x^4 - 333x^3 + x - 1.
The formatting rules which must be adhered to are as follows:

1. Terms must appear in decreasing order of degree.

2. Exponents should appear after a caret `"^".

3. The constant term appears as only the constant.

4. Only terms with nonzero coefficients should appear, unless all terms have zero coefficients in which case the constant term should appear.

5. The only spaces should be a single space on either side of the binary + and - operators.

6. If the leading term is positive then no sign should precede it; a negative leading term should be preceded by a minus sign, as in -7x^2 + 30x + 66.

7. Negated terms should appear as a subtracted unnegated term (with the exception of a negative leading term which should appear as described above). That is, rather than x^2 + -3x, the output should be x^2 - 3x.

8. The constants 1 and -1 should appear only as the constant term. That is, rather than -1x^3 + 1x^2 + 3x^1 - 1, the output should appear as-x^3 + x^2 + 3x - 1.

Input

The input will contain one or more lines of coefficients delimited by one or more spaces. There are nine coefficients per line, each coefficient being an integer with a magnitude of less than 1000.

Output

The output should contain the formatted polynomials, one per line.

Sample Input

0 0 0 1 22 -333 0 1 -1

0 0 0 0 0 0 -55 5 0

Sample Output

x^5 + 22x^4 - 333x^3 + x - 1

-55x^2 + 5x

Source

Mid-Central USA 1996

题目类型：模拟

算法分析：按照多项式加法的过程模拟即可

#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;
#define n 9

inline int fabs (int k)
{
	return k < 0 ? -k : k;
}

int main()
{
	int a[n], i;

	while (cin >> a[0])
	{
		for (i = 1; i < n; i++)
			cin >> a[i];

		bool first = true;

		for (i = 0; i < n; i++)
			if (a[i])
			{
				if (first)
				{
					if (a[i] == -1 && i < n - 1)
						cout << '-';

					else if (a[i] != 1 || i == n - 1)
						cout << a[i];

					if (i == n - 2)
						cout << 'x';

					else if (i < n - 1)
						cout << "x^" << n - i - 1;

					first = false;
				}

				else
				{
					cout << ' ' << (a[i] < 0 ? '-' : '+') << ' ';

					if (fabs (a[i]) != 1 || i == n - 1)
						cout << fabs (a[i]);

					if (i == n - 2)
						cout << 'x';

					else if (i < n - 1)
						cout << "x^" << n - i - 1;
				}
			}
			if (first)
				cout << 0;

			cout << endl;
	}
	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

using namespace std;

#define n 9

inline int fabs (int k)

{

return k < 0 ? -k : k;

}

int main()

{

int a[n], i;

while (cin >> a[0])

{

for (i = 1; i < n; i++)

cin >> a[i];

bool first = true;

for (i = 0; i < n; i++)

if (a[i])

{

if (first)

{

if (a[i] == -1 && i < n - 1)

cout << '-';

else if (a[i] != 1 || i == n - 1)

cout << a[i];

if (i == n - 2)

cout << 'x';

else if (i < n - 1)

cout << "x^" << n - i - 1;

first = false;

}

else

{

cout << ' ' << (a[i] < 0 ? '-' : '+') << ' ';

if (fabs (a[i]) != 1 || i == n - 1)

cout << fabs (a[i]);

if (i == n - 2)

cout << 'x';

else if (i < n - 1)

cout << "x^" << n - i - 1;

}

if (first)

cout << 0;

cout << endl;

}

return 0;

}

poj1546

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

15 9月 2015

Basically Speaking

The Really Neato Calculator Company, Inc. has recently hired your team to help design their Super Neato Model I calculator. As a computer scientist you suggested to the company that it would be neato if this new calculator could convert among number bases. The company thought this was a stupendous idea and has asked your team to come up with the prototype program for doing base conversion. The project manager of the Super Neato Model I calculator has informed you that the calculator will have the following neato features:

It will have a 7-digital display.
Its buttons will include the capital letters A through F in addition to the digits 0 through 9.
It will support bases 2 through 16.

Input

The input for your prototype program will consist of one base conversion per line. There will be three numbers per line. The first number will be the number in the base you are converting from. The second number is the base you are converting from. The third number is the base you are converting to. There will be one or more blanks surrounding (on either side of) the numbers. There are several lines of input and your program should continue to read until the end of file is reached.

Output

The output will only be the converted number as it would appear on the display of the calculator. The number should be right justified in the 7-digit display. If the number is to large to appear on the display, then print ERROR'' (without the quotes) right justified in the display.

Sample Input

1111000 2 10

1111000 2 16

2102101 3 10

2102101 3 15

12312 4 2

1A 15 2

1234567 10 16

ABCD 16 15

Sample Output

120

1765

7CA

ERROR

11001

12D687

D071

Source

Mid-Central USA 1995

题目类型：简单进制转换

算法分析：直接进行任意进制之间的转换即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;

const int maxn = 166;

int ans[maxn], len;
char input[maxn];

int TransOld (char *val, int base)
{
	int i, sum = 0, wei = 1, len = strlen (val);
	for (i = len - 1; i >= 0; i--)
	{
		if (val[i] >= 'A' && val[i] <= 'Z')
			sum += (val[i] - 'A' + 10) * wei;

		else
			sum += (val[i] - '0') * wei;

		wei *= base;
	}

return sum;
}

void Trans (int val, int base)
{
    len = 0;
    do
    {
        ans[len++] = val % base;
        val /= base;
    } while (val);
}

int main()
{
//    ifstream cin ("aaa.txt");

    int oldbase, newbase;
    while (cin >> input >> oldbase >> newbase)
    {
        int temp = TransOld (input, oldbase);
        Trans (temp, newbase);

        if (len > 7)
        {
            cout << "  ERROR" << endl;
            continue;
        }

        int i;
        for (i = 1; i <= 7 - len; i++)
            cout << " ";

        for (i = len - 1; i >= 0; i--)
        {
            if (ans[i] > 9)
                cout << char (ans[i] - 10 + 'A');

            else
                cout << ans[i];
        }
        cout << endl;
    }

return 0;
}

100

101

102

103

104

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 166;

int ans[maxn], len;

char input[maxn];

int TransOld (char *val, int base)

{

int i, sum = 0, wei = 1, len = strlen (val);

for (i = len - 1; i >= 0; i--)

{

if (val[i] >= 'A' && val[i] <= 'Z')

sum += (val[i] - 'A' + 10) * wei;

else

sum += (val[i] - '0') * wei;

wei *= base;

}

return sum;

}

void Trans (int val, int base)

{

len = 0;

{

ans[len++] = val % base;

val /= base;

} while (val);

}

int main()

{

// ifstream cin ("aaa.txt");

int oldbase, newbase;

while (cin >> input >> oldbase >> newbase)

{

int temp = TransOld (input, oldbase);

Trans (temp, newbase);

if (len > 7)

{

cout << " ERROR" << endl;

continue;

}

int i;

for (i = 1; i <= 7 - len; i++)

cout << " ";

for (i = len - 1; i >= 0; i--)

{

if (ans[i] > 9)

cout << char (ans[i] - 10 + 'A');

else

cout << ans[i];

}

cout << endl;

}

return 0;

}

poj1528

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

15 9月 2015

Perfection

From the article Number Theory in the 1994 Microsoft Encarta: If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not 1/-1, b is called a proper divisor of a. Even integers, which include 0, are multiples of 2, for example, -4, 0, 2, 10; an odd integer is an integer that is not even, for example, -5, 1, 3, 9. A perfect number is a positive integer that is equal to the sum of all its positive, proper divisors; for example, 6, which equals 1 + 2 + 3, and 28, which equals 1 + 2 + 4 + 7 + 14, are perfect numbers. A positive number that is not perfect is imperfect and is deficient or abundant according to whether the sum of its positive, proper divisors is smaller or larger than the number itself. Thus, 9, with proper divisors 1, 3, is deficient; 12, with proper divisors 1, 2, 3, 4, 6, is abundant."
Given a number, determine if it is perfect, abundant, or deficient.

Input

A list of N positive integers (none greater than 60,000), with 1 <= N < 100. A 0 will mark the end of the list.

Output

The first line of output should read PERFECTION OUTPUT. The next N lines of output should list for each input integer whether it is perfect, deficient, or abundant, as shown in the example below. Format counts: the echoed integers should be right justified within the first 5 spaces of the output line, followed by two blank spaces, followed by the description of the integer. The final line of output should read END OF OUTPUT.

Sample Input

15 28 6 56 60000 22 496 0

Sample Output

PERFECTION OUTPUT

15 DEFICIENT

28 PERFECT

6 PERFECT

56 ABUNDANT

60000 ABUNDANT

22 DEFICIENT

496 PERFECT

END OF OUTPUT

Source

Mid-Atlantic 1996

题目类型：模拟

算法分析：直接按照题目对于完美数的定义直接求出完美因子的的和，将其与待测试数进行比较即可。注意输出的格式

#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;

int perfect (int val)
{
    int i, sum = 0;
    for (i = 2; i <= val; i++)
         if (val % i == 0)
             sum += val / i;

	return sum;
}
int main()
{
    int val;
    //ifstream cin ("aaa.txt");
	printf ("PERFECTION OUTPUT\n");

    while (cin >> val)
	{
		if (val == 0)
			break;

		int ans = perfect (val);
		printf ("%5d", val);

        if (ans == val)
            printf ("  PERFECT\n");

		else if (ans < val)
			printf ("  DEFICIENT\n");

		else
			printf ("  ABUNDANT\n");
	}
	printf ("END OF OUTPUT\n");
	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

using namespace std;

int perfect (int val)

{

int i, sum = 0;

for (i = 2; i <= val; i++)

if (val % i == 0)

sum += val / i;

return sum;

}

int main()

{

int val;

//ifstream cin ("aaa.txt");

printf ("PERFECTION OUTPUT\n");

while (cin >> val)

{

if (val == 0)

break;

int ans = perfect (val);

printf ("%5d", val);

if (ans == val)

printf (" PERFECT\n");

else if (ans < val)

printf (" DEFICIENT\n");

else

printf (" ABUNDANT\n");

}

printf ("END OF OUTPUT\n");

return 0;

}

poj1523

maksyuki 发表于 oj 分类，标签: 图论-求解割点\割边(Tarjan)

15 9月 2015

SPF

Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, 3, in the network 阅读全文 »

poj1511

maksyuki 发表于 oj 分类，标签: 图论-最短路

15 9月 2015

Invitation Cards

In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. 阅读全文 »

返回首页上一页 4 5 6 7 8 下一页最后一页

超客的水墨烟雨

poj1751

poj1738

poj1703

poj1700

poj1679

poj1659

poj1651

poj1617

poj1603

poj1573

poj1562

poj1555

poj1546

poj1528

poj1523

poj1511

分类目录

标签云

书签

近期评论

2015年9月
一	二	三	四	五	六	日
« 8月				10月 »
	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