Codeforces ラウンド #280 (ディビジョン 2 A、B、C、D、E)_html/css_WEB-ITnose

タイムゾーンを変更した後、CF をプレイするのはさらに難しくなります。 。 。昨日はできなかったので、今日は補いました。

A. Vanya と Cubes

各加算の数の規則性は明らかに次のとおりです: (i+1)*i/2。 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

順番に並べ替えて、距離が最も小さいものを見つけます。距離に /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 質問を理解するのは非常に簡単で、並べ替えた後の欲張りなものです。

#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 とコンピューター ゲーム

X と Y をあげてください。これにより、x または y の n 倍以内に誰が最初にタスクを完了するかを決定できます。実際には、どちらの整数の倍数が最初に指定された nx に到達するかを決定します。x の場合、y の公倍数が出力されます。 y の倍数の場合は出力: Vanya 、入力

出力

標準出力

の倍数の場合 Vanya と彼の友人 Vova は、パスするために n 匹のモンスターを破壊する必要があるコンピューター ゲームをプレイします。 Vanya のキャラクターは 1 秒あたり x ヒットの頻度で攻撃を実行し、Vova のキャラクターは 1 秒あたり y のヒットの頻度で攻撃を実行します。各キャラクターは武器を上げるのに一定の時間を費やしてから攻撃します (武器を上げる時間は 1?/?)。最初のキャラクターは x 秒、2 番目のキャラクターは 1?/?y 秒かかります)。i 番目のモンスターは AI ヒットを受けた後に死亡します。

ワーニャとヴォヴァは、どちらが各モンスターに最後にヒットするのか疑問に思っています。最後のヒットを同時に行うには、両方が最後のヒットを行ったと仮定します。

入力

最初の行には 3 つの整数 n,x,y (1?≤?n?≤?105、 1?≤?x,?y?≤?106) ? モンスターの数、ワーニャとヴォヴァの攻撃の頻度。

次の n 行には整数 ai (1?≤?ai?≤?109) が含まれます。 i 番目のモンスターを破壊するために必要なヒット数です。

出力

i 番目の行の出力ワード「Vanya」で、i 番目のモンスターに対する最後のヒットが Vanya によって実行された場合、 Vova が最後のヒットを演奏した場合は「Vova」、両方の少年が同時に演奏した場合は「両方」。

入力

4 3 21234

出力

VanyaVovaVanyaBoth

注

最初のサンプルでは、​​Vanya は時間 1?/?3 で最初のヒットを行い、Vova は時間 1?/?2 で 2 番目のヒットを行い、Vanya は3 番目のヒットは時間 2?/?3 で、両方の少年が時間 1 で 4 番目と 5 番目のヒットを同時に行います。

2 番目のサンプルでは、​​Vanya と Vova が時間 1 で最初と 2 番目のヒットを同時に行います。

2 1 112

E - Vanya と Field

この質問は非常に優れており、実際、パターンがあります:

質問の重要な条件は次のとおりです

まず、1 次元の場合について考えます。グリッドが 1 行だけあり、長さが x、毎回移動できる距離が dx、gcd(x,dx)=1 であると仮定します。このように手動でシミュレーションすると、パターンを見つけることができます。ある点からこの点に戻るまでのステップ数は x 回で、毎回ドロップされる点は繰り返されません。つまり、この x 回の位置がグリッド上の各正方形全体をカバーします。

さて、二次元の場合、gcd(n,dx) = gcd(n,dy) = 1、つまり、特定の行と特定の列の交点から開始して、この交点に戻るには、次のようになります。 n 個のステップを実行します。これらの n 個のステップはすべての行と列をカバーします。各サイクルは、x ごとに 1 回、y ごとに 1 回実行する必要があります。n 個のグリッドは、合計で n*n 個のグリッドがあるため、n 個のサイクル グループが存在します。一連のサイクル内のセルは同等です。同じ行内の n 個のグリッドはすべて、異なる n グループからのものです。

次に、特殊なループのセットを考えます。このループのセットは (0,0) から始まります

最初のステップを実行すると、(dx%n, dy%n) に到達します

2 番目のステップは ( 2 *dx%n, 2*dy%n)

k を (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;}