include &lt;bits/stdc++.h&gt;

5 weeks ago, # |

man , i dont know why my c dont is correct , aaaaa

→ Reply

5 weeks ago, # ^ |

after the contest i post my c here

→ Reply

fusheng0805

5 weeks ago, # ^ |

hope your answer

→ Reply

5 weeks ago, # ^ |

the logic is correct but need be more faster, i hate tle . ~~~~~ //this is code

include <bits/stdc++.h>

using namespace std;

define f first

define s second

typedef long long ll;

int main(){ int q; cin >> q;

queue<pair<ll,ll>> snakes;
ll global = 0;

while(q--){
    int tipo; cin >> tipo;

    if(tipo == 1){
        ll l; cin >> l;
        if(snakes.empty()){
            snakes.push({0,l});
        }else{
            snakes.push({snakes.back().f + snakes.back().s,l});
        }
    }else if(tipo == 3){
        int k; cin >> k;
        queue<pair<ll,ll>> copia = snakes;

        for(ll i = 1; i < k; i++){
            copia.pop();
        }
        cout << copia.front().f  - global << endl;
    }else{
        int m = snakes.front().s;
        snakes.pop();
        global += m;
    }
}

} ~~~~~

→ Reply

Nitter

5 weeks ago, # ^ |

Ey you dont have to make a copy of the queue, you can access in O(1) like a vector, just with queue[k-1] that's why u are having TLE

→ Reply

https://atcoder.jp/contests/abc389/submissions/61814693

5 weeks ago, # ^ |

really , how i do that ?

→ Reply

Nitter

5 weeks ago, # ^ |

← Rev. 2 →

cout << copia[k-1] — global << endl; Just like that, in case you have questions u can check my code :) CODE

→ Reply

wiuerhtioquwhtewqurtlkad

5 weeks ago, # |

← Rev. 2 →

after contest someone explain solution for D.

→ Reply

da_ke

5 weeks ago, # ^ |

← Rev. 9 →

Sorry for my poor English.

Consider line

$$$x=1.5,x=2.5,x=3.5,\cdots,x=R+0.5$$$

find the intersection of the lines with the circle and calc the total of the rectangle.

U'd better use Rectangular Coordinates. It can solve it quickly.

By the way, the problem is very similar to abc191_d.

→ Reply

wiuerhtioquwhtewqurtlkad

5 weeks ago, # ^ |

Thanks

→ Reply

abhijitmanna912001

5 weeks ago, # |

