**Problem 0144 : Empty Stalls**

Case Time Limit: 1000 ms Memory Limit: 65536 KB

Total Testdata Count: 11

AC/Submit: 7/24 AC/Submit Users: 2/4

[回到列表]

**題目敘述**

Farmer John's new barn consists of a huge circle of $N$ stalls ($2 \leq N \leq 3000000$), numbered $0 \sim N-1$, with stall $N-1 $being adjacent to stall $0$.

At the end of each day, FJ's cows arrive back at the barn one by one, each

with a preferred stall they would like to occupy. However, if a cow's

preferred stall is already occupied by another cow, she scans forward

sequentially from this stall until she finds the first unoccupied stall,

which she then claims. If she scans past stall $N-1$, she continues scanning

from stall $0$.

Given the preferred stall of each cow, please determine the smallest index

of a stall that remains unoccupied after all the cows have returned to the

barn. Notice that the answer to this question does not depend on the order

in which the cows return to the barn.

In order to avoid issues with reading huge amounts of input, the input to

this problem is specified in a concise format using $K$ lines ($1 \leq K \leq 10000$) each of the form:

$X$ $Y$ $A$ $B$

One of these lines specifies the preferred stall for $X \times Y$ total cows: $X$ cows

prefer each of the stalls $f(1) .. f(Y)$, where $f(i) = (Ai + B) \mod N$. The

values of $A$ and $B$ lie in the range $0 \sim 1000000000$.

Do not forget the standard memory limit of 64MB for all problems.

**輸入說明**

* Line 1: Two space-separated integers: $N$ and $K$.

* Lines 2..1+K: Each line contains integers $X$ $Y$ $A$ $B$, interpreted as

above. The total number of cows specified by all these lines

will be at most $N-1$. Cows can be added to the same stall by

several of these lines.

**輸出說明**

* Line 1: The minimum index of an unoccupied stall.

**範例輸入**

10 3 3 2 2 4 2 1 0 1 1 1 1 7

**範例輸出**

5

**備註**

There are 10 stalls in the barn, numbered 0..9. The second line of input

states that 3 cows prefer stall (2*1+4) mod 10 = 6, and 3 cows prefer stall

(2*2+4) mod 10 = 8. The third line states that 2 cows prefer stall (0*1+1)

mod 10 = 1. Line four specifies that 1 cow prefers stall (1*1+7) mod 10 =

8 (so a total of 4 cows prefer this stall).

**測資**

測資組A : 1~1 (1筆測資)，9 分

測資組B : 2~2 (1筆測資)，9 分

測資組C : 3~3 (1筆測資)，9 分

測資組D : 4~4 (1筆測資)，9 分

測資組E : 5~5 (1筆測資)，9 分

測資組F : 6~6 (1筆測資)，9 分

測資組G : 7~7 (1筆測資)，9 分

測資組H : 8~8 (1筆測資)，9 分

測資組I : 9~9 (1筆測資)，9 分

測資組J : 10~10 (1筆測資)，9 分

測資組K : 11~11 (1筆測資)，10 分