题解归档 - cf2219A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2219A
• 本地来源：problems/cf2219A/idea.md
• 题目链接：https://codeforces.com/contest/2219/problem/A
• 原始标题：cf2219A - Grid L

思路

cf2219A - Grid L

Pattern

An n x m grid contains:

• n(m+1) horizontal unit edges;
• m(n+1) vertical unit edges;
• total 2nm+n+m unit edges.

Each L-shaped piece consumes one horizontal and one vertical unit edge; each
single segment consumes one remaining edge. Therefore:

p + 2q = 2nm + n + m

and additionally:

q <= n(m+1) and q <= m(n+1).

The total equation can be factored:

(2n+1)(2m+1) = 2(p+2q)+1.

Algorithm

Factor the odd number 2(p+2q)+1. For every factorization into odd factors
larger than 1, recover n and m, then test the two L-capacity inequalities.

Checks

• python tools/math_reasoning_search.py --problem cf2219A -n 5 - required
  precheck done.
• Reused the same derivation and implementation as cf2220C, then verified
  under the cf2219A problem directory.

代码

来源：problems/cf2219A/solution.cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static bool valid(ll n, ll m, ll p, ll q) {
    ll total = 2 * n * m + n + m;
    if (total != p + 2 * q) return false;
    ll horizontal = n * (m + 1);
    ll vertical = m * (n + 1);
    return q <= horizontal && q <= vertical;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        ll p, q;
        cin >> p >> q;
        ll need = 2 * (p + 2 * q) + 1;
        bool ok = false;
        for (ll d = 3; d * d <= need && !ok; d += 2) {
            if (need % d != 0) continue;
            ll e = need / d;
            ll n = (d - 1) / 2;
            ll m = (e - 1) / 2;
            if (valid(n, m, p, q)) {
                cout << n << ' ' << m << '\n';
                ok = true;
            } else if (valid(m, n, p, q)) {
                cout << m << ' ' << n << '\n';
                ok = true;
            }
        }
        if (!ok) cout << -1 << '\n';
    }
    return 0;
}