Bánh trung thu
Xem PDFTrung 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\) và \(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 3Output
2Note
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
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