codeforce #165 div2

 

A题：求所给角度（0--180）能否组成正多边形.。

套用内角公式（n - 2）* 180 / n ,则

a == 180.0 - (360.0/j)

j为边数

 

[cpp]  

#include <iostream>  

#include <cstdio>  

  

using namespace std;  

  

int main()  

{  

    int n;  

    double a;  

    while(cin >> n)  

    {  

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

        {  

            cin >> a;  

            int ok = 0;  

            for(int j=2; j<=360; j++)  

            {  

                if(a == 180.0 - (360.0/j))  

                {  

                    ok = 1;  

                    break;  

                }  

            }  

            if(ok == 1)  

            {  

                cout << "YES" << endl;  

            }  

            else  

                cout << "NO" << endl;  

        }  

    }  

    return 0;  

}  

 

 

B题：

原先有一系列板块编号1-n，如有某个板块更新信息则占据首位，其他后移。给出刷新后位置由前到后的板块编号，问一定更新信息的板块有几个。

 

相邻两个板块i,i+1如果编号i > 编号i+1。说明板块i一定更新了，板块i+1却不一定。而板块i更新，排在板块i前面的，也是必定更新了。

这样问题就变成找最后一个满足板块编号i > 编号i+1的。

 

[cpp]  

#include <iostream>  

#include <cstdio>  

  

using namespace std;  

  

int a[100005];  

  

int main()  

{  

    int n;  

    while(cin >> n)  

    {  

        int t=0;  

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

        {  

            cin >>  a[i];  

        }  

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

        {  

            if(a[i] > a[i+1])  

                t = i;  

        }  

        cout << t << endl;  

    }  

    return 0;  

}  

 

 

C题：

C. Magical Boxes

time limit per test 2 seconds

memory limit per test 256 megabytes

input standard input

output standard output

Emuskald is a well-known illusionist. One of his trademark tricks involves a set of magical boxes. The essence of the trick is in packing the boxes inside other boxes.

From the top view each magical box looks like a square with side length equal to 2k (k is an integer, k ≥ 0) units. A magical box v can be put inside a magical box u, if side length of v is strictly less than the side length of u. In particular, Emuskald can put 4 boxes of side length 2k - 1 into one box of side length 2k, or as in the following figure:

Emuskald is about to go on tour performing around the world, and needs to pack his magical boxes for the trip. He has decided that the best way to pack them would be inside another magical box, but magical boxes are quite expensive to make. Help him find the smallest magical box that can fit all his boxes.

Input

The first line of input contains an integer n (1 ≤ n ≤ 105), the number of different sizes of boxes Emuskald has. Each of following n lines contains two integers ki and ai (0 ≤ ki ≤ 109, 1 ≤ ai ≤ 109), which means that Emuskald has ai boxes with side length 2ki. It is guaranteed that all of ki are distinct.

Output

Output a single integer p, such that the smallest magical box that can contain all of Emuskald’s boxes has side length 2p.

Sample test(s)

input

2

0 3

1 5

output

3

input

1

0 4

output

1

input

2

1 10

2 2

output

3

Note

Picture explanation. If we have 3 boxes with side length 2 and 5 boxes with side length 1, then we can put all these boxes inside a box with side length 4, for example, as shown in the picture.

In the second test case, we can put all four small boxes into a box with side length 2.

 

有一堆大大小小的箱子，小的能放大的里面，求另取一个边长最短的箱子，将这些箱子装下。具体规则就看题吧...

想法是将已有箱子按照边长由小到大排序，一个循环中，将较小的放入较大些的，如果较小的剩余，则剩余的小的箱子换算成较大的；如此递推，

再枚举能装下已有最大箱子最小的边长的箱子。 虽然考虑到了k范围实在是太大了而加上if(2 * box[i+1].len - 2 * box[i].len <= 32)剔除，但没注意等于

32也是超过范围的。所以去掉等号，就行了。

[cpp] 

#include <iostream>  

#include <cstdio>  

#include <cmath>  

#include <algorithm>  

using namespace std;  

  

struct BOX  

{  

    long long len,num;  

} box[100005];  

  

bool cmp(BOX a, BOX b)  

{  

    return a.len < b.len;  

}  

  

int main()  

{  

    int n;  

    while(cin >> n)  

    {  

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

        {  

            cin >> box[i].len >> box[i].num;  

        }  

        sort(box,box+n,cmp);  

  

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

补充：软件开发 , C++ ,