Codeforces Round #280 (Div. 2 A,B,C,D,E)_html/css_WEB-ITnose

It’s even harder to play CF after changing the time zone. . . I didn’t do it yesterday, so I made up for it today.

A. Vanya and Cubes

The number regularity of each addition is obviously: (i 1)*i/2. You can get the answer by violently enumerating i.

#include <algorithm>#include <iostream>#include <stdlib.h>#include <string.h>#include <iomanip>#include <stdio.h>#include <string>#include <queue>#include <cmath>#include <stack>#include <map>#include <set>#define eps 1e-8#define M 1000100#define LL long long//#define LL long long#define INF 0x3f3f3f#define PI 3.1415926535898#define mod 1000000007#define rson mid+1, r, rt<<1|1#define lson l, mid, rt<<1#define root 0, ans-1, 1const int maxn = 1001;using  namespace std;int main(){    int n;    while(~scanf("%d",&n))    {        int ans = 1;        int sum = 1;        while(1)        {            ans++;            sum += (ans+1)*ans/2;            if(sum >= n) break;        }        if(sum > n) ans--;        cout<<ans<<endl;    }}

B - Vanya and Lanterns

Sort in order, and then find the one with the smallest distance. Pay attention to judging the starting point and end point. Because their distance does not use /2.

#include <algorithm>#include <iostream>#include <stdlib.h>#include <string.h>#include <iomanip>#include <stdio.h>#include <string>#include <queue>#include <cmath>#include <stack>#include <map>#include <set>#define eps 1e-8#define M 1000100#define LL long long//#define LL long long#define INF 0x3f3f3f#define PI 3.1415926535898#define mod 1000000007#define rson mid+1, r, rt<<1|1#define lson l, mid, rt<<1#define root 0, ans-1, 1const int maxn = 1010;using  namespace std;int num[maxn];int main(){    int n, d;    while(~scanf("%d %d",&n, &d))    {        for(int i = 0; i < n; i++) scanf("%d",&num[i]);        sort(num, num+n);        double Max = 0.0;        for(int i = 0; i < n-1; i++) Max = max(Max, (double)((num[i+1]-num[i])*1.0/2));        Max = max(Max, num[0]*1.0-0);        Max = max(Max, d*1.0-num[n-1]*1.0);        printf("%.12lf\n",Max);    }    return 0;}

C - Vanya and Exams

C It is very simple to understand the questions, it is just a greed after sorting.

#include <algorithm>#include <iostream>#include <stdlib.h>#include <string.h>#include <iomanip>#include <stdio.h>#include <string>#include <queue>#include <cmath>#include <stack>#include <map>#include <set>#define eps 1e-8#define M 1000100#define LL long long//#define LL long long#define INF 0x3f3f3f#define PI 3.1415926535898#define mod 1000000007#define rson mid+1, r, rt<<1|1#define lson l, mid, rt<<1#define root 0, ans-1, 1const int maxn = 100010;using  namespace std;struct node{    LL a, b;}f[maxn];bool cmp(node a, node b){    return a.b < b.b;}int main(){    LL n, r, ave;    while(~scanf("%I64d %I64d %I64d",&n, &r, &ave))    {        LL ans = ave*n;        LL sum = 0LL;        for(int i = 0; i < n; i++)        {            scanf("%I64d %I64d",&f[i].a, &f[i].b);            sum += f[i].a;        }        sort(f, f+n, cmp);        LL xans = 0;        for(int i = 0; i < n; i++)        {            LL p = ans-sum;            LL sp = max(r-f[i].a, 0LL);            if(p <= 0) break;            if(p > sp)            {                sum += sp;                xans += f[i].b*sp;            }            else            {                xans += p*f[i].b;                sum += p;                break;            }        }        cout<<xans<<endl;    }}

D - Vanya and Computer Game

