codeforce #165 div2

这次做的不够理想，过程磕磕绊绊，C题还是倒在第42个样例上（看了下WA的人，就数我最悲剧）......

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

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

a == 180.0 - (360.0/j)

j为边数

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

#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 to2^k(kis an integer,k ≥ 0) units. A magical boxvcan be put inside a magical boxu, if side length ofvis strictly less than the side length ofu. In particular, Emuskald can put 4 boxes of side length2^k - 1into one box of side length2^k, 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 integern(1 ≤ n ≤ 10⁵), the number of different sizes of boxes Emuskald has. Each of followingnlines contains two integersk_ianda_i(0 ≤ k_i ≤ 10⁹,1 ≤ a_i ≤ 10⁹), which means that Emuskald hasa_iboxes with side length2^k_i. It is guaranteed that all ofk_iare distinct.

Output

Output a single integerp, such that the smallest magical box that can contain all of Emuskald’s boxes has side length2^p.

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也是超过范围的。所以去掉等号，就行了。

#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++)
        {
            if(2 * box[i+1].len - 2 * box[i].len < 32)
            {
                int t = ceil(box[i].num*1.0/((1 << (2*box[i+1].len -2 * box[i].len)))) - box[i+1].num;
                if(t > 0)
                    box[i+1].num += t;
            }
        }
        long long t = box[n-1].num;
        int i;
        for(i=1;; i++)
        {
            if(1 << (2 * i) >= t)
                break;
        }
        cout << i + box[n-1].len << endl;
    }
    return 0;
}

赛后发现C题是div1的第一题，可见去div1就是挂零的节奏......长路漫漫啊！！！