SHOPPING - Mua đồ
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Một cửa hàng A ban đầu có M món hàng đánh số từ 1 đến M. Món hàng thứ i có giá tiền là i.Cửa hàng này có một điểm đặc biệt là không có hàng trong kho và cần mất một ngày để nhậphàng mới, tức là nếu một món hàng i được bán vào ngày hôm qua, thì đến tận ngày mai mới cóthể bán tiếp món hàng giá tiền tương ứng.Sau nhiều thời gian dành dụm, Anh đã để dành được N đồng vàng. Anh quyết định sẽ dùng Nđồng vàng, mỗi ngày mua quà ở cửa hàng A tặng cho crush của mình. “Mưa dầm thấm lâu”, Anhmuốn tặng quà cho crush nhiều ngày liên tục nhất có thể. Hãy tính số ngày liên tiếp mà Anh có thể mua quà cho crush mình.
Input
- Dòng đầu chứa một số nguyên T là số lượng bộ test (1 < t < ~10^4~)
- T dòng tiếp theo, mỗi dòng chứa hai số nguyên M,N (0< M < N < ~10^9~)
Output
- Gồm T dòng, mỗi dòng chứa số nguyên là số ngày liên tục nhiều nhất mà Anh có thể mua quàtặng cho crush ứng với mỗi test case.
Sample
Input #1
3
1 1
2 2
3 3
Output #1
1
1
2
Bình luận
Ý tưởng: Nếu cửa hàng có đúng 1 món hàng thì chỉ mua được tối đa 1 ngày liên tục
Nếu cửa hàng có từ 2 món trở lên thì ta cứ mua món có giá tiền là 1, sau đó mua món có giá tiền là 2, rồi lại mua món có giá tiền 1 (lúc này cửa hàng đã nhập lại), sau đó lại mua 2 (cửa hàng đã nhập lại)...vv.
Khi đó số ngày liên tục tối đa của ta sẽ dài nhất. Ta được các cặp 1, 2, 1, 2 so le nhau. Đếm số cặp (1, 2) sẽ ra kết quả là số ngày (Chú ý trường hợp thừa ra 1 hoặc 2).
bài bày khó :((