Grid L (CF R 1093 - A)

https://codeforces.com/contest/2219/problem/A

---

아이디어

가로의 길이를 n, 세로의 길이를 m이라고 해봅시다.

그러면 필요한 단위 길이의 개수는 n*(m+1)+m*(n+1)=2nm+n+m이 됩니다. 이 값이 p+2q와 같아져야합니다. 이러한 n,m의 값은 n<=m으로 정의하였을 때 n이 20,000 이하의 범위에서 존재하게 됩니다. 그러므로 이러한 (n,m)의 쌍을 O(20000)에 찾을 수 있습니다.

 

그러면 n,m이 나오면 그것을 현재 주어진 조각들로 구성할 수 있는지의 여부를 어떻게 판단할 수 있을까요?

n*m칸을 채우다보면 기본적으로 L모양으로 채울 수 있지만 일자 모양이 |n-m|개 필요함을 확인할 수 있습니다. 그러므로 가능한 (n,m)중 |n-m|이 최소인것이 일자 모양의 개수보다 작거나 같은 경우에만 가능하고, 그렇지 않은 경우 -1을 출력해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

void solve()
{
    ll p,q,i,Min=1e18,x,y;

    cin>>p>>q;
    for (i=1;2*i*i+2*i<=p+2*q;i++)
    {
        if ((p+2*q-i)%(2*i+1)==0)
        {
            ll j=(p+2*q-i)/(2*i+1);
            Min=j-i;
            x=i,y=j;
        }
    }

    if (Min<=p) cout<<x<<' '<<y<<"\n";
    else cout<<-1<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T;
    cin>>T;
    while (T--)
        solve();
}