Tolik and His Uncle

Created by LXC on Mon Apr 8 14:55:34 2024

https://codeforces.com/problemset/problem/1179/B

ranting: 1800

tag: constructive algorithms

problem

有一天，_rqy想出来了一道构造题，出给了wqy去做。然而wqy不会做，于是就来找你。

你有一个$n$行$m$列的棋盘，其中第$i$行第$j$列的格子标号为$(i,j)$。你需要从$(1,1)$开始遍历这个棋盘。每一次，如果你在$(x,y)$，你可以选择一个向量$(\text{d}x,\text{d}y)$，并且移动到$(x+\text{d}x,y+\text{d}y)$这个格子上。

你不能离开这个棋盘，同时每一个向量只能使用一次。你的任务是合理安排自己的行走路线，使得每一个格子都只被经过一次。输出这个方案。

wqy翻译了那么多题面，你一定要帮他解出来！

solution

我们从上之下从左至右遍历。

当经过(x,y)时，立即经过(n-x+1, m-y+1)。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+1, vector<int>(m+1));
    int c = 0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (g[i][j]) continue;
            cout << i << " " << j << "\n";
            g[i][j] = 1;
            c++;
            if (g[n-i+1][m-j+1]) continue;
            cout << n-i+1 << " " << m-j+1 << "\n";
            g[n-i+1][m-j+1] = 1;
            c++;
        }
    }
    // cout << c << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}