Codeforces Round#229 DIV2 A,B,C,D-布布扣-bubuko.com

这次的CF很简单，区分度不大。。。

A太水了，两个set搞定。。。B太水了没印象。。。C k比较小，可以预处理一遍。。。 D 把格子按i+j排序，选最小的k个就是目标位置。。。倒着输出。。。

Inna loves sleeping very much, so she needs n alarm clocks in total to wake up. Let‘s suppose that Inna‘s room is a 100?×?100 square with the lower left corner at point (0,?0) and with the upper right corner at point (100,?100). Then the alarm clocks are points with integer coordinates in this square.

The morning has come. All n alarm clocks in Inna‘s room are ringing, so Inna wants to turn them off. For that Inna has come up with an amusing game:

First Inna chooses a type of segments that she will use throughout the game. The segments can be either vertical or horizontal.
Then Inna makes multiple moves. In a single move, Inna can paint a segment of any length on the plane, she chooses its type at the beginning of the game (either vertical or horizontal), then all alarm clocks that are on this segment switch off. The game ends when all the alarm clocks are switched off.

Inna is very sleepy, so she wants to get through the alarm clocks as soon as possible. Help her, find the minimum number of moves in the game that she needs to turn off all the alarm clocks!

Input

The first line of the input contains integer n (1?≤?n?≤?105) — the number of the alarm clocks. The next n lines describe the clocks: the i-th line contains two integers xi, yi — the coordinates of the i-th alarm clock (0?≤?xi,?yi?≤?100).

Note that a single point in the room can contain any number of alarm clocks and the alarm clocks can lie on the sides of the square that represents the room.

Output

In a single line print a single integer — the minimum number of segments Inna will have to draw if she acts optimally.

Sample test(s)

input
4
0 0
0 1
0 2
1 0

output
2

input
4
0 0
0 1
1 0
1 1

output
2

input
4
1 1
1 2
2 3
3 3

output
3

Note

In the first sample, Inna first chooses type "vertical segments", and then she makes segments with ends at : (0,?0), (0,?2); and, for example, (1,?0), (1,?1). If she paints horizontal segments, she will need at least 3 segments.

In the third sample it is important to note that Inna doesn‘t have the right to change the type of the segments during the game. That‘s why she will need 3 horizontal or 3 vertical segments to end the game.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

set<int> Heng,Shu;

int main()
{
    int N,a,b;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        scanf("%d%d",&a,&b);
        Heng.insert(a);Shu.insert(b);
    }
    printf("%d\n",min(Heng.size(),Shu.size()));
    return 0;
}

Inna is a great piano player and Dima is a modest guitar player. Dima has recently written a song and they want to play it together. Of course, Sereja wants to listen to the song very much.

A song is a sequence of notes. Dima and Inna want to play each note at the same time. At that, they can play the i-th note at volume v(1?≤?v?≤?ai; v is an integer) both on the piano and the guitar. They should retain harmony, so the total volume with which the i-th note was played on the guitar and the piano must equal bi. If Dima and Inna cannot play a note by the described rules, they skip it and Sereja‘s joy drops by 1. But if Inna and Dima play the i-th note at volumes xi and yi (xi?+?yi?=?bi) correspondingly, Sereja‘s joy rises byxi·yi.

Sereja has just returned home from the university and his current joy is 0. Help Dima and Inna play the song so as to maximize Sereja‘s total joy after listening to the whole song!

Input

The first line of the input contains integer n (1?≤?n?≤?105) — the number of notes in the song. The second line contains n integers ai (1?≤?ai?≤?106). The third line contains n integers bi (1?≤?bi?≤?106).

Output

In a single line print an integer — the maximum possible joy Sereja feels after he listens to a song.

Sample test(s)

input
3
1 1 2
2 2 3

output
4

input
1
2
5

output
-1

Note

In the first sample, Dima and Inna play the first two notes at volume 1 (1?+?1?=?2, the condition holds), they should play the last note at volumes 1 and 2. Sereja‘s total joy equals: 1·1?+?1·1?+?1·2?=?4.

In the second sample, there is no such pair (x,?y), that 1?≤?x,?y?≤?2, x?+?y?=?5, so Dima and Inna skip a note. Sereja‘s total joy equals -1.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;

int n;
LL a[110000],b[110000],ans;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n;i++)
    {
        if(a[i]+a[i]>=b[i]&&(b[i]/2)&&(b[i]-b[i]/2))
        {
            ans+=b[i]/2*(b[i]-b[i]/2);
        }
        else ans+=-1;
    }

    cout<<ans<<endl;
    return 0;
}

Inna loves sweets very much. She has n closed present boxes lines up in a row in front of her. Each of these boxes contains either a candy (Dima‘s work) or nothing (Sereja‘s work). Let‘s assume that the boxes are numbered from 1 to n, from left to right.

As the boxes are closed, Inna doesn‘t know which boxes contain candies and which boxes contain nothing. Inna chose number k and asked w questions to Dima to find that out. Each question is characterised by two integers li,?ri (1?≤?li?≤?ri?≤?n; r?-?l?+?1 is divisible byk), the i-th question is: "Dima, is that true that among the boxes with numbers from li to ri, inclusive, the candies lie only in boxes with numbers li?+?k?-?1, li?+?2k?-?1, li?+?3k?-?1, ..., ri?"

Dima hates to say "no" to Inna. That‘s why he wonders, what number of actions he will have to make for each question to make the answer to the question positive. In one action, Dima can either secretly take the candy from any box or put a candy to any box (Dima has infinitely many candies). Help Dima count the number of actions for each Inna‘s question.

