↵
<spoiler summary="Spoiler">↵
...↵
</spoiler>↵
↵
↵
My Intutiton:↵
↵
For every size of buffer, we will try to calculate the length of cycle in which the buffer is filled and it is emptied. Calculate the total number of such cycles and if it is = min number of cycles, then it can be the possible buffer length.I used binary search to find such cycle. ↵
↵
Min Number of cycles = total bandwidth/max bufher length↵
↵
max buffer length=p*d↵
↵
<spoiler summary="
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
// #include <ext/pb_ds/assoc_container.hpp>↵
// #include <ext/pb_ds/tree_policy.hpp>↵
// using namespace __gnu_pbds;↵
// #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>↵
↵
template <typename T> istream& operator >> (istream& in, vector<T>& v) { for (auto &it:v) in >> it; return in; }↵
template <typename T> ostream& operator << (ostream& os, const vector<T>& v) { for (auto &it:v) os << it << " "; return os; }↵
template <typename T1, typename T2> istream& operator >> (istream& in, pair<T1,T2>& p) { cin >> p.first >> p.second; return in; }↵
template <typename T1, typename T2> ostream& operator << (ostream& os, const pair<T1,T2>& p) { cout << p.first << " " << p.second; return os; }↵
template <typename T1, typename T2> void maxn(T1& a, T2 b) { a = max(a,b); }↵
template <typename T1, typename T2> void maxx(T1& a, T2 b) { a = max(a,b); }↵
↵
#define int long long int↵
#define ll int↵
#define double long double↵
#define pb push_back↵
#define ff first↵
#define ss second↵
#define all(v) v.begin(),v.end()↵
#define allr(v) v.rbegin(),v.rend()↵
#define sz(v) (int)v.size()↵
#define deb(x) cout<<#x<<"="<<x<<endl;↵
#define pii pair<int,int>↵
#define vi vector<int>↵
↵
const int mod = 1e9+7;↵
const int mod2 = 998244353;↵
const double PI = 3.1415926535897932384626433832795;↵
const int INF = 0xFFFFFFFFFFFFFFFLL;↵
↵
int find_cycle(int d,int b,int t,int p,int mid)↵
{↵
int buffer_size=mid;↵
int time_to_fill=(buffer_size+d-1)/d;↵
int curr_consumption_time=buffer_size/(b-d);↵
int den=(time_to_fill+curr_consumption_time)*d;↵
int num=t*b;↵
int curr_cycles=(num+den-1)/den;↵
return curr_cycles;↵
}↵
↵
void solve()↵
{↵
int d,b,t,p; cin>>d>>b>>t>>p;↵
int tot_bytes=b*t;↵
int consumption_time=d*p/(b-d);↵
int den=(p+consumption_time)*d;↵
int tot_cycles=(tot_bytes+den-1)/den;↵
int l=0,r=p*d+10;↵
while(l+1<r)↵
{↵
int mid=(l+r)>>1;↵
int curr_cycles=find_cycle(d,b,t,p,mid);↵
if(curr_cycles>tot_cycles) l=mid;↵
else r=mid;↵
}↵
cout<<r<<endl;↵
}↵
↵
int32_t main() {↵
// #ifndef ONLINE_JUDGE↵
freopen("video.in", "r", stdin);↵
freopen("video.out", "w", stdout);↵
// #endif↵
cin.tie(0)->sync_with_stdio(0);↵
int tc=1;↵
// cin>>tc;↵
while(tc--) solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
It gives WA on tc 7, any help would be deeply appreciated.↵
