結果

問題 No.2597 Yet Another Topological Problem
コンテスト
ユーザー suisen
提出日時 2023-11-22 17:45:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 4,315 bytes
コンパイル時間 943 ms
コンパイル使用メモリ 87,340 KB
最終ジャッジ日時 2025-02-17 23:03:15
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

// <WA?> 拡大率の条件漏れ (1)

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>

const std::string Possible{ "Possible" };
const std::string Impossible{ "Impossible" };

/**
 * D は q の倍数とする。k=D/q: 拡大率
 * 
 * R=floor(q/p) として、次のような山(実線)を i=0,1,...,R まで並べる
 * 
 *      x=i(kp-1)
 *          :   x=i(kp+1)                 山の内側の点線 (山 i-1 を kp だけ右にシフトしたもの): 通行禁止
 *          :       :
 *          +-------+       y=i
 *          | ..... |
 *          | :   : |
 *          | :   : |
 *          | :   : |
 *          | :   : |
 *          | :   : +-----  y=-R+i
 * ---------+ :   :.......
 * ...........:
 * 
 * [拡大率 k (=D/q) が満たすべき条件]
 * 1. R(kp+1)-R(kp-1) < kp   : R番目の山の幅が kp 未満
 * 2. kq - R(kp-1) < kp      : R番目の山の左端と kq(=D) の距離が kp 未満
 * 3. R(kp+1) <= kq          : R番目の山の右端より右側 (inclusive) に kq(=D) が存在
 * 
 * それぞれ整理すると
 * 1. k >= ceil((2R+1)/p)
 * 2. k >= ceil((R+1)/(p(R+1)-q)
 * 3. k >= ceil(R/(q-pR))
 * 
 * つまり k は 1,2,3 の右辺の最大値を取れば十分
 * 
 * [線分の長さ]
 * - x 方向: kq
 * - y 方向: R((R+1)+R)+R = 2R(R+1)
 * 
 * R,k,q の最大値は？
 * - R: 249
 * - k: 250
 * - q: 500
 * 
 * 結局 kq + 2R(R+1) <= 249500 なので長さの制約は OK
 * 
 * [座標の大きさ]
 * - x 方向: 0<=x<=kq なので |x|<=125000 で OK
 * - y 方向: -R<=y<=R なので |y|<=500 で OK
 */

void debug(const std::vector<std::pair<int, int>>& points) {
    int maxx = 0;
    int miny = 0, maxy = 0;
    for (const auto& [x, y] : points) {
        maxx = std::max(maxx, x);
        miny = std::min(miny, y);
        maxy = std::max(maxy, y);
    }
    std::vector<std::string> lines_(maxy - miny + 1, std::string(maxx + 1, ' '));
    auto lines = lines_.rend() - (maxy + 1);
    for (int x = 0; x <= maxx; ++x) {
        lines[0][x] = '.';
    }
    lines[0][0] = '+';
    for (size_t i = 1; i < points.size(); ++i) {
        auto [px, py] = points[i - 1];
        auto [cx, cy] = points[i];

        if (i + 1 == points.size()) {
            lines[cy][cx] = '+';
        } else {
            auto [nx, ny] = points[i + 1];
            bool cv = px == cx;
            bool nv = cx == nx;
            if (cv != nv) {
                lines[cy][cx] = '+';
            } else if (cv) {
                lines[cy][cx] = '|';
            } else {
                lines[cy][cx] = '-';
            }
        }
    }
    for (auto& line : lines_) {
        std::cerr << line << '\n';
    }
    std::cerr.flush();
}

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

    int p, q;
    std::cin >> p >> q;

    if (p == 1) {
        std::cout << Impossible << '\n';
        return 0;
    }
    std::cout << Possible << '\n';

    const int R = q / p;

    const int k = std::max(
        {
            // 2 * R / p + 1,
            R / (p * (R + 1) - q) + 1,
            (R + q - p * R - 1) / (q - p * R)
        }
    );

    std::vector<std::pair<int, int>> points;

    // 山 i
    for (int i = 0; i < R; ++i) {
        int x = i * (k * p + 1);
        int y = i;

        // 山 i を下る
        while (y > -R + i) {
            points.emplace_back(x, y);
            --y;
        }
        // 山 i と i+1 の間の谷の右端まで移動
        while (x < (i + 1) * (k * p - 1)) {
            points.emplace_back(x, y);
            ++x;
        }
        // 山 i+1 を上る
        while (y < i + 1) {
            points.emplace_back(x, y);
            ++y;
        }
        // 山 i+1 の峰の右端まで移動
        while (x < (i + 1) * (k * p + 1)) {
            points.emplace_back(x, y);
            ++x;
        }
    }
    // 山 R
    {
        int x = R * (k * p + 1);
        int y = R;

        // 山 R を下る
        while (y > 0) {
            points.emplace_back(x, y);
            --y;
        }
        // (D,0) まで進む
        while (x <= k * q) {
            points.emplace_back(x, y);
            ++x;
        }
    }

    std::cout << points.size() - 1 << '\n';
    for (const auto& [x, y] : points) {
        std::cout << x << ' ' << y << '\n';
    }
}
0