Give you an x ​​and a y. It allows you to determine who completes the task first within n times x or y. In fact, it is to determine whose integer multiple reaches the given nx first. It is a binary enumeration. If it is x, common multiples of y will output both. If it is a multiple of y, output: Vanya , if it is a multiple of 🎜>

memory limit per test

256 megabytes

input

standard input

output

standard output

Vanya and his friend Vova play a computer game where they need to destroy n monsters to pass a level. Vanya's character performs attack with frequency x hits per second and Vova's character performs attack with frequency y hits per second. Each character spends fixed time to raise a weapon and then he hits (the time to raise the weapon is 1?/?x seconds for the first character and 1?/?y seconds for the second one). The i-th monster dies after he receives ai hits.

Vanya and Vova wonder who makes the last hit on each monster. If Vanya and Vova make the last hit at the same time, we assume that both of them have made the last hit.

Input The first line contains three integers n,x,y (1?≤?n?≤?105, 1?≤?x,? y?≤?106) ? the number of monsters, the frequency of Vanya's and Vova's attack, correspondingly.

Next n lines contain integers ai (1?≤?ai?≤?109) ? the number of hits needed do destroy the i-th monster.

Output

Print n lines. In the i-th line print word "Vanya", if the last hit on the The i-th monster was performed by Vanya, "Vova", if Vova performed the last hit, or "Both", if both boys performed it at the same time.

Sample test( s)

input

output

input

4 3 21234

output

VanyaVovaVanyaBoth

2 1 112

Note

In the first sample Vanya makes the first hit at time 1?/?3, Vova makes the second hit at time 1?/?2, Vanya makes the third hit at time 2?/?3, and both boys make the fourth and fifth hit simultaneously at the time 1.

In the second sample Vanya and Vova make the first and second hit simultaneously at time 1.

BothBoth

E - Vanya and Field

This question is quite good. In fact, it has rules:

The key condition of the question is this

First think about a problem. First, in a one-dimensional case, assume there is only one row of grids. , the length is x, the distance that can be moved each time is dx, and gcd(x,dx)=1, simulate it manually and you can find the pattern. From a certain point until you return to this point, the number of steps is x times, and the points dropped each time are not repeated, that is, the positions of these x times cover every square on the entire grid.

#include <algorithm>#include <iostream>#include <stdlib.h>#include <string.h>#include <iomanip>#include <stdio.h>#include <string>#include <queue>#include <cmath>#include <stack>#include <time.h>#include <map>#include <set>#define eps 1e-8#define M 1000100#define LL long long//#define LL long long#define INF 0x3f3f3f#define PI 3.1415926535898#define mod 1000const int maxn = 200010;using namespace std;const LL R = 1e15;int main(){    LL n, x, y;    while(~scanf("%I64d %I64d %I64d", &n, &x, &y))    {        LL nx;        for(int i = 0; i < n; i++)        {            scanf("%I64d",&nx);            LL l = 0;            LL r = R;            while(l < r)            {                LL mid = (l+r)>>1;                if(mid/x+mid/y < nx) l = mid+1;                else r = mid;            }            if(l%x == 0 && l%y == 0) cout<<"Both"<<endl;            else if(l%y == 0) cout<<"Vanya"<<endl;            else cout<<"Vova"<<endl;        }    }    return 0;}

Now in the two-dimensional case, gcd(n,dx) = gcd(n,dy) = 1, that is, starting from the intersection of a certain row and a certain column, to return to this intersection, just It takes n steps and these n steps cover every row and column. Each cycle must go once for each x and once for each y. n grids belong to a group of cycles. There are n*n grids in total, so there are n groups of cycles. The cells within a set of cycles are equivalent. The n grids in the same row all come from different n groups.

Now consider a special set of loops. This set of loops starts from (0,0)

After taking the first step, you will reach (dx%n, dy%n)

The second step goes to (2*dx%n, 2*dy%n)

The kth step goes to (k*dx%n, k*dy%n)

