Codeforces 466 B. Wonder Room

2281 단어
폭력+난동
B. Wonder Room
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The start of the new academic year brought about the problem of accommodation students into dormitories. One of such dormitories has aa × b square meter wonder room. The caretaker wants to accommodate exactly n students there. But the law says that there must be at least 6 square meters per student in a room (that is, the room for n students must have the area of at least 6n square meters). The caretaker can enlarge any (possibly both) side of the room by an arbitrary positive integer of meters. Help him change the room so as all nstudents could live in it and the total area of the room was as small as possible.
Input
The first line contains three space-separated integers n, a and b (1 ≤ n, a, b ≤ 109) — the number of students and the sizes of the room.
Output
Print three integers s, a1 and b1 (a ≤ a1; b ≤ b1) — the final area of the room and its sizes. If there are multiple optimal solutions, print any of them.
Sample test(s)
input
3 3 5

output
18
3 6

input
2 4 4

output
16
4 4
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int LL;

LL n,a,b;

int main()
{
	cin>>n>>a>>b;
	LL s=n*6;
	if(a*b>=s)
	{
		cout<<a*b<<endl;
		cout<<a<<" "<<b<<endl;
		return 0;
	}
	bool flag=false;
	if(b<a) 
	{
		swap(a,b);
		flag=true;
	}

	LL X,Y,AREA=(1LL<<62);
	int nt=0;
	for(LL i=a;i<s;i++)
	{
		LL j=s/i;
		if(j*i<s) j++;
		nt++;
		if(j<b)	break;
		if(j*i<AREA)	
		{
			AREA=i*j;
			X=i;Y=j;
			if(flag) swap(X,Y);
		}
		else if(j*i==s)
		{
			cout<<i*j<<endl;
			if(flag) swap(i,j);
			cout<<i<<" "<<j<<endl;
			return 0;
		}
		else if(j*i>AREA&&nt>20000)
		{
			break;
		}
	}
	cout<<X*Y<<endl;
	cout<<X<<" "<<Y<<endl;

	return 0;
}

좋은 웹페이지 즐겨찾기