PRESENT - Quà tặng crush

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 0.05s
Giới hạn bộ nhớ: 256M
Tác giả:
aprocoder
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, 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ập hà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”, Anh muốn tặng quà cho crush nhiều ngày liên tục nhất có thể.

Tính số ngày liên tiếp mà Anh có thể mua quà cho crush mình.

Input

Dữ liệu bao gồm nhiều bộ test:

  • Dòng đầu chứa một số nguyên T là số lượng test (1 ≤ T ≤ ~ 10^4 ~).
  • T dòng tiếp theo, mỗi dòng chứa 2 số nguyên M, N (1 ≤ 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

Problem source: Beginner Free Contest 31

Bình luận

Please read the guidelines before commenting.


  • 1
    mducc  đã bình luận lúc 2, Tháng 6, 2026, 13:17 ← sửa 2

    Quy luật: Để tối ưu số ngày tặng quà dài nhất, ta luôn ưu tiên chọn mua xoay vòng 2 món rẻ nhất là món giá 1 và món giá 2 (tốn 3 đồng cho mỗi chu kỳ 2 ngày).

    Trường hợp m = 1: Chỉ có đúng 1 món giá 1 nên không thể mua liên tục quá 1 ngày nên Kết quả luôn là 1

    Trường hợp m >= 2: Chia số tiền thành các nhóm 3 đồng để lấy số ngày (ans = (n / 3) * 2), nếu còn dư tiền (n%3 >= 1) thì cộng thêm 1 ngày vì đủ mua tiếp món giá 1

    code tham khảo (c++) 

    #include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        long long m, n;
        cin >> m >> n;
        if (m == 1) {
            if (n >= 1) cout << 1 << "\n";
            else cout << 0 << "\n";
            continue;
        }
        long long ans = 0;
        long long k = n / 3;
        long long du = n % 3;
        ans = k * 2;
        if (du >= 1) ans++;
        cout << ans << "\n";
    }
}