Help needed in Packing Rectangles (Binary Search)

→ Обратите внимание

До соревнования
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
29:40:48
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	Benq	3676
2	jiangly	3670
3	Kevin114514	3657
4	maroonrk	3355
5	Um_nik	3353
6	squareOf105	3346
7	tourist	3343
8	strapple	3324
9	heuristica	3322
10	jiangbowen	3291

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
5	Um_nik	142
6	Errichto	139
7	adamant	137
8	BledDest	135
9	maroonrk	133
10	qwexd	130

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя coder__12345

Help needed in Packing Rectangles (Binary Search)

Автор coder__12345, история, 3 года назад, По-английски

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 года назад
4

Комментарии (2)

Показать архивные | Написать комментарий?

coder__12345

3 года назад, скрыть # |

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

→ Ответить

vstiff

3 года назад, скрыть # |

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.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 16.10.2026 11:54:13 (g2).

Десктопная версия, переключиться на мобильную.

При поддержке