After contest, anyone explain approach for D and F, getting stuck in TLE :(

→ Reply

hydra_cody

5 weeks ago, # ^ |

You can go at max r distance from the center in any direction.So, Move across the x-axis from [-r to r] and find the corresponding max y above[0,r]and lowest y below [-r,0] with binary search. 61834784

→ Reply

_Artist__

5 weeks ago, # ^ |

Can also use the equation of a circle. Fix values of x like 0.5,1.5,.... and just calculate the y . Since its a circle its symmetrical so you can just multiply by 2

→ Reply

introMANN

5 weeks ago, # ^ |

void solve()
{
	ll r;
	cin >> r;

	ll n1 = sqrt(1.0 * r * r - 0.5 * 0.5) - 0.5;
	ll n2 = (1.0 * r) / sqrt( 2.0) - 0.5;

	cout << 4 * (n1 + n2) + 1 << nl;
}

What's wrong with this solution ?

→ Reply

_Artist__

5 weeks ago, # ^ |

I dont get what you are trying to do mate.

I used the equation (x*x+y*y=r*r) for circles, we know r , if we iterate over x from 0.5 we can find the maximum y for which this is valid. I start from the second square , go till the end , multiply this by 2 and then finally add the middle column once.

Code

// Problem: D - Squares in Circle
// Contest: AtCoder - Toyota Programming Contest  2025（AtCoder Beginner Contest 389)
// URL: https://atcoder.jp/contests/abc389/tasks/abc389_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 2025-01-18 17:52:30
// Submission by : _o7_

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll_max 1e18
#define endl "\n"
#define MOD 1000000007
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define o7 {ios_base::sync_with_stdio(0); cin.tie(0);}
#define pb push_back
#define mp make_pair
#define it(x) (x).begin(), (x).end()
#define rit(x) (x).rbegin(), (x).rend()
using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int32_t main(){
	o7
    int t;
    // cin>>t;
    t=1;
    while(t--){
        int r;
        cin>>r;
        int val=r*r;
        int ans=0;
        for(double i=1.5;i<r;i+=1)
        {
        	double vs=i*i;
        	double temp=val-vs;
        	double sq=sqrt(temp);
        	sq-=0.5;
        	ans+=max(0LL,(int)sq*2+1);
        }
	        ans*=2;
	        double vs=(0.5)*(0.5);
        	double temp=val-vs;
        	double sq=sqrt(temp);
        	sq-=0.5;
        	ans+=max(0LL,(int)sq*2+1);
        cout<<ans<<endl;
    }
    
    return 0;
}

→ Reply

introMANN

5 weeks ago, # ^ |

I'm trying to get the maximum count of squares above the root square. With symmetry , we can get the count for the 4 directions , similar logic for diagonal squares .

→ Reply

_Artist__

5 weeks ago, # ^ |

Oh ok , well im also doing the same thing i just caluclate apart from the base line as it only occurs once so what i do is calculate from above multipy it by 2 then add. After this i multiply this value by 2 for the whole circle then i manually add the center line which would have occured only once

→ Reply

UP84

5 weeks ago, # |

I loved problem E,gave D an hour and still can't do it,i'm really bad at geometry.

→ Reply

MUI1344

5 weeks ago, # ^ |

Can you share your approach after the contest?

→ Reply

shantanugupta2907

5 weeks ago, # ^ |

For D, first I calculated in first quadrant and than on the axes.

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include <debug.h>
#else
#define debug(...)
#endif
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
#define py cout << "YES\n";
#define all(x) begin(x), end(x)
#define pm cout << "-1\n";
#define pn cout << "NO \n";
#define fo(i, n) for (long long i = 0; i < n; i++)
#define fr(i, n) for (ll i = n - 1; i >= 0; i--)
#define cin(a, n) \
    vll a(n);     \
    fo(i, n) { cin >> a[i]; }
#define print_v(a)   \
    for (auto i : a) \
        cout << i << " ";
#define printv(a)         \
    for (auto i : a)      \
        cout << i << " "; \
    cout << endl;
#define double long double
void solve()
{

    double R;
    cin >> R;
    ll cnt = 0;
    auto isInside = [&](double x, double y) -> bool
    {
        return (x * x + y * y <= R * R);
    };
    for (double i = 1; i <= floor(R); i += 1)
    {
        double maxi = (R * R) - (i + 0.5) * (i + 0.5);
        if (maxi < 0)
            continue;
        maxi = sqrt(maxi);
        maxi = maxi - 0.5;
        debug(floor(maxi), i);
        cnt += maxi;
    }
    ll ans = cnt * 4;
    cnt = -1;
    double i = 0;
    for (double j = -R; j <= R; j += 1)
    {
        if (isInside(i - 0.5, j - 0.5) &&
            isInside(i - 0.5, j + 0.5) &&
            isInside(i + 0.5, j - 0.5) &&
            isInside(i + 0.5, j + 0.5))
        {
            // debug(i, j);
            cnt++;
        }
    }
    double j = 0;
    for (i = -R; i <= R; i += 1)
    {
        if (isInside(i - 0.5, j - 0.5) &&
            isInside(i - 0.5, j + 0.5) &&
            isInside(i + 0.5, j - 0.5) &&
            isInside(i + 0.5, j + 0.5))
        {
            // debug(i, j);
            cnt++;
        }
    }
    cout << ans + cnt << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    ll t;
    t = 1;
    while (t--)
        solve();
    return 0;
}

→ Reply

ibrm

5 weeks ago, # ^ |

for D you could just oeis it

→ Reply

StealthBlack0_o

5 weeks ago, # |

Looking at the number of ACs on Problem D, it was really disappointing that I couldn’t come up with the solution. Can anyone explain the solution to Problem D?

→ Reply

alpha1215

5 weeks ago, # ^ |

you can binary search for $$$y$$$ for each $$$x$$$

→ Reply

StealthBlack0_o

5 weeks ago, # ^ |

can you share your submission link

→ Reply

alpha1215

5 weeks ago, # ^ |

→ Reply

lueagzil

5 weeks ago, # ^ |

ll f(ll rr, ll i)
{
	ll ans = 0;
	ll l = 0, r = rr;
	ll tar = 2 * rr * rr - 1;
	while (l <= r)
	{
		ll mid = (l + r) / 2;
		if ((mid + mid * mid + i + i * i) * 2 <= tar)
		{
			ans = mid;
			l = mid + 1;
		}
		else
		{
			r = mid - 1;
		}
	}
	return ans;
}

void solve(int cas)
{
	ll r;
	std::cin >> r;
	ll ans = 0;
	ll x1 = r * 2 - 1;
	for (int i = 1; i <= r - 1; i++)
	{
		ll tans = f(r, i);
		// std::cout << i << " " << tans << "\n";
		ans += 2 * tans + 1;
	}
	ans *= 2;
	ans += x1;
	print(ans);
}

→ Reply

SandyNyaN

5 weeks ago, # ^ |

This isn't necessary. After dividing the circle into four equal parts according to the direction of the square's edges, we find that y is monotonically decreasing with respect to x. https://atcoder.jp/contests/abc389/submissions/61805834

→ Reply

RituRaj.12797

5 weeks ago, # ^ |

did same

had a pretty short solution just iterated on neighboring distance and calculated possible number of square by calculating the xth square which will be last for this horizontal distance


int yc(int r, int i) {

    long double of = 0.5*1.0;

    long double is = i*1.0+of;
    long double res = r*r*1.0 - is*is*1.0;

    long double sq = sqrt(res);

    long double x = sq - of*1.0;

    // x = 0.99999999999999;
    int z = pFloor(x);
    // cout<<z<<"\n";

    return z;

}


void solve() {
    int r;
    cin>>r;

    int ans =  0;

    for(int i = -r + 1 ; i < r ; i++) {

        int x = yc(r,abs(i));
        ans += 2*(x) + 1;
        
    }

    // cout<<yc(2,1)<<"\n";

    cout<<ans<<"\n";


}

→ Reply

introMANN

5 weeks ago, # ^ |

What wrong with this mathematical solution ?

void solve()
{
	ll r;
	cin >> r;

	ll n1 = sqrt(1.0 * r * r - 0.5 * 0.5) - 0.5;
	ll n2 = (1.0 * r) / sqrt( 2.0) - 0.5;

	cout << 4 * (n1 + n2) + 1 << nl;
}

Can anyone point out ?

→ Reply

34z12000

5 weeks ago, # |

E was a bit painful

→ Reply

Igor_Parfenov

5 weeks ago, # |

+15

My thought process on $$$F$$$.

Bla
Bla
Bla
Implement a segment tree with operations $$$X$$$.

"Maybe I can avoid it? Let's try another idea."

Blo
Blo
Blo
Implement a segment tree with operations $$$Y$$$.

"Try again."

Blu
Blu
Blu
Implement a segment tree with operations $$$Z$$$.

→ Reply

MUI1344

5 weeks ago, # ^ |

Did you solve it using a segment tree or??

→ Reply

Igor_Parfenov

5 weeks ago, # ^ |

I didn't solve it. Not because, ahem-ahem, I don't know segment tree. Certainly.

→ Reply

MUI1344

5 weeks ago, # ^ |

Lol

→ Reply

NonEuclideanNerd

5 weeks ago, # |

Has anyone solved problem E using Lagrange multipliers?

→ Reply

nihalgeorge01

5 weeks ago, # ^ |

← Rev. 2 →

I tried $$$a_i = \lfloor\sqrt{\frac{M}{NP_i}}\rfloor$$$. This gets $$$\sum_{i=1}^{N}a_{i}^{2}P_{i}$$$ close to $$$M$$$, but I wasn't able to figure out how to use the leftover budget caused by the floor function.

Using at most 1 more of each price wont be enough, since the rounding from a large price could allow multiple smaller prices to work (at least this made me fail the second sample). Any ideas would be great

→ Reply

Lance0

5 weeks ago, # |

D Major Spoilers

→ Reply

lueagzil

5 weeks ago, # |

Solving F by performing binary search on segment tree. Narrowly pass with 800+ms. When calculating the complexity during contest, always worrying about TLE

→ Reply

cosmosking

5 weeks ago, # |

how e

→ Reply

Fox-516

5 weeks ago, # |

← Rev. 6 →

With Problem E

I change the value of inf in following code from 1e18+1 to 2e18+1 will result in different answer. Why this happend

#include <bits/stdc++.h>
using namespace std;
typedef __uint128_t ll;
// typedef long long ll;
unsigned long long n, m;
vector<unsigned long long> a;
const long double inf = 1e18+1;
ll calcnt(ll p, ll limit)
{
    return (limit / p + 1) / 2;
}
ll calcost(ll limit)
{
    ll ans = 0;
    for (auto x : a)
    {
        ll cnt = calcnt(x, limit);
        if (x * cnt * cnt > inf)
            return inf;
        ans += cnt * cnt * x;
        if (ans > inf)
            return inf;
    }
    return ans;
}
unsigned long long cal(ll limit)
{
    ll ans = 0;
    for (auto x : a)
    {
        ll cnt = calcnt(x, limit);
        ans += cnt;
    }
    return ans;
}
int main()
{
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    ll l = 0, r = 1e18;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (calcost(mid) > m)
            r = mid;
        else
            l = mid + 1;
    }
    unsigned long long ans = cal(l - 1);
    m -= (unsigned long long)calcost(l - 1);
    cout << ans + m / (unsigned long long)l << endl;
}

