Bánh trung thu

Xem PDF

Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trung thu đang đến gần, chú Ba muốn chuẩn bị thật nhiều bánh trung thu để tặng cho các em nhỏ ở vùng sâu vùng xa. Vì đường xá xa xôi nên chú Ba cần đóng gói cẩn thận rồi mới vận chuyển. Hiện tại chú có có \(n\) gói bánh, \(k\) vách ngăn và rất nhiều hộp. Biết rằng nếu đặt \(x\) \((x \ge 0)\) vách ngăn vào nó, ta sẽ nhận được một hộp được chia làm \(x+1\) phần.

Chú Ba không muốn hộp có quá nhiều vách ngăn nên chú giới hạn một hộp không được chia thành quá \(a\) phần. Mặt khác, chú cũng không muốn bỏ quá \(b\) gói bánh vào một phần của hộp. Vì số lượng bánh là khá nhiều nên chú muốn nhờ bạn giúp xác định số lượng hộp tối thiểu cần dùng để bỏ hết tất cả bánh trung thu vào hộp là bao nhiêu.

Input

  • Một dòng duy nhất chứa bốn số nguyên \(a\), \(n\), \(k\)\(b\) (\(2 \le a \le 1000\), \(1 \le n, k, b \le 1000\)).

Output

  • In ra một số nguyên duy nhất là kết quả của bài toán.

Example

Test 1

Input
2 11 3 3
Output
2
Note

Ta có thể chia như sau:

  • Bỏ một vách ngăn vào hộp thứ nhất. Bây giờ hộp thứ nhất có hai phần và ta có thể cho \(3\) gói bánh vào mỗi phần. Khi đó hộp thứ nhất chứa \(6\) gói bánh.
  • Bỏ một vách ngăn vào hộp thứ hai. Khi đó hộp thứ hai có hai phần, ta có thể cho \(3\) gói bánh vào phần thứ nhất và \(2\) gói bánh vào phần thứ hai.

Cuối cùng ta đã bỏ được tất cả \(11\) gói bánh vào \(2\) hộp.


Bình luận


  • 0
    2009_phamduc 9:45 p.m. 15 Tháng 3, 2024

    pragma GCC optimize("O2")

    pragma GCC target("popcnt,lzcnt,bmi,bmi2,abm")

    include <bits/stdc++.h>

    define stmgdht signed main()

    define ln '\n';

    define ll long long

    define str string

    define fir first

    define sec second

    define pb push_back

    define freopen(name) if(fopen(name".INP","r"))

    define ALL(x) (x).begin(),(x).end()

    define phamduc ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);

    define TIME (1.0*clock()/CLOCKS_PER_SEC)

    define OFFSET 2000004

    using namespace std;
    ll kl,sum,n,dem,res,f[50005];
    int x,k,a[50005];
    bool check( int a,int b,int c){
    return a+b>c;
    }
    bool kt( int a,int b,int c){
    return aa+bb>cc;
    }
    void solve(){
    int a,n,k,b; cin>>a>>n>>k>>b;
    int l=a-1,m=k%(a-1);
    for ( int i=1;i<=k/l;i++){
    res+=b
    (a);
    if(res>=n){
    cout <<i<<' ';
    return ;
    }
    }
    if(k%l!=0)res+=(m+1)*b;
    if(res>=n){
    cout <<k/l+1; return ; } ll f=n-res; for ( int i=1;;i++){ res+=b; if(res>=n){
    if(k%l!=0){
    cout <<k/l+1+i;
    return ;
    }
    else{
    cout <<k/l+i;
    return ;
    }
    }
    }

    }
    stmgdht
    {
    freopen("cau5");
    phamduc
    int t=1;
    while(t--){
    solve();
    cout <<ln;
    }
    }
    code ac neu ban can tham khao khi van chua hieu huong dan giai