Help needed in Packing Rectangles (Binary Search)

coder__12345's blog

By coder__12345, history, 3 years ago, In English

Problem Link: https://codeforces.me/edu/course/2/lesson/6/2/practice/contest/283932/problem/A

Accepted Code

#include<bits/stdc++.h>

using namespace std;

#define int long long


int a,b,n;

bool isfit(int mid){
	return (mid/a)*(mid/b)>=n;
}

signed main(){
	cin>>a>>b>>n;
	int l=0,r=1;
	while(isfit(r)==false){
		r*=2;
	}
	while(r-l>1){
		int mid=l+(r-l)/2;
		if(isfit(mid)){
			r=mid;
		}
		else{
			l=mid;
		}
	}
        if(isfit(l)) cout<<l<<endl;
        else cout<<r<<endl;
}

Not Accepted Code

#include<bits/stdc++.h>

using namespace std;

#define int long long


int a,b,n;

bool isfit(int mid){
	return (mid/a)*(mid/b)>=n;
}

signed main(){
	cin>>a>>b>>n;
	int l=0,r=1;
	while(isfit(r)==false){
		r*=2;
	}
	while(r-l>1){
		int mid=l+(r-l)/2;
		if(isfit(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
        cout<<l<<endl;
}

The only change in the two code is the value being assigned to l, when i normally implement binary search i use it like in the not accepted one but why in this problem its giving wrong answer?

coder__12345
3 years ago
4

Comments (2)

Show archived | Write comment?

coder__12345

3 years ago, hide # |

Auto comment: topic has been updated by coder__12345 (previous revision, new revision, compare).

→ Reply

vstiff

3 years ago, hide # |

First code finds point where isfit changes 'sign', if isfit(l) before running BS was = false you don't need to check it anymore, answer is always r. Second code is kind of mix with no clear idea behind it. It should work after changing to while r>l, but 1st is just a lot better concept.

btw mid = (l+r)/2 saves some keystrokes.

→ Reply