→ Reply

falcZhang

5 weeks ago, # |

E: only WA on 21,need help
//this is code
using namespace std;
int main()
{
    int n;
    unsigned long long m;
    scanf("%d%lld", &n, &m);
    long long s = 0;
    long long ans = 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    unsigned long long l = 0, r = m, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        __int128_t sum = 0;
        for (int i = 1; i <= n; ++i) {
            long long t = (mid + a[i]) / (2 * a[i]);
            sum += (__int128_t)t * t * a[i];
        }
        if (sum <= m) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    long long res = m;
    for (int i = 1; i <= n; ++i) {
        long long t = (r + a[i]) / (2 * a[i]);
        ans += t;
        res -= t * t * a[i];
    }
    ans += res / (r + 1);
    printf("%lld\n", ans);
    return 0;
}

→ Reply

falcZhang

5 weeks ago, # |

E: only WA on 21,need help

//this is code using namespace std; int main() { int n; unsigned long long m; scanf("%d%lld", &n, &m); long long s = 0; long long ans = 0; vector a(n + 1); for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); } unsigned long long l = 0, r = m, mid; while (l <= r) { mid = (l + r) / 2; int128_t sum = 0; for (int i = 1; i <= n; ++i) { long long t = (mid + a[i]) / (2 * a[i]); sum += (int128_t)t * t * a[i]; } if (sum <= m) { l = mid + 1; } else { r = mid — 1; } } long long res = m; for (int i = 1; i <= n; ++i) { long long t = (r + a[i]) / (2 * a[i]); ans += t; res -= t * t * a[i]; } ans += res / (r + 1); printf("%lld\n", ans); return 0; } ~~~~~

