dd's site \#

Posted on In ,

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.

The input file 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 \le m \le 100$ and $1 \le n \le 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.

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

1 1 /* 3 5 /@/@/* //@// /@/@/* 1 8 @@////@/* 5 5 ////@ /@@/@ /@//@ @@@/@ @@//@ 0 0

0 1 2 2

题意 计算@连通块的数量 典型的dfs应用

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
#include<cstdio>
#include<cstring>
using namespace std;
#define r i+x[k]
#define c j+y[k]
const int N = 105;
char mat[N][N];
int n, x[8] = { -1, -1, -1, 0, 0, 1, 1, 1};
int m, y[8] = { -1, 0, 1, -1, 1, -1, 0, 1};

int dfs (int i, int j)
{
    if (mat[i][j] == '*') return 0;
    mat[i][j] = '*';
    for (int k = 0; k < 8; ++k)
        if (r > 0 && r <= n && c > 0 && c <= m && mat[r][c] == '@')
            dfs (r, c);
    return 1;
}

int main()
{
    while (scanf ("%d%d", &n, &m), n)
    {
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            scanf ("%s", mat[i] + 1);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                ans += dfs (i, j);
        printf ("%d\n", ans);
    }
    return 0;
}

Posted on In ,

题意 求条形图中最大矩形的面积 输入给你条的个数 每个条的高度hi （以下等于也视为高）

只要知道第i个条左边连续多少个（a）比他高 右边连续多少个（b）比他高 那么以这个条为最大高度的面积就是hi/*(a+b+1);

但是直接枚举每一个的话肯定会超时的 超时代码

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
#include<cstdio>
using namespace std;
const int N = 100005;
typedef long long ll;
ll h[N]; int n,wide[N];
int main()
{
    while (scanf ("%d", &n), n)
    {
        for (int i = 1; i <= n; ++i)
            scanf ("%I64d", &h[i]);
        for (int i = 1; i <= n; ++i)
        {
            wide[i] = 1;
            int k = i;
            while (k > 1 && h[--k] >= h[i]) ++wide[i];
            k = i;
            while (k < n && h[++k] >= h[i]) ++wide[i];
        }
        ll ans = 0;
        for (int i = 1; i <= n; ++i)
            if (h[i]*wide[i] > ans) ans = h[i] * wide[i];
        printf ("%I64d\n", ans);
    }
    return 0;
}

可以发现 当第i-1个比第i个高的时候 比第i-1个高的所有也一定比第i个高

于是可以用到动态规划的思想

令left[i]表示包括i在内比i高的连续序列中最左边一个的下标 right[i]为最右边一个的下标

那么有 当**h[left[i]-1]>=h[i]]时left[i]=left[left[i]-1]**从前往后可以递推出left[i]

同理 当**h[right[i]+1]>=h[i]]时right[i]=right[right[i]+1]**从后往前可递推出righ[i]

最后答案就等于**max{(right[i]-left[i]+1)/*h[i]}**了

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
#include<cstdio>
using namespace std;
const int N = 100005;
typedef long long ll;
ll h[N];
int n, left[N], right[N];
int main()
{
    while (scanf ("%d", &n), n)
    {
        for (int i = 1; i <= n; ++i)
            scanf ("%I64d", &h[i]), left[i] = right[i] = i;


        h[0] = h[n + 1] = -1;
        for (int i = 1; i <= n; ++i)      //求left[i]
            while (h[left[i] - 1] >= h[i])
                left[i] = left[left[i] - 1];


        for (int i = n; i >= 1; --i)      //求right[i]
            while (h[right[i] + 1] >= h[i])
                right[i] = right[right[i] + 1];


        ll ans = 0;
        for (int i = 1; i <= n; ++i)
            if (h[i] * (right[i] - left[i] + 1) > ans) ans = h[i] * ll (right[i] - left[i] + 1);
        printf ("%I64d\n", ans);
    }
    return 0;
}

然后还有单调栈写法 比DP操作起来更容易

通过单调栈可以在 O(n) 时间内找到数组中在 h[i] 左边(右边)离 h[i] 最近的大于 h[i] 那个数(或者下标) 这里是取下标 知道 h[i] 左边最近和右边最近的高度小于 h[i] 的两个下标后 那么就知道以这个矩形高度为基准的大矩形的面积了

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
ll h[N], s[N], le[N], ri[N];

int main()
{
    int n, top;
    while(scanf("%d", &n), n)
    {
        for(int i = 1; i <= n; ++i)
            scanf("%I64d", &h[i]);

        top = 0, s[0] = 0;   //le[i]保存i左边第一个小于h[i]的下标
        for(int i = 1; i <= n; ++i)
        {
            while(top && h[s[top]] >= h[i]) --top;
            le[i] = s[top];
            s[++top] = i;
        }

        top = 0, s[0] = n + 1;  //ri[i]保存i右边最后一个大于等于h[i]的下标
        for(int i = n; i > 0; --i)
        {
            while(top && h[s[top]] >= h[i]) --top;
            ri[i] = s[top] - 1;
            s[++top] = i;
        }

        ll ans = h[1];
        for(int i = 1; i <= n; ++i)
            if(h[i] * (ri[i] - le[i]) > ans)
                ans =  h[i] * (ri[i] - le[i]);
        printf("%I64d\n", ans);
    }
    return 0;
}

Largest Rectangle in a Histogram

Problem Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, …, hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
Sample Input

7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
Sample Output

8 4000

Posted on In ,

1506的升级版 只是多了一维 h要自己算 详情看上一篇

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int mat[N][N], le[N][N], ri[N][N], h[N][N], cas, n, m;
int main()
{
    char s[5];
    scanf ("%d", &cas);
    while (cas--)
    {
        memset (mat, 0, sizeof (mat));
        memset (h, 0, sizeof (h));
        scanf ("%d%d", &n, &m);

        for (int i = 1; i <= n; ++i)
        {
            h[i][0] = h[i][m + 1] = -1;
            for (int j = 1; j <= m; ++j)
            {
                scanf ("%s", s), mat[i][j] = s[0];
                le[i][j] = ri[i][j] = j;
                if (mat[i][j] == 'F') h[i][j] = h[i - 1][j] + 1;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = m; j >= 1; --j)
                while (h[i][ri[i][j] + 1] >= h[i][j])
                    ri[i][j] = ri[i][ri[i][j] + 1];

            for (int j = 1; j <= m; ++j)
            {
                while (h[i][le[i][j] - 1] >= h[i][j])
                    le[i][j] = le[i][le[i][j] - 1];
                ans = max (ans, (ri[i][j] - le[i][j] + 1) * h[i][j]);
            }
        }
        printf ("%d\n", ans * 3);
    }
    return 0;
}

City Game

Problem Description

Bob is a strategy game programming specialist. In his new city building game the gaming environment is as follows: a city is built up by areas, in which there are streets, trees,factories and buildings. There is still some space in the area that is unoccupied. The strategic task of his game is to win as much rent money from these free spaces. To win rent money you must erect buildings, that can only be rectangular, as long and wide as you can. Bob is trying to find a way to build the biggest possible building in each area. But he comes across some problems – he is not allowed to destroy already existing buildings, trees, factories and streets in the area he is building in.
Each area has its width and length. The area is divided into a grid of equal square units.The rent paid for each unit on which you’re building stands is 3$.
Your task is to help Bob solve this problem. The whole city is divided into K areas. Each one of the areas is rectangular and has a different grid size with its own length M and width N.The existing occupied units are marked with the symbol R. The unoccupied units are marked with the symbol F.
Input

The first line of the input contains an integer K – determining the number of datasets. Next lines contain the area descriptions. One description is defined in the following way: The first line contains two integers-area length M<=1000 and width N<=1000, separated by a blank space. The next M lines contain N symbols that mark the reserved or free grid units,separated by a blank space. The symbols used are:
R – reserved unit
F – free unit
In the end of each area description there is a separating line.
Output

For each data set in the input print on a separate line, on the standard output, the integer that represents the profit obtained by erecting the largest building in the area encoded by the data set.
Sample Input

2 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F 5 5 R R R R R R R R R R R R R R R R R R R R R R R R R
Sample Output

45 0

City Game

Problem Description

Bob is a strategy game programming specialist. In his new city building game the gaming environment is as follows: a city is built up by areas, in which there are streets, trees,factories and buildings. There is still some space in the area that is unoccupied. The strategic task of his game is to win as much rent money from these free spaces. To win rent money you must erect buildings, that can only be rectangular, as long and wide as you can. Bob is trying to find a way to build the biggest possible building in each area. But he comes across some problems – he is not allowed to destroy already existing buildings, trees, factories and streets in the area he is building in.
Each area has its width and length. The area is divided into a grid of equal square units.The rent paid for each unit on which you’re building stands is 3$.
Your task is to help Bob solve this problem. The whole city is divided into K areas. Each one of the areas is rectangular and has a different grid size with its own length M and width N.The existing occupied units are marked with the symbol R. The unoccupied units are marked with the symbol F.
Input

The first line of the input contains an integer K – determining the number of datasets. Next lines contain the area descriptions. One description is defined in the following way: The first line contains two integers-area length M<=1000 and width N<=1000, separated by a blank space. The next M lines contain N symbols that mark the reserved or free grid units,separated by a blank space. The symbols used are:
R – reserved unit
F – free unit
In the end of each area description there is a separating line.
Output

For each data set in the input print on a separate line, on the standard output, the integer that represents the profit obtained by erecting the largest building in the area encoded by the data set.
Sample Input

2 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F 5 5 R R R R R R R R R R R R R R R R R R R R R R R R R
Sample Output

45 0

Posted on In ,

Compromise

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6440 Accepted: 2882 Special Judge

Description
In a few months the European Currency Union will become a reality. However, to join the club, the Maastricht criteria must be fulfilled, and this is not a trivial task for the countries (maybe except for Luxembourg). To enforce that Germany will fulfill the criteria, our government has so many wonderful options (raise taxes, sell stocks, revalue the gold reserves,…) that it is really hard to choose what to do.
Therefore the German government requires a program for the following task:
Two politicians each enter their proposal of what to do. The computer then outputs the longest common subsequence of words that occurs in both proposals. As you can see, this is a totally fair compromise (after all, a common sequence of words is something what both people have in mind).
Your country needs this program, so your job is to write it for us.

Input

The input will contain several test cases.
Each test case consists of two texts. Each text is given as a sequence of lower-case words, separated by whitespace, but with no punctuation. Words will be less than 30 characters long. Both texts will contain less than 100 words and will be terminated by a line containing a single ‘/#’.
Input is terminated by end of file.

Output

For each test case, print the longest common subsequence of words occuring in the two texts. If there is more than one such sequence, any one is acceptable. Separate the words by one blank. After the last word, output a newline character.

Sample Input

die einkommen der landwirte sind fuer die abgeordneten ein buch mit sieben siegeln um dem abzuhelfen muessen dringend alle subventionsgesetze verbessert werden /# die steuern auf vermoegen und einkommen sollten nach meinung der abgeordneten nachdruecklich erhoben werden dazu muessen die kontrollbefugnisse der finanzbehoerden dringend verbessert werden /#

Sample Output

die einkommen der abgeordneten muessen dringend verbessert werden

题意 求两端文本的最长公共子单词序列 直接lcs增量法可以得出 打印路劲也是直接递归就行

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
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 105, L = 35;
char a[N][L], b[N][L];
int pre[N][N], d[N][N], n, m, la, lb, flag;
void lcs()
{
    memset (d, 0, sizeof (d)); memset (pre, 0, sizeof (pre));
    for (int i = 1; i < la; ++i)
        for (int j = 1; j < lb; ++j)
            if (!strcmp (a[i], b[j]))
            {
                d[i][j] = d[i - 1][j - 1] + 1;
                pre[i][j] = 1;
            }
            else if (d[i - 1][j] > d[i][j - 1])
            {
                d[i][j] = d[i - 1][j];
                pre[i][j] = 2;
            }
            else
            {
                d[i][j] = d[i][j - 1];
                pre[i][j] = 3;
            }
}

void print (int i, int j)
{
    if (pre[i][j] == 1)
    {
        print (i - 1, j - 1);
        if (flag) flag = 0;
        else printf (" ");
        printf ("%s", a[i]);
    }
    else if (pre[i][j] == 2)
        print (i - 1, j);
    else if (pre[i][j] == 3)
        print (i, j - 1);
}

int main()
{
    while (scanf ("%s", a[1]) != EOF)
    {
        la = 1; lb = 0; flag = 1;
        while (scanf ("%s", a[++la]), a[la][0] != '#');
        while (scanf ("%s", b[++lb]), b[lb][0] != '#');
        lcs();
        print (la - 1, lb - 1);
        printf ("\n");
    }
    return 0;
}

Posted on In ,

A Typical Homework(a.k.a Shi Xiong Bang Bang Mang)

Hi, I am an undergraduate student in institute of foreign languages. As you know, C programming is a required course in our university, even if his/her major is far from computer science. I don’t like this course at all, as I am not good at computer and I don’t wanna even have a try of any programming!! But I have to do the homework in order to pass :( Sh… Could you help me with it? Please keep secret!! I know that you won’t say NO to a poor little girl, boy. :)

Task

Write a Student Performance Management System (SPMS).

Concepts

In the SPMS, there will be at most 100 students, each has an SID, a CID, a name and four scores (Chinese, Mathematics, English and Programming).

When you enter the SPMS, the main menu should be shown like this: Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit

Adding a Student

If you choose 1 from the main menu, the following message should be printed on the screen: Please enter the SID, CID, name and four scores. Enter 0 to finish. Then your program should wait for user input. The input lines are always valid (no invalid SID, CID, or name, exactly four scores etc), but the SID may already exist. In that case, simply ignore this line and print the following: Duplicated SID. On the other hand, multiple students can have the same name. You should keep printing the message above until the user inputs a single zero. After that the main menu is printed again.

Removing a Student

If you choose 2 from the main menu, the following message should be printed on the screen: Please enter SID or name. Enter 0 to finish. Then your program should wait for user input, and remove all the students matching the SID or name in the database, and print the following message (it’s possible xx=0): xx student(s) removed. You should keep printing the message above until the user inputs a single zero. After that the main menu is printed again.

Querying Students

If you choose 3 from the main menu, the following message should be printed on the screen: Please enter SID or name. Enter 0 to finish. Then your program should wait for user input. If no student matches the SID or name, simply do nothing, otherwise print out all the matching students, in the same order they’re added to the database. The format is similar to the input format for “adding a student”, but 3 more columns are added: rank (1st column), total score and average score (last two columns). The student with highest total score (considering all classes) received rank-1, and if there are two rank-2 students, the next one would be rank-4. You should keep printing the message above until the user inputs a single zero. After that the main menu is printed again.

Showing the Ranklist

If you choose 4 from the main menu, the following message should be printed on the screen: Showing the ranklist hurts students’ self-esteem. Don’t do that. Then the main menu is printed again.

Showing Statistics

If you choose 5 from the main menu, show the statistics, in the following format: Please enter class ID, 0 for the whole statistics. When a class ID is entered, print the following statistics. Note that “passed” means to have a score of at least 60. Chinese Average Score: xx.xx Number of passed students: xx Number of failed students: xx Mathematics Average Score: xx.xx Number of passed students: xx Number of failed students: xx English Average Score: xx.xx Number of passed students: xx Number of failed students: xx Programming Average Score: xx.xx Number of passed students: xx Number of failed students: xx Overall: Number of students who passed all subjects: xx Number of students who passed 3 or more subjects: xx Number of students who passed 2 or more subjects: xx Number of students who passed 1 or more subjects: xx Number of students who failed all subjects: xx Then, the main menu is printed again.

Exiting SPMS

If you choose 0 from the main menu, the program should terminate. Note that course scores and total score should be formatted as integers, but average scores should be formatted as a real number with exactly two digits after the decimal point.

Input

There will be a single test case, ending with a zero entered in the main menu screen. The entire input will be valid. The size of input does not exceed 10KB.

Output

Print out everything as stated in the problem description. You should be able to play around this little program in your machine, with a keyboard and a screen. However, both the input and output may look silly when they’re not mixed, as in the keyboard-screen case.

Sample Input

1 0011223344 1 John 79 98 91 100 0022334455 1 Tom 59 72 60 81 0011223344 2 Alice 100 100 100 100 2423475629 2 John 60 80 30 99 0 3 0022334455 John 0 5 1 2 0011223344 0 5 0 4 0

Output for the Sample Input

Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit Please enter the SID, CID, name and four scores. Enter 0 to finish. Please enter the SID, CID, name and four scores. Enter 0 to finish. Please enter the SID, CID, name and four scores. Enter 0 to finish. Duplicated SID. Please enter the SID, CID, name and four scores. Enter 0 to finish. Please enter the SID, CID, name and four scores. Enter 0 to finish. Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit Please enter SID or name. Enter 0 to finish. 2 0022334455 1 Tom 59 72 60 81 272 68.00 Please enter SID or name. Enter 0 to finish. 1 0011223344 1 John 79 98 91 100 368 92.00 3 2423475629 2 John 60 80 30 99 269 67.25 Please enter SID or name. Enter 0 to finish. Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit Please enter class ID, 0 for the whole statistics. Chinese Average Score: 69.00 Number of passed students: 1 Number of failed students: 1 Mathematics Average Score: 85.00 Number of passed students: 2 Number of failed students: 0 English Average Score: 75.50 Number of passed students: 2 Number of failed students: 0 Programming Average Score: 90.50 Number of passed students: 2 Number of failed students: 0 Overall: Number of students who passed all subjects: 1 Number of students who passed 3 or more subjects: 2 Number of students who passed 2 or more subjects: 2 Number of students who passed 1 or more subjects: 2 Number of students who failed all subjects: 0 Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit Please enter SID or name. Enter 0 to finish. 1 student(s) removed. Please enter SID or name. Enter 0 to finish. Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit Please enter class ID, 0 for the whole statistics. Chinese Average Score: 59.50 Number of passed students: 1 Number of failed students: 1 Mathematics Average Score: 76.00 Number of passed students: 2 Number of failed students: 0 English Average Score: 45.00 Number of passed students: 1 Number of failed students: 1 Programming Average Score: 90.00 Number of passed students: 2 Number of failed students: 0 Overall: Number of students who passed all subjects: 0 Number of students who passed 3 or more subjects: 2 Number of students who passed 2 or more subjects: 2 Number of students who passed 1 or more subjects: 2 Number of students who failed all subjects: 0 Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit Showing the ranklist hurts students’ self-esteem. Don’t do that. Welcome to Student Performance Management System (SPMS). 1 - Add 2 - Remove 3 - Query 4 - Show ranking 5 - Show Statistics 0 - Exit Rujia Liu’s Present 5: Developing Simplified Softwares
Special Thanks: Youzhi Bao, Zhuohua Chen

这种题目出现在oj上感觉挺奇怪的 这不是当年C语言期末考试的题目吗 实在不知道我的代码哪里有问题 样例是一摸一样的

可能哪里格式错了吧 既然是个系统就不在乎那些了TT

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
using namespace std;
#define eps 1e-5
map<string, int> si;
int n;
struct Student
{
    string sid, name;
    int cid, chi, mat, eng, pro, sco;
    Student () {}
    Student (string s, int c, string na, int s1, int s2, int s3, int s4)
        : sid (s), cid (c), name (na), chi (s1), mat (s2), eng (s3), pro (s4)
    {
        sco = chi + mat + eng + pro;
    }
    void print()
    {
        cout << sid << " " << cid << " " << name;
        printf (" %d %d %d %d %d %.2lf\n", chi, mat, eng, pro, sco, sco / 4.0 + eps);
    }
} stu[100000];


void Add()
{
    string s, na;
    int c, s1, s2, s3, s4;
    printf ("Please enter the SID, CID, name and four scores. Enter 0 to finish.\n");
    while (cin >> s, s != "0")
    {
        cin >> c >> na >> s1 >> s2 >> s3 >> s4;
        if (si[s]) printf ("Duplicated SID.\n");
        else
        {
            si[s] = (++n);
            stu[n] = Student (s, c, na, s1, s2, s3, s4);
        }
        printf ("Please enter the SID, CID, name and four scores. Enter 0 to finish.\n");
    }
}


void Remove()
{
    string s;
    int t;
    printf ("Please enter SID or name. Enter 0 to finish.\n");
    while (cin >> s, s != "0")
    {
        t = 0;
        for (int i = 1; i <= n; ++i)
            if (si[stu[i].sid])
                if (stu[i].name == s || stu[i].sid == s)
                {
                    si[stu[i].sid] = 0;
                    ++t;
                }
        printf ("%d student(s) removed.\n", t);
        printf ("Please enter SID or name. Enter 0 to finish.\n");
    }
}

void Query()
{
    int t;
    string s;
    printf ("Please enter SID or name. Enter 0 to finish.\n");
    while (cin >> s, s != "0")
    {
        for (int i = t = 1; i <= n; ++i)
            if (si[stu[i].sid])
            {
                if (stu[i].sid == s || stu[i].name == s)
                {
                    printf ("%d ", t++);
                    stu[i].print();
                }
                else  ++t;
            }
        printf ("Please enter SID or name. Enter 0 to finish.\n");
    }
}


void Show_ranking()
{
    printf ("Showing the ranklist hurts students' self-esteem. Don't do that.\n");
}

void Show_Statistics()
{
    printf ("Please enter class ID, 0 for the whole statistics.\n");
    int schi = 0, seng = 0, smat = 0, spro = 0, pmat = 0, cla,
        pchi = 0, peng = 0, ppro = 0, npa = 0, np1 = 0, np2 = 0, np3 = 0, nfa = 0, numb;
    scanf ("%d", &cla);
    for (int i = 1; i <= n; ++i)
        if ( (stu[i].cid == cla || cla == 0) && si[stu[i].sid])
        {
            int t = 0;
            schi += stu[i].chi;
            if (stu[i].chi >= 60)
            {
                ++pchi;
                ++t;
            }
            seng += stu[i].eng;
            if (stu[i].eng >= 60)
            {
                ++peng;
                ++t;
            }
            spro += stu[i].pro;
            if (stu[i].pro >= 60)
            {
                ++ppro;
                ++t;
            }
            smat += stu[i].mat;
            if (stu[i].mat >= 60)
            {
                ++pmat;
                ++t;
            }
            if (t == 0) ++nfa;
            if (t == 1) ++np1;
            if (t == 2) ++np2;
            if (t == 3) ++np3;
            if (t == 4) ++npa;
        }
    numb = nfa + np1 + np2 + np3 + npa;
    printf ("Chinese\n");
    printf ("Average Score: %.2lf\n", schi / (numb * 1.0) + eps);
    printf ("Number of passed students: %d\n", pchi);
    printf ("Number of failed students: %d\n\n", numb - pchi);
    
    printf ("Mathematics\n");
    printf ("Average Score: %.2lf\n", smat / (numb * 1.0) + eps);
    printf ("Number of passed students: %d\n", pmat);
    printf ("Number of failed students: %d\n\n", numb - pmat);
    
    printf ("English\n");
    printf ("Average Score: %.2lf\n", seng / (numb * 1.0) + eps);
    printf ("Number of passed students: %d\n", peng);
    printf ("Number of failed students: %d\n\n", numb - peng);
    
    printf ("Programming\n");
    printf ("Average Score: %.2lf\n", spro / (numb * 1.0) + eps);
    printf ("Number of passed students: %d\n", ppro);
    printf ("Number of failed students: %d\n\n", numb - ppro);
    
    printf ("Overall:\n");
    printf ("Number of students who passed all subjects: %d\n", npa);
    printf ("Number of students who passed 3 or more subjects: %d\n", npa + np3);
    printf ("Number of students who passed 2 or more subjects: %d\n", npa + np3 + np2);
    printf ("Number of students who passed 1 or more subjects: %d\n", npa + np3 + np2 + np1);
    printf ("Number of students who failed all subjects: %d\n\n", nfa);
}


int main()
{
    int cho;
    n = 0;
    while (1)
    {
        printf ("Welcome to Student Performance Management System (SPMS).\n\n");
        printf ("1 - Add\n");
        printf ("2 - Remove\n");
        printf ("3 - Query\n");
        printf ("4 - Show ranking\n");
        printf ("5 - Show Statistics\n");
        printf ("0 - Exit\n\n");
        scanf ("%d", &cho);
        if (cho == 1) Add();
        if (cho == 2) Remove();
        if (cho == 3) Query();
        if (cho == 4) Show_ranking();
        if (cho == 5) Show_Statistics();
        if (cho == 0)  return 0;
    }
}

刘汝佳的代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// UVa12412 A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)
// Rujia Liu
#include<stdio.h>
#include<string.h>
#define maxn 1000
#define maxl 100
#define EPS 1e-5

int n = 0;
char sid[maxn][maxl];
int cid[maxn];
char name[maxn][maxl];
int score[maxn][5];
int removed[maxn];

const char* course_name[] = {"Chinese", "Mathematics", "English", "Programming"};

int valid (int k)
{
    for (int i = 0; i < k; i++) if (!removed[i])
        {
            if (strcmp (sid[i], sid[k]) == 0) return 0;
        }
    return 1;
}

void add()
{
    for (;;)
    {
        printf ("Please enter the SID, CID, name and four scores. Enter 0 to finish.\n");
        scanf ("%s", sid[n]);
        if (strcmp (sid[n], "0") == 0) break;
        scanf ("%d%s%d%d%d%d", &cid[n], name[n], &score[n][0], &score[n][1], &score[n][2], &score[n][3]);
        if (valid (n))
        {
            score[n][4] = score[n][0] + score[n][1] + score[n][2] + score[n][3];
            n++;
        }
        else printf ("Duplicated SID.\n");
    }
}

int rank (int k)
{
    int r = 0;
    for (int i = 0; i < n; i++)
        if (!removed[i] && score[i][4] > score[k][4]) r++;
    return r + 1;
}

void DQ (int isq)
{
    char s[maxl];
    for (;;)
    {
        printf ("Please enter SID or name. Enter 0 to finish.\n");
        scanf ("%s", s);
        if (strcmp (s, "0") == 0) break;
        int r = 0;
        for (int i = 0; i < n; i++) if (!removed[i])
            {
                if (strcmp (sid[i], s) == 0 || strcmp (name[i], s) == 0)
                {
                    if (isq) printf ("%d %s %d %s %d %d %d %d %d %.2f\n", rank (i), sid[i], cid[i], name[i], score[i][0], score[i][1], score[i][2], score[i][3], score[i][4], score[i][4] / 4.0 + EPS);
                    else
                    {
                        removed[i] = 1;
                        r++;
                    }
                }
            }
        if (!isq) printf ("%d student(s) removed.\n", r);
    }
}

double get_course_stat (int c, int s, int* passed, int* failed)
{
    int tot = 0;
    *passed = *failed = 0;
    for (int i = 0; i < n; i++)
        if (!removed[i] && (c == 0 || cid[i] == c))
        {
            tot += score[i][s];
            if (score[i][s] >= 60) (*passed)++;
            else (*failed)++;
        }
    return (double) tot / (double) (*passed + *failed);
}

void get_overall_stat (int c, int* cnt)
{
    cnt[0] = cnt[1] = cnt[2] = cnt[3] = cnt[4] = 0;
    for (int i = 0; i < n; i++)
        if (!removed[i] && (c == 0 || cid[i] == c))
        {
            int k = 0;
            for (int j = 0; j < 4; j++) if (score[i][j] >= 60) k++;
            cnt[k]++;
        }
}

void stat()
{
    int c;
    printf ("Please enter class ID, 0 for the whole statistics.\n");
    scanf ("%d", &c);
    for (int i = 0; i < 4; i++)
    {
        int passed, failed;
        double avg = get_course_stat (c, i, &passed, &failed);
        printf ("%s\n", course_name[i]);
        printf ("Average Score: %.2f\n", avg + EPS);
        printf ("Number of passed students: %d\n", passed);
        printf ("Number of failed students: %d\n", failed);
        printf ("\n");
    }
    int cnt[5];
    get_overall_stat (c, cnt);
    printf ("Overall:\n");
    printf ("Number of students who passed all subjects: %d\n", cnt[4]);
    printf ("Number of students who passed 3 or more subjects: %d\n", cnt[4] + cnt[3]);
    printf ("Number of students who passed 2 or more subjects: %d\n", cnt[4] + cnt[3] + cnt[2]);
    printf ("Number of students who passed 1 or more subjects: %d\n", cnt[4] + cnt[3] + cnt[2] + cnt[1]);
    printf ("Number of students who failed all subjects: %d\n", cnt[0]);
    printf ("\n");
}

int main()
{
    for (;;)
    {
        int choice;
        printf ("Welcome to Student Performance Management System (SPMS).\n");
        printf ("\n");
        printf ("1 - Add\n");
        printf ("2 - Remove\n");
        printf ("3 - Query\n");
        printf ("4 - Show ranking\n");
        printf ("5 - Show Statistics\n");
        printf ("0 - Exit\n");
        printf ("\n");
        scanf ("%d", &choice);
        if (choice == 0) break;
        if (choice == 1) add();
        if (choice == 2) DQ (0);
        if (choice == 3) DQ (1);
        if (choice == 4) printf ("Showing the ranklist hurts students' self-esteem. Don't do that.\n");
        if (choice == 5) stat();
    }
    return 0;
}

Posted on In ,

Task schedule

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description

有一台机器，并且给你这台机器的工作表，工作表上有n个任务，机器在ti时间执行第i个任务，1秒即可完成1个任务。
有m个询问，每个询问有一个数字q，表示如果在q时间有一个工作表之外的任务请求，请计算何时这个任务才能被执行。
机器总是按照工作表执行，当机器空闲时立即执行工作表之外的任务请求。
Input

输入的第一行包含一个整数T， 表示一共有T组测试数据。
对于每组测试数据：
第一行是两个数字n, m，表示工作表里面有n个任务, 有m个询问；
第二行是n个不同的数字t1, t2, t3….tn，表示机器在ti时间执行第i个任务。
接下来m行，每一行有一个数字q，表示在q时间有一个工作表之外的任务请求。
特别提醒：m个询问之间是无关的。
[Technical Specification]

  1. T <= 50
  2. 1 <= n, m <= 10^5
  3. 1 <= ti <= 2/*10^5, 1 <= i <= n
  4. 1 <= q <= 2/*10^5
    Output

对于每一个询问，请计算并输出该任务何时才能被执行，每个询问输出一行。
Sample Input

1 5 5 1 2 3 5 6 1 2 3 4 5
Sample Output

4 4 4 4 7

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<cstdio>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
int busy[N], ans[N], m, n, t, cas, q;
int main()
{
    scanf ("%d", &cas);
    while (cas--)
    {
        scanf ("%d%d", &n, &m);
        memset (busy, 0, sizeof (busy));
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &t), busy[t] = 1;
        ans[200001] = 200001;
        for (int i = 200000; i >= 1; --i)
            if (busy[i]) ans[i] = ans[i + 1];
            else ans[i] = i;
        while (m--)
            scanf ("%d", &q), printf ("%d\n", ans[q]);
    }
    return 0;
}

Posted on In ,

Most crossword puzzle fans are used to anagrams–groups of words with the same letters in different orders–for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have this attribute, no matter how you rearrange their letters, you cannot form another word. Such words are called ananagrams, an example is QUIZ.

Obviously such definitions depend on the domain within which we are working; you might think that ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possible domain would be the entire English language, but this could lead to some problems. One could restrict the domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in the same domain) but NOTE is not since it can produce TONE.

Write a program that will read in the dictionary of a restricted domain and determine the relative ananagrams. Note that single letter words are, ipso facto, relative ananagrams since they cannot be ``rearranged’’ at all. The dictionary will contain no more than 1000 words.

Input

Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. Note that words that contain the same letters but of differing case are considered to be anagrams of each other, thus tIeD and EdiT are anagrams. The file will be terminated by a line consisting of a single /#.

Output

Output will consist of a series of lines. Each line will consist of a single word that is a relative ananagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will always be at least one relative ananagram.

Sample input

ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIed noel dire Disk mace Rob dries /#

Sample output

Disk NotE derail drIed eye ladder soon

题意 给你一篇文章 以”/#”号结束 按字典序求输出这篇文章中真正只出现过一次的单词 就是不能通过字母重新排列得到文章中另一个单词的单词

把每个单词的字母全部化为小写 再把这个单词中的字母按字典序排列 得到一个字符串 用map记下出现次数就行 只出现过一次的就是要输出的

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cctype>
#include<map>
using namespace std;
typedef vector<string>::iterator it;
vector<string> ans;
map<string, int> cnt, tcnt;
map<string, string> ss;
int main()
{
    string s, t;
    while (cin >> s, s != "#")
    {
        t = s;
        ans.push_back (s);
        for (int j = 0; j < t.length(); ++j)
            t[j] = tolower (t[j]);
        sort (t.begin(), t.end());
        ss[s] = t;
        ++cnt[t];
    }
    sort (ans.begin(), ans.end());
    for (it i = ans.begin(); i < ans.end(); ++i)
        if (cnt[ss[*i]] == 1)  cout << *i << endl;
    return 0;
}

Posted on In ,

题意 有n辆火车 按1到n的顺序进站 最后进站的车可以在任何时候出去 判断给定的出站序列是否可能

火车只有两种状态 从A进站 或者从站到B 模拟栈的操作就行了

令A表示A中当前待进站的第一辆火车 tar[B]表示出站序列中当前应该出站的火车 sta为火车站

当A==tar[B]的时候 A进站马上出战 否则当站中最后一辆==tar[B]时 这辆车出站 都不满足就只能A中的最前面的火车进站

当n辆火车全部进站 而站中还有火车是 给定的出战序列就是不可能的

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
#include<cstdio>
#include<stack>
using namespace std;
const int N = 1005;
int n, tar[N], A, B;
int main()
{
    while (scanf ("%d", &n), n)
    {
        while (scanf ("%d", &tar[1]), tar[1])
        {
            for (int i = 2; i <= n; ++i)
                scanf ("%d", &tar[i]);
            stack<int> sta;
            A = B = 1;
            bool ok = true;
            while (B <= n)
            {
                if (A == tar[B])
                {   ++A; ++B;   }
                else if (!sta.empty() && sta.top() == tar[B])
                {   sta.pop();  ++B;  }
                else if (A <= n)
                    sta.push (A++);
                else
                {   ok = false;  break;  }
            }
            printf (ok ? "Yes\n" : "No\n");
        }
        printf("\n");
    }
    return 0;
}

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

\begin{picture}(6774,3429)(0,-10)\put(1789.500,1357.500){\arc{3645.278}{4.7247}......tFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}Station}}}}}\end{picture}

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has$N \leŸ 1000$ coaches numbered in increasing order $1, 2, \dots, N$. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be $a_1. a_2, \dots, a_N$. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

The input file consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of $1, 2, \dots, N$ The last line of the block contains just 0.

The last block consists of just one line containing 0.

The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains No . In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last ``null’’ block of the input file.

5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0

Yes No Yes

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

\begin{picture}(6774,3429)(0,-10)\put(1789.500,1357.500){\arc{3645.278}{4.7247}......tFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}Station}}}}}\end{picture}

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has$N \leŸ 1000$ coaches numbered in increasing order $1, 2, \dots, N$. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be $a_1. a_2, \dots, a_N$. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

The input file consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of $1, 2, \dots, N$ The last line of the block contains just 0.

The last block consists of just one line containing 0.

The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains No . In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last ``null’’ block of the input file.

5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0

Yes No Yes

Posted on In ,

觉得这题最难的就是理解题意了 应该怪我英语太差了

题意 一个大于1的数可以 表示成p1^e1/*p2^e2/*p3^e3/*p4^e4/p5^e5/…/*pn^en的形式 其中p是素数 且p是递减的 p< 32767

输入给你这个数的这种表达形式的所有p和e 第奇数个数为pi第偶数个数为ei 每行的所有数据表示一个数 你要求出这个数x然后输出x-1的这种表达形式；

理解了题意这个题就简单了 直接暴力可能会超时 所以还是打了个素数表 还要注意pow的前一个参数要乘以1.0 不然会精度丢失

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
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 33000;
int x, a, b , m , last , ans[N], vis[N], prime[N];

void initPrime()
{
    int num = 0, m = sqrt (N + 0.5);
    for (int i = 2; i <= m; ++i)
    {
        if (vis[i] == 0)
            for (int j = i * i; j < N; j += i)
                vis[j] = 1;
    }
    for (int i = 2, t = 0; i < N; ++i)
        if (!vis[i]) prime[++num] = i;
}

int main()
{
    initPrime(); char c;
    while (scanf ("%d", &a), a)
    {
        scanf ("%d%c", &b, &c);
        x = pow (a*1.0, b);
        while (c == ' ')
        {
            scanf ("%d %d%c", &a, &b, &c);
            x = x * pow (a*1.0, b);
        }
        --x; last = 0;
        memset(ans,0,sizeof(ans));

        for (int i = 1; x > 1; m=i,++i)
            if (x % prime[i] == 0)
            {
                if (!last) last = i;
                while (x % prime[i] == 0)
                {
                    ++ans[i];
                    x /= prime[i];
                }
            }
        for (int i = m; i >= last; --i)
            if (ans[i]) printf (i == last ? "%d %d\n" : "%d %d ", prime[i], ans[i]);
    }
    return 0;
}

Prime Land

Description
Everybody in the Prime Land is using a prime base number system. In this system, each positive integer x is represented as follows: Let {pi}i=0,1,2,… denote the increasing sequence of all prime numbers. We know that x > 1 can be represented in only one way in the form of product of powers of prime factors. This implies that there is an integer kx and uniquely determined integers ekx, ekx-1, …, e1, e0, (ekx > 0), that The sequence
(ekx, ekx-1, … ,e1, e0)
is considered to be the representation of x in prime base number system.
It is really true that all numerical calculations in prime base number system can seem to us a little bit unusual, or even hard. In fact, the children in Prime Land learn to add to subtract numbers several years. On the other hand, multiplication and division is very simple.
Recently, somebody has returned from a holiday in the Computer Land where small smart things called computers have been used. It has turned out that they could be used to make addition and subtraction in prime base number system much easier. It has been decided to make an experiment and let a computer to do the operation ``minus one’’.
Help people in the Prime Land and write a corresponding program.
For practical reasons we will write here the prime base representation as a sequence of such pi and ei from the prime base representation above for which ei > 0. We will keep decreasing order with regard to pi.

Input

The input consists of lines (at least one) each of which except the last contains prime base representation of just one positive integer greater than 2 and less or equal 32767. All numbers in the line are separated by one space. The last line contains number 0.

Output

The output contains one line for each but the last line of the input. If x is a positive integer contained in a line of the input, the line in the output will contain x - 1 in prime base representation. All numbers in the line are separated by one space. There is no line in the output corresponding to the last ``null’’ line of the input.

Sample Input

17 1 5 1 2 1 509 1 59 1 0

Sample Output

2 4 3 2 13 1 11 1 7 1 5 1 3 1 2 1

Prime Land

Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2972 Accepted: 1362

Description
Everybody in the Prime Land is using a prime base number system. In this system, each positive integer x is represented as follows: Let {pi}i=0,1,2,… denote the increasing sequence of all prime numbers. We know that x > 1 can be represented in only one way in the form of product of powers of prime factors. This implies that there is an integer kx and uniquely determined integers ekx, ekx-1, …, e1, e0, (ekx > 0), that The sequence
(ekx, ekx-1, … ,e1, e0)
is considered to be the representation of x in prime base number system.
It is really true that all numerical calculations in prime base number system can seem to us a little bit unusual, or even hard. In fact, the children in Prime Land learn to add to subtract numbers several years. On the other hand, multiplication and division is very simple.
Recently, somebody has returned from a holiday in the Computer Land where small smart things called computers have been used. It has turned out that they could be used to make addition and subtraction in prime base number system much easier. It has been decided to make an experiment and let a computer to do the operation ``minus one’’.
Help people in the Prime Land and write a corresponding program.
For practical reasons we will write here the prime base representation as a sequence of such pi and ei from the prime base representation above for which ei > 0. We will keep decreasing order with regard to pi.

Input

The input consists of lines (at least one) each of which except the last contains prime base representation of just one positive integer greater than 2 and less or equal 32767. All numbers in the line are separated by one space. The last line contains number 0.

Output

The output contains one line for each but the last line of the input. If x is a positive integer contained in a line of the input, the line in the output will contain x - 1 in prime base representation. All numbers in the line are separated by one space. There is no line in the output corresponding to the last ``null’’ line of the input.

Sample Input

17 1 5 1 2 1 509 1 59 1 0

Sample Output

2 4 3 2 13 1 11 1 7 1 5 1 3 1 2 1

Posted on In ,

Copying Books

Time Limit: 3000MS Memory Limit: 10000K Total Submissions: 7109 Accepted: 2221

Description
Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.
Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 … m) that may have different number of pages (p1, p2 … pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, … < bk-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

Input

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integers p1, p2, … pm separated by spaces. All these values are positive and less than 10000000.

Output

For each case, print exactly one line. The line must contain the input succession p1, p2, … pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character (‘/‘) to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.
If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

Sample Input

2 9 3 100 200 300 400 500 600 700 800 900 5 4 100 100 100 100 100

Sample Output

100 200 300 400 500 / 600 700 / 800 900 100 / 100 / 100 / 100 100

Source

Central Europe 1998

题意 k个人复制m本书 求最小的时间 即把m个数分成k份 使和最大的那份最小

d[i][j]表示i个人完成前j本书需要的时间 有转移方程d[i][j]=min(d[i][j],max(d[i-1][k],s[j]-s[k])) k表示i-1到j之间的所有数 s[k]表示从第一本书到第k本书需要时间的和 初始d[1][i]=s[i];

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 550, INF = 0x3f3f3f3f;
int a[N], flag[N], s[N],  d[N][N], t, cas, n, m, ans;
int dp (int i, int j)
{
    if (d[i][j] > 0) return d[i][j];
    d[i][j] = INF;
    for (int k = i - 1; k < j; ++k)
        d[i][j] = min (d[i][j], max (dp (i - 1, k), s[j] - s[k]));
    return d[i][j];
}

int main()
{
    scanf ("%d", &cas);
    while (cas--)
    {
        scanf ("%d%d", &n, &m);
        memset (d, -1, sizeof (d));  memset (flag, -1, sizeof (flag));
        for (int i = 1; i <= n; ++i)
        { scanf ("%d", &a[i]); d[1][i] = s[i] = s[i - 1] + a[i]; }
        ans = dp (m, n);

        for (int i = n,t=0 ; i >= 1; --i)
            if ( ( (t = t + a[i]) > ans) || m > i)
                {  t = a[i]; flag[i] = 0; --m; }
        for (int i = 1; i <= n; ++i)
        {
            printf (flag[i] ? "%d" : "%d /", a[i]);
            printf (i == n ? "\n" : " ");
        }
    }
    return 0;
}
0%