CodeforcesRound#280(Div.2A,B,C,D,E)_html/css

A. Vanya and Cubes

每次加的數(shù)規(guī)律性很明顯就是:(i+1)*i/2。暴力枚舉i就可以得到答案。

#include #include #include #include #include #include #include #include #include #include #include 

C看懂題目就很簡單了啊，就是排序之后的一個貪心。

#include #include #include #include #include #include #include #include #include #include #include 

給你一個x，一個y。讓你判斷在n次以內x，y誰先完成任務，其實就是判斷誰的整數(shù)倍先到給的nx，二分枚舉，如果是x，y的公倍數(shù)輸出both，如果是y的倍數(shù)輸出:Vanya,如果是x的倍數(shù)輸出：Vova.

D. Vanya and Computer Game

time limit per test

memory limit per test

input

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 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

4 3 21234

output

VanyaVovaVanyaBoth

input

2 1 112

output

BothBoth

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.

#include #include #include #include #include #include #include #include #include #include #include #include 

這個題目挺好的，其實他是有規(guī)律的：

題目的關鍵條件是這個

首先想個問題，先是一維的情況下，假設只有一行的格子，長度為x，每次能移動的距離為dx，而且gcd(x,dx)=1，這樣手動模擬一下，可以發(fā)現(xiàn)規(guī)律，從某個點出發(fā)直到回到這個點上，步數(shù)均為x次，而且每次落下的點都是不重復的，也即這x次的位置覆蓋了整條方格上的每一個方格。

那現(xiàn)在二維的情況下，gcd(n,dx) = gcd(n,dy) = 1，也就是從某一行和某一列的交點出發(fā)，要重新回到這個交點，就要經過n步而且這n步覆蓋了每一行每一列。每個循環(huán)必須每個x走一次以及每個y走一次，n個格子屬于一組循環(huán)里面的，總共有n*n個格子，所以有n組循環(huán)。一組循環(huán)內的格子是等價的。同一行內的n個格子均來自不同的n組。

現(xiàn)在考慮一組特殊的循環(huán)，這組循環(huán)從(0,0)開始出發(fā)

走了第一步以后就到 (dx%n, dy%n)

第二步到 (2*dx%n, 2*dy%n)

第k步到 (k*dx%n, k*dy%n)

用一個對應關系存儲，從（0，0）出發(fā)的，經過了k步以后，會到達位置（x[k] , y[k]）。

然后考慮普遍的情況了，每組循環(huán)都比如經過(0, y0)這個點

從這個點出發(fā)的第一步 (dx%n, (y0+dy)%n)

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

那么現(xiàn)在給你某個坐標（x，y），要怎么算出他屬于哪一組循環(huán)的呢

根據(jù)等式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

memory limit per test

input

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 #include #include #include #include #include #include #include #include #include #include #include #include 

聲明：本網(wǎng)頁內容旨在傳播知識，若有侵權等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com