→ Reply

skill_Issued

5 weeks ago, # |

Can someone explain the logic for E ? How is binary search applicable ?

→ Reply

stostap

5 weeks ago, # ^ |

it's pretty common trick: You need to pack the backpack with some items. And your task is to put the maximum number of items there. So logically, you'll put the cheapest items. So you perform the BS over the price of last item you can put there.

→ Reply

5 weeks ago, # ^ |

Hey, Can you please look at my solution, i think have done the same thing but i am not getting right answer, If possible please point out my mistake.

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];
    int s=0,e=1^18;
    int ans=-1;
    int pnt=0;
    int ss=0;
    while(s<=e){
        int mid=(e-s)/2+s;
        int sum=0;
        int cnt=0;
        for(int i=0; i<n; i++){
            int k=floor(sqrt(double(mid)/double(a[i])));
            sum+=(k*k*a[i]);
            cnt+=k;
        }
        if(sum<=m){
            ans=mid;
            ss=sum;
            pnt=cnt;
            s=mid+1;
        }
        else{
            e=mid-1;
        }
    }
    // cout<<pnt<<endl;
    // cout<<ans<<endl;
    //  cout<<m<<' '<<ss<<' '<<endl;
    pnt+=(m-ss)/(ans+1);
    cout<<pnt<<endl;

}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

