Problem: Example

Input

4


Output

4
0 0
1 0
2 0
1 1

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>
#include <bitset>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

const ll MN = 1100100;

ll gcd(ll a, ll b) {
    if (b==0) return a;
    return gcd(b, a%b);
}

ll N;
vector<P> res;
void solve() {
    vector<P> v;
    for (int di = 1; di <= 200; di++) {
        for (int x = 0; x <= di; x++) {
            int y = di-x;
            if (gcd(x, y) != 1) continue;
            v.push_back(P(x, y));
        }
    }
    sort(v.begin(), v.end(), [&](const P &l, const P &r){
        using Pc = complex<double>;
        return arg(Pc(l.first, l.second)) < arg(Pc(r.first, r.second));
    });

    ll n = 1;
    while (n*(n-1)/2 < N) {
        n++;
    }
    ll di = n*(n-1)/2-N;
    if (di == 1 or (10 <= N and di == 3)) n++;
    di = n*(n-1)/2-N;

    static int dp[MN], nex[MN];
    dp[0] = 0;
    for (int i = 1; i < N+10; i++) {
        dp[i] = 1<<28;
        int c = -1;
        for (int j = 1; c+j <= i; j++) {
            c += j;
            if (dp[i-c]+j < dp[i]) {
                dp[i] = dp[i-c]+j;
                nex[i] = j;
            }
            dp[i] = min(dp[i], dp[i-c] + j);
        }
    }

    vector<int> cnt;
    while (di) {
        cnt.push_back(nex[di]);
        di -= nex[di]*(nex[di]+1)/2-1;
    }

    // cout << n << " " << cnt.size() << endl;
    // for (int d: cnt) {
    //     cout << d << " ";
    // }
    // cout << endl;

    P now = P(0, 0);
    res.push_back(now);
    int nowv = 0;
    for (int d: cnt) {
        for (int i = 0; i < d; i++) {
            now = P(now.first+v[nowv].first,now.second+v[nowv].second);
            res.push_back(now);
        }
        nowv++;
    }
    for (int i = res.size(); i < n; i++) {
        now = P(now.first+v[nowv].first,now.second+v[nowv].second);
        res.push_back(now);
        nowv++;
    }
}


// bool dp[3010][3010];
// bool used[3010][3010];
// bool calc(ll n, ll di) {
//     if (di == 0) return true;
//     if (di < 0) return false;
//     bool memo = (max(n, di) < 3010);
//     if (memo && used[n][di]) return dp[n][di];
//     if (memo) used[n][di] = true;
//     for (ll i = 1; i <= n; i++) {
//         if (calc(n-i, di - i*(i+1)/2 + 1)) {
//             if (memo) dp[n][di] = true;
//             return true;
//         }
//     }
//     if (memo) dp[n][di] = false;
//     return false;
// }

// bool check() {
//     ll n = 1;
//     while (n*(n-1)/2 < N) {
//         n++;
//     }
//     ll di = n*(n-1)/2-N;
//     if (di == 1 or (10 <= N and di == 3)) n++;
//     di = n*(n-1)/2-N;
// //    printf("chec %lld %lld\n", n, di);
//     return calc(n-1, di);
// }

int main() {
    cin >> N;
    if (N == 2 or N == 7 or N == 9 or N == 20) {
        if (N == 2) {
            cout << "-1" << endl;
            return 0;
        }
        if (N == 7) {
            printf("%d\n", 6);
            printf("%d %d\n", 4, 7);
            printf("%d %d\n", 2, 1);
            printf("%d %d\n", 4, 2);
            printf("%d %d\n", 8, 4);
            printf("%d %d\n", 4, 4);
            printf("%d %d\n", 3, 4);
            return 0;
        }
        if (N == 9) {
            printf("%d\n", 6);
            printf("%d %d\n", 11, 9);
            printf("%d %d\n", 12, 15);
            printf("%d %d\n", 21, 4);
            printf("%d %d\n", 16, 11);
            printf("%d %d\n", 25, 2);
            printf("%d %d\n", 1, 5);
            return 0;
        }
        if (N == 20) {
            printf("8\n");
            printf("%d %d\n", 21, 19);
            printf("%d %d\n", 27, 11);
            printf("%d %d\n", 7, 19);
            printf("%d %d\n", 8, 20);
            printf("%d %d\n", 15, 19);
            printf("%d %d\n", 6, 25);
            printf("%d %d\n", 17, 29);
            printf("%d %d\n", 22, 20);
            return 0;
        }
        assert(false);
        return 0;
    }
    solve();
    cout << res.size() << endl;
    for (auto p : res) {
         cout << p.first << " " << p.second << endl;
    }
    return 0;
}