trang chủ / bài tập / paychnge

Thanh toán đúng tiền

Bạn có $a$ đồng xu mệnh giá $n$ và $b$ đồng xu mệnh giá $1$ . Bạn luôn thanh toán đúng bằng tiền lẻ — tức là tổng giá trị các đồng xu bạn đưa ra phải bằng đúng số tiền cần trả.

Cho số tiền $S$ . Hãy xác định xem có tồn tại hai số nguyên $x$ và $y$ thoả mãn $0 \leq x \leq a$ , $0 \leq y \leq b$ và $x \cdot n + y = S$ hay không.

Bạn phải trả lời $q$ truy vấn độc lập.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $q$ — số truy vấn.
Mỗi truy vấn được cho trên một dòng gồm bốn số nguyên $a$ , $b$ , $n$ , $S$ .

Dữ liệu ra

Với mỗi truy vấn, in ra YES nếu tồn tại $x$ và $y$ thoả mãn yêu cầu, in ra NO nếu không. Bạn có thể in chữ in hoa hoặc in thường tuỳ ý.

Ràng buộc

$1 \leq q \leq 10^{4}$
$1 \leq a, b, n, S \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 1 2 3 4 1 2 3 6 5 2 6 27 3 3 5 18	YES NO NO YES	Truy vấn 1: $x = 1, y = 1$ cho $1 \cdot 3 + 1 = 4$ . Truy vấn 2: không có cách nào. Truy vấn 3: $x \leq 4$ thì cần $y \geq 3$ , nhưng $b = 2$ . Truy vấn 4: $x = 3, y = 3$ cho $3 \cdot 5 + 3 = 18$ .
1 16 2 3 55	NO	Lấy nhiều nhất $16$ đồng mệnh giá $3$ được $48$ , còn thiếu $7$ nhưng chỉ có $2$ đồng mệnh giá $1$ .
1 500 1000 600 131	YES	$S = 131 < 600$ , dùng $x = 0$ và $y = 131$ .

Bình luận

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

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 2,00một phần

Giới hạn thời gian 1.0s

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig