「CFgym100541」Pencil Game

2015年3月14日2,9650

Minh has a box of pencils. The box is a rectangle of size M * N, where position (i, j) has a pencil with a length of exactly i * N + j (0 ≤ i ≤ M - 1, 0 ≤ j ≤ N - 1). Note that position (0, 0) does not have any pencil hence having a length of 0.

He wonders if he could select a sub-rectangle of the box and join all the pencils within that sub-rectangle together, to get a new long pencil that has a specific length L that he wants.

Your task is to find a sub-rectangle of the box in which the total length of the contained pencils is L and return the area of that the sub-rectangle. If there are multiple solutions, return the smallest possible area. If there’s no such sub-rectangle, return - 1.

Input

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 150. The following lines describe the datasets.

Each dataset contains three space-separated numbers M, N and L (1 ≤ M, N ≤ 10⁶, 1 ≤ L ≤ 10¹²) written in one line.

Output

For each dataset, write in one line the smallest possible area of the sub-rectangle in which the total sum of pencil lengths is L. Write in one line - 1 if there is no such sub-rectangle.

Sample test(s)

input

4
2 3 8
3 3 10
3 3 36
1000000 1000000 1000000000000

2 3 8

3 3 10

3 3 36

1000000 1000000 1000000000000

output

-1

题解

我是傻逼T T

如果确定了矩形的长宽，就比较容易判是否可行

然后考虑枚举面积K

K一定是2L的约数，且K不会超过根号L级别

然后再枚举一条边，同样只要根号K

我是傻逼T T

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-6
#define inf 1000000000
#define mod 1000000009
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
ll n,m,tot;
ll L,sum[2000005];
bool cal(int x,int y)
{
	tot++;
	if(x>n||y>m)return 0;
	int t1=n-x,t2=m-y;
	ll tmp=sum[x-1]*y+x*sum[y-1]*n;
	if(tmp>L)return 0;
	tmp=L-tmp;
	ll k=x*y;if(tmp%k!=0)return 0;
	tmp/=k;
	if(t2*n+t1<tmp)return 0;
	if(t1<tmp%n)return 0;
	return 1;
}
int main()
{
    for(int i=1;i<=2000000;i++)sum[i]=sum[i-1]+i;
    T=read();
    while(T--)
    {
        m=read();n=read();L=read();
        bool flag=0;
        for(ll x=1;sum[x-1]<=L;x++)
			if(L*2%x==0)
			{
				for(ll i=1;i*i<=x;i++)
					if(x%i==0)
					{
						flag|=cal(i,x/i);
						flag|=cal(x/i,i);
						if(flag)break;
					}
				if(flag)
				{
					cout<<x<<endl;
					break;
				}
			}
        if(!flag)puts("-1");
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-6

#define inf 1000000000

#define mod 1000000009

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T;

ll n,m,tot;

ll L,sum[2000005];

bool cal(int x,int y)

{

tot++;

if(x>n||y>m)return 0;

int t1=n-x,t2=m-y;

ll tmp=sum[x-1]*y+x*sum[y-1]*n;

if(tmp>L)return 0;

tmp=L-tmp;

ll k=x*y;if(tmp%k!=0)return 0;

tmp/=k;

if(t2*n+t1<tmp)return 0;

if(t1<tmp%n)return 0;

return 1;

}

int main()

{

for(int i=1;i<=2000000;i++)sum[i]=sum[i-1]+i;

T=read();

while(T--)

{

m=read();n=read();L=read();

bool flag=0;

for(ll x=1;sum[x-1]<=L;x++)

if(L*2%x==0)

{

for(ll i=1;i*i<=x;i++)

if(x%i==0)

{

flag|=cal(i,x/i);

flag|=cal(x/i,i);

if(flag)break;

}

if(flag)

{

cout<<x<<endl;

break;

}

if(!flag)puts("-1");

}

return 0;

}

« 「uoj #66」新年的巧克力棒「BZOJ3210」花神的浇花集会 »

hzwer.com _ Home | http://hzwer.com

「CFgym100541」Pencil Game

分类目录

热门文章

Myfriends

近期评论