→ Reply

rakim_

5 weeks ago, # ^ |

← Rev. 2 →

I understood most of the solution but I still don't get how dividing the remaining money by l+1 gives the right number of l+1 priced items.
How can we be sure that there are (money_left)/l+1 items available for purchase?

→ Reply

https://atcoder.jp/contests/abc389/submissions/61842706

5 weeks ago, # ^ |

Thanks for showing concern on this, If there would be no i+1 items then binary search would have given i+1 as answer, so this means there are some i+1 items out there and also we can’t purchase all of them if we could then again we won't be having i as our binary search answer, it would be i+1, as we can buy all the products having price<=(i+1). So to do partial purchase rem_budget/(i+1) is i guess good. If you find any fallacy kindly report.

→ Reply

rakim_

5 weeks ago, # ^ |

rem_budget/(i+1) is i guess good

how do you know if your guess is actually correct(?). I wanted a more mathy proof if possible

→ Reply

Nxchman

5 weeks ago, # |

did pretty poorly, only solved problem A but was really close to solving problem B and C.

→ Reply

Nxchman

5 weeks ago, # |

I got TLE for problem C

→ Reply

da_ke

5 weeks ago, # ^ |

Try to do it with queue and prefix sum.

→ Reply

Nxchman

5 weeks ago, # ^ |

thanks!

→ Reply

EricWan

5 weeks ago, # |

E > F ?

But I still solve E :)

→ Reply

dinhvietcuong

5 weeks ago, # |

Problem E can be ACed using the Cauchy–Schwarz inequality with real numbers, followed by removing sub-optimal buys using a heap.

→ Reply

hidden_i

5 weeks ago, # |

For problem E, why does solution says: "as well as as many items of price x+1 as possible."?

Why do we need to also take those items whose cost is (x + 1)?

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

We will take those, if there are 5 such items worth (k+1) each, and we have budget left of 2k+3, after buying all items having worth less than or equal to k, we will buy two (k+1) item also in order to maximize our output.

→ Reply

hidden_i

5 weeks ago, # ^ |

Thanks

Follow-up: If budget allows picking up say all items worth (x + 1), then why shall we not proceed to also pick higher rated items e.g. (x + 2)?

→ Reply

5 weeks ago, # ^ |

In that case, our binary search would yield us (x+1) not (x), if we can pick all x+1 item, moreover this also implies there will be indeed some items of(x+1) that will be out of our budget, if not our binary search would given us x+1. I hope this explains your query.

→ Reply

ugabugaasd

5 weeks ago, # ^ |

← Rev. 3 →

Edit: how do we ensure we will have enough k+1 items? For e.g. if we have the remaining sum worth 2k+2, how can we ensure that there will we at least 2 items worth exactly (k+1)

