Chuồng Trống

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John vận hành một chuồng bò hình tròn với $N$ ô chuồng được đánh số từ $0$ đến $N - 1$ , trong đó ô $N - 1$ nằm kề ô $0$ . Mỗi ngày, khi những con bò trở về chuồng, mỗi con đều có một ô chuồng yêu thích. Nếu ô chuồng yêu thích đã bị chiếm, con bò sẽ di chuyển theo chiều tăng dần của số hiệu ô (quay vòng từ ô $N - 1$ về ô $0$ ) cho đến khi tìm được ô trống.

Dãy ô chuồng yêu thích của các con bò được mô tả qua $K$ nhóm. Mỗi nhóm gồm bốn số $X$ , $Y$ , $A$ , $B$ mô tả $X \cdot Y$ con bò: có $X$ con bò yêu thích mỗi ô trong dãy $f (1), f (2), \dots, f (Y)$ , trong đó $f (i) = (A \cdot i + B) mod N$ .

Các con bò lần lượt tìm chuồng theo thứ tự: nhóm 1 trước, rồi nhóm 2, v.v. Trong mỗi nhóm, bò yêu thích $f (1)$ vào trước (tất cả $X$ con), rồi đến bò yêu thích $f (2)$ , v.v.

Tổng số bò luôn nhỏ hơn $N$ , nên sau khi tất cả bò đã vào chuồng, sẽ luôn còn ít nhất một ô trống. Hãy tìm chỉ số nhỏ nhất của ô chuồng còn trống sau khi tất cả bò đã vào chuồng.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $K$ .
$K$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $X$ , $Y$ , $A$ , $B$ .

Dữ liệu ra

Một số nguyên duy nhất: chỉ số nhỏ nhất của ô chuồng còn trống.

Ràng buộc

$2 \leq N \leq 3 000 000$
$1 \leq K$
$0 \leq A, B \leq 10^{9}$
Tổng số bò (tổng các $X \cdot Y$ ) $\leq N - 1$

Ví dụ

Input	Output	Giải thích
10 3 3 2 2 4 2 1 0 1 1 1 1 7	5	Nhóm 1: $f (1) = 6, f (2) = 8$ , mỗi ô 3 bò. Nhóm 2: $f (1) = 1$ , 2 bò. Nhóm 3: $f (1) = 8$ , 1 bò. Bò lần lượt chiếm các ô, ô trống nhỏ nhất còn lại là 5.
15 5 1 1 13 6 1 4 15 1 1 2 4 18 1 1 14 9 1 1 15 17	0	Sau khi tất cả bò vào chuồng, ô 0 vẫn trống và là ô trống có chỉ số nhỏ nhất.

Bình luận

Không có bình luận tại thời điểm này.