Please note that Dima doesn‘t change the array during Inna‘s questions. That‘s why when you calculate the number of operations for the current question, please assume that the sequence of boxes didn‘t change.

Input

The first line of the input contains three integers n, k and w (1?≤?k?≤?min(n,?10),?1?≤?n,?w?≤?105). The second line contains ncharacters. If the i-th box contains a candy, the i-th character of the line equals 1, otherwise it equals 0.

Each of the following w lines contains two integers li and ri (1?≤?li?≤?ri?≤?n) — the description of the i-th question. It is guaranteed thatri?-?li?+?1 is divisible by k.

Output

For each question, print a single number on a single line — the minimum number of operations Dima needs to make the answer to the question positive.

Sample test(s)

input
10 3 3
1010100011
1 3
1 6
4 9

output
1
3
2

Note

For the first question, you need to take a candy from the first box to make the answer positive. So the answer is 1.

For the second question, you need to take a candy from the first box, take a candy from the fifth box and put a candy to the sixth box. The answer is 3.

For the third question, you need to take a candy from the fifth box and put it to the sixth box. The answer is 2.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int n,k,w;
string cmd;
int tang[110000],bian[11][110000];

int main()
{
    cin>>n>>k>>w;cin>>cmd;
    for(int i=0;i<n;i++) if(cmd[i]==‘1‘) tang[i+1]=1;
    for(int i=0;i<k;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            bian[i][j]=bian[i][j-1];
            if(((j-i)%k==0)&&tang[j]!=1) bian[i][j]++;
            else if(((j-i)%k)&&tang[j]!=0) bian[i][j]++;
        }
    }

    while(w--)
    {
        int a,b,S;
        cin>>a>>b;
        S=(a-1)%k;
        printf("%d\n",bian[S][b]-bian[S][a-1]);
    }

    return 0;
}

Inna loves sweets very much. That‘s why she decided to play a game called "Sweet Matrix".

Inna sees an n?×?m matrix and k candies. We‘ll index the matrix rows from 1 to n and the matrix columns from 1 to m. We‘ll represent the cell in the i-th row and j-th column as (i,?j). Two cells (i,?j) and (p,?q) of the matrix are adjacent if |i?-?p|?+?|j?-?q|?=?1. A path is a sequence of the matrix cells where each pair of neighbouring cells in the sequence is adjacent. We‘ll call the number of cells in the sequence the path‘s length.

Each cell of the matrix can have at most one candy. Initiallly, all the cells are empty. Inna is trying to place each of the k candies in the matrix one by one. For each candy Inna chooses cell (i,?j) that will contains the candy, and also chooses the path that starts in cell (1,?1) and ends in cell (i,?j) and doesn‘t contain any candies. After that Inna moves the candy along the path from cell (1,?1) to cell (i,?j), where the candy stays forever. If at some moment Inna can‘t choose a path for the candy, she loses. If Inna can place all the candies in the matrix in the described manner, then her penalty equals the sum of lengths of all the paths she has used.

Help Inna to minimize the penalty in the game.

Input

The first line of the input contains three integers n, m and k (1?≤?n,?m?≤?50,?1?≤?k?≤?n·m).

Output

In the first line print an integer — Inna‘s minimum penalty in the game.

In the next k lines print the description of the path for each candy. The description of the path of the candy that is placed i-th should follow on the i-th line. The description of a path is a sequence of cells. Each cell must be written in the format (i,?j), where i is the number of the row and j is the number of the column. You are allowed to print extra whitespaces in the line. If there are multiple optimal solutions, print any of them.

Please follow the output format strictly! If your program passes the first pretest, then the output format is correct.

Sample test(s)

input
4 4 4

output
8
(1,1) (2,1) (2,2)
(1,1) (1,2)
(1,1) (2,1)
(1,1)

Note

Note to the sample. Initially the matrix is empty. Then Inna follows her first path, the path penalty equals the number of cells in it — 3. Note that now no path can go through cell (2, 2), as it now contains a candy. The next two candies go to cells (1, 2) and (2, 1). Inna simply leaves the last candy at cell (1, 1), the path contains only this cell. The total penalty is: 3 + 2 + 2 + 1 = 8.

Note that Inna couldn‘t use cell (1, 1) to place, for instance, the third candy as in this case she couldn‘t have made the path for the fourth candy.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int abs(int x)
{
    return x<=0? -x : x;
}

int n,m,k;
struct node
{
    int x,y,id,ra;
    bool operator < (const node x) const
    {
        if(id!=x.id)
        return id>x.id;
        else
        return ra<x.ra;
    }
}arr[3000];

priority_queue<node> q;

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            q.push((node){i,j,i+j-1,abs(i-j)});
        }
    }
    int cnt=0,sum=0;
    for(int i=0;i<k;i++)
    {
        node u=q.top();
        arr[cnt++]=u;
        sum+=arr[cnt-1].id;
        q.pop();
    }
    cout<<sum<<endl;
    for(int i=cnt-1;i>=0;i--)
    {
        int x=arr[i].x;int y=arr[i].y;
        for(int j=1;j<=x;j++)
        {
            printf("(%d,%d)",j,1);
            if(j!=x) putchar(32);
        }
        if(2<=y) putchar(32);
        for(int j=2;j<=y;j++)
        {
            printf("(%d,%d)",x,j);
            if(j!=y) putchar(32);
        }
        if(i!=0) putchar(10);
    }

    return 0;
}

Codeforces Round#229 DIV2 A,B,C,D

原文：http://blog.csdn.net/u012797220/article/details/19100407