→ Reply

5 weeks ago, # |

Hi, I solved 5th question, this is my code, can someone point out what is my mistake?

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];
    int s=0,e=1^18;
    int ans=-1;
    int pnt=0;
    int ss=0;
    while(s<=e){
        int mid=(e-s)/2+s;
        int sum=0;
        int cnt=0;
        for(int i=0; i<n; i++){
            int k=floor(sqrt(double(mid)/double(a[i])));
            sum+=(k*k*a[i]);
            cnt+=k;
        }
        if(sum<=m){
            ans=mid;
            ss=sum;
            pnt=cnt;
            s=mid+1;
        }
        else{
            e=mid-1;
        }
    }
    // cout<<pnt<<endl;
    // cout<<ans<<endl;
    //  cout<<m<<' '<<ss<<' '<<endl;
    pnt+=(m-ss)/(ans+1);
    cout<<pnt<<endl;

}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Can someone please find mistake.

→ Reply

5 weeks ago, # ^ |

it's failing 2nd sample test case, if it is possible to explain how answer is 53 it will be helpful too.

→ Reply

5 weeks ago, # ^ |

k*k*a[i] is the total price of k products, the price of the kth product should be (2*k-1)*a[i].

→ Reply

Ndot

4 weeks ago, # ^ |

I am stuck in same doubt , I dont understand why calculating using sqrt is wrong. for checking how many k satisfy k^2*p[i] <= x .Why is this incorrect

→ Reply

4 weeks ago, # ^ |

For each i, check how many k_i satisfy (2*k_i-1)*a[i]<=x, and the sum of k_i^2*a[i] should be <= m.

→ Reply

Ndot

4 weeks ago, # ^ |

I was trying to bruteforce with a heap , I do understand that the price of each product would be (2*k_i-1)*a[i] but i dont really understand why is the above comment incorrect it doesnt feel trivial/intituitive to me . Can you explain maybe why the search space for total price wouldnt be monotonic or whats the flaw here

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

It seems that you don't understand the meaning of x here. x is the upper limit of the purchase price of each product. For product i, the purchase quantity k must satisfy (2*k_i-1)*a[i]<=x.

Our goal is to find the largest x so that m is enough to buy all products with a price not exceeding x, and the remaining money can be used to buy products with a price of x+1. This x can be found by binary search x and checking the total price sum(k_i^2*a[i])<=m

→ Reply

Ndot

4 weeks ago, # ^ |

I understand x represents cost of each unit of a[i], but i dont understand why we cant binary search on maximum cost we can spend at each index

→ Reply

b42late

5 weeks ago, # |

← Rev. 4 →

#include <bits/stdc++.h>
#define debug(x) cout << #x << ": " << x << endl
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

void solve() 
{
    int n;
    ll m;
    cin >> n >> m;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    auto calc = [&](ll x) {
        ll tot = 0, cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (v[i] > x) continue;
            ll k = (x - v[i]) / (2 * v[i]);
            cnt += k + 1;
            tot += (k + 1) * (k + 1) * v[i];
            if (tot > 1e18)
            {
                break;
            }
        }
        return make_pair(tot, cnt);
    };
    auto check = [&](ll x) {
        
        return calc(x).first <= m;
    };
    ll l = 0, r = m + 1;
    while (l < r)
    {
        ll mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << calc(l).second << endl;
}

int main() 
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

how to avoid overflow in Problem E, can anybody help me ?

→ Reply

AnuragV15

5 weeks ago, # |

Give clarity on this please.

In problem E. It calculated a price x(using binary search) for which we can by all items with price <=x. Such that total cost is <=M but there will be some remaining money. why is this remaining money used to buy as many items as possible of price x+1. (remaining_money)/(x+1). How we know if item priced x+1 will exist with surety and we can buy as many as possible.

→ Reply

skill_Issued

4 weeks ago, # ^ |

→ Reply