เม่นเดินซิกแซก: ช่องสีเทาคือคู่ที่บิตไม่ชนกัน จึงนับได้โดยไม่ต้องเดิน

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 21;                       // 10^6 < 2^20 ส่วนผลรวมสองตัวใช้ 21 บิตพอ
ll R, C, K;

// จำนวนคู่ (r, c) ที่ r < R, c < C, บิตไม่ชนกัน และ r + c < D
ll countBelow(ll D){
    if(D <= 0) return 0;
    ll dp[2][2][2] = {};                // ยังติดขอบของ R, ของ C, ของ D อยู่ไหม
    dp[1][1][1] = 1;
    for(int i = B - 1; i >= 0; i--){
        ll nx[2][2][2] = {};
        int rb = (R >> i) & 1, cb = (C >> i) & 1, db = (D >> i) & 1;
        for(int a = 0; a < 2; a++) for(int b = 0; b < 2; b++) for(int c = 0; c < 2; c++){
            ll v = dp[a][b][c]; if(!v) continue;
            for(int x = 0; x < 2; x++) for(int y = 0; y < 2; y++){
                if(x && y) continue;                      // r กับ c ห้ามมีบิต 1 ตรงกัน
                int s = x | y;                            // บิตไม่ชนกัน ผลบวกจึงเท่ากับผลหรือ
                if(a && x > rb) continue; int na = (a && x == rb) ? 1 : 0;
                if(b && y > cb) continue; int nb = (b && y == cb) ? 1 : 0;
                if(c && s > db) continue; int nc = (c && s == db) ? 1 : 0;
                nx[na][nb][nc] += v;
            }
        }
        memcpy(dp, nx, sizeof dp);
    }
    // เอาเฉพาะสถานะที่หลุดขอบครบทั้งสามตัว ที่ยังติดขอบคือค่าเท่าขอบพอดี ซึ่งต้องไม่นับ
    return dp[0][0][0];
}

// จำนวน r ที่บิตเป็นสับเซตของ D และ r <= x
ll subLE(ll D, ll x){
    if(x < 0) return 0;
    ll res = 0, below = 0; bool tight = true;
    for(int i = B; i >= 0; i--) if((D >> i) & 1) below++;
    for(int i = B; i >= 0; i--){
        int di = (D >> i) & 1, xi = (x >> i) & 1;
        if(di) below--;
        if(xi){
            res += 1LL << below;                          // บิตนี้เลือกเป็น 0 ที่เหลืออิสระหมด
            if(!di){ tight = false; break; }              // บิตนี้บังคับเป็น 0 อยู่แล้ว เลิกติดขอบ
        }
    }
    return res + (tight ? 1 : 0);
}

int main(){
    if(scanf("%lld %lld %lld", &R, &C, &K) != 3) return 0;
    ll seen = 0, D = 0;                                   // หาว่าเม่นหลับกลางแนวทแยงเส้นไหน
    for(ll d = 0; d < R + C - 1; d++){
        ll len = min(R - 1, d) - max(0LL, d - C + 1) + 1;
        if(seen + len >= K){ D = d; break; }
        seen += len;
    }
    ll ans = countBelow(D);                               // ท่อนแรก แนวทแยงที่เดินจบแล้ว
    ll t = K - seen;                                      // ท่อนสอง เหลืออีก t ช่องบนเส้น D
    ll lo = max(0LL, D - C + 1), hi = min(R - 1, D), a, b;
    if(D & 1){ a = lo;         b = lo + t - 1; }          // แนวทแยงคี่เดินจากบนลงล่าง
    else     { a = hi - t + 1; b = hi; }                  // แนวทแยงคู่เดินจากล่างขึ้นบน
    ans += subLE(D, b) - subLE(D, a - 1);
    printf("%lld\n", ans);
}

// ตัวตรวจ เดินจริงทีละช่องตามที่โจทย์เล่า ใช้ได้เฉพาะกระดานเล็ก
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long R, C, K; cin >> R >> C >> K;
    long long cnt = 0, seen = 0;
    for(long long d = 0; d < R + C - 1 && seen < K; d++){
        long long lo = max(0LL, d - C + 1), hi = min(R - 1, d);
        if(d % 2 == 1) for(long long r = lo; r <= hi && seen < K; r++){
            long long c = d - r; seen++; if((r & c) == 0) cnt++; }
        else for(long long r = hi; r >= lo && seen < K; r--){
            long long c = d - r; seen++; if((r & c) == 0) cnt++; }
    }
    cout << cnt << "\n";
}