用一个对应关系存储，从（0，0）出发的，经过了k步以后，会到达位置（x[k] , y[k]）。

 

然后考虑普遍的情况了，每组循环都比如经过(0, y0)这个点

从这个点出发的第一步 (dx%n, (y0+dy)%n) 

第k步到 (dx%n, (y0+dy)%n)， 也即(x[k], (y0+y[k])%n)

 

那么现在给你某个坐标（x，y），要怎么算出他属于哪一组循环的呢

根据等式x[k]==x，可以求出对应的k的值

那就能求出对应的y[k]了，然后y0+y[k]==y →  y0=y-y[k]

这样就知道这个（x，y） 是属于 （0，y0）这一组的了

 

那么算法大概是这样：

预处理出x[k],y[k]，时间复杂度o（n）

遍历每一个apple的坐标（x，y），求出对应的坐标（0，y0），然后cnt[y0]++，复杂度o（m）

找出值最大的cnt[y]，答案就是(0,y)了。 总复杂度o(n+m)

摘自：http://www.cnblogs.com/someblue/p/4136436.html

E. Vanya and Field

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vanya decided to walk in the field of size n?×?n cells. The field contains m apple trees, the i-th apple tree is at the cell with coordinates(xi,?yi). Vanya moves towards vector (dx,?dy). That means that if Vanya is now at the cell (x,?y), then in a second he will be at cell . The following condition is satisfied for the vector: , where  is the largest integer that divides both a and b. Vanya ends his path when he reaches the square he has already visited.

Vanya wonders, from what square of the field he should start his path to see as many apple trees as possible.

Input

The first line contains integers n,?m,?dx,?dy(1?≤?n?≤?106, 1?≤?m?≤?105, 1?≤?dx,?dy?≤?n) ? the size of the field, the number of apple trees and the vector of Vanya's movement. Next m lines contain integers xi,?yi (0?≤?xi,?yi?≤?n?-?1) ? the coordinates of apples. One cell may contain multiple apple trees.

Output

Print two space-separated numbers ? the coordinates of the cell from which you should start your path. If there are several answers you are allowed to print any of them.

Sample test(s)

input

5 5 2 30 01 21 32 43 1

output

1 3

input

2 3 1 10 00 11 1

output

0 0

Note

In the first sample Vanya's path will look like: (1,?3)?-?(3,?1)?-?(0,?4)?-?(2,?2)?-?(4,?0)?-?(1,?3)

In the second sample: (0,?0)?-?(1,?1)?-?(0,?0)

#include <algorithm>#include <iostream>#include <stdlib.h>#include <string.h>#include <iomanip>#include <stdio.h>#include <string>#include <queue>#include <cmath>#include <math.h>#include <time.h>#include <stack>#include <map>#include <set>#define eps 1e-8///#define LL long long#define LL __int64#define INF 0x3f3f3f#define PI acos(-1)#define mod 1000000007using namespace std;const int maxn = 10000010;int vis[maxn];int num[maxn];struct node{    int x, y;    int k;}f[maxn];int main(){    int n, m, dx, dy;    while(~scanf("%d %d %d %d",&n, &m, &dx, &dy))    {        f[0].x = 0;        f[0].y = 0;        f[0].k = 0;        vis[0] = 0;        for(int i = 1; i < n; i++)        {            f[i].x = (f[i-1].x+dx)%n;            f[i].y = (f[i-1].y+dy)%n;            f[i].k = i;            vis[f[i].x] = i;        }        memset(num, 0, sizeof(num));        int x, y;        for(int i = 0; i < m; i++)        {            scanf("%d %d",&x, &y);            int k = vis[x];            int ky = f[k].y;            int y0 = (y-ky+n)%n;            num[y0]++;        }        int Max = 0;        int sk;        for(int i = 0; i < n; i++)        {            if(Max < num[i])            {                Max = num[i];                sk = i;            }        }        cout<<0<<" "<<sk<<endl;    }    return 0;}