<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

292. Field for the Cemetery
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



A new cemetery is going to be built in Petrozavodsk. It will look like qxc rectangle. You have to determine how many rectangular nx1 graves can be placed there. Graves may only be placed parallel to the sides of cemetery.


Input
There will be exactly three lines in the input, each containing one integer: q, c, and n (0 <= q,c <= 10^1000, 1 <= n <= 10^1000).

Output
Output a single number --- maximal number of graves.

Sample test(s)

Input
Test #1
4
5
3

Test #2
100000000000000000000000000000
100000000000000000000000000000
100000000000000000000000000001

Output
Test #1
6

Test #2
0
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

<|response|>
## 1. Abridged problem statement

Given a rectangle of size `q × c`, find the maximum number of axis-parallel graves of size `n × 1` that can fit inside it.

A grave may be placed either:

- horizontally: `1 × n`,
- vertically: `n × 1`.

The numbers `q`, `c`, and `n` can have up to `1000` decimal digits, so arbitrary-precision integers are required.

---

## 2. Key observations needed to solve the problem

### Observation 1: If one side is smaller than `n`

Suppose the rectangle sides are:

```text
short = min(q, c)
long  = max(q, c)
```

If:

```text
short < n
```

then a grave cannot be placed across the short side.

So all graves must be placed parallel to the long side.

Each of the `short` independent rows/columns can contain:

```text
floor(long / n)
```

graves.

Therefore:

```text
answer = short * floor(long / n)
```

This also gives `0` if both sides are smaller than `n`.

---

### Observation 2: If both sides are at least `n`

Assume:

```text
q >= n and c >= n
```

Write:

```text
q = x * n + s
c = y * n + t
```

where:

```text
s = q mod n
t = c mod n
0 <= s, t < n
```

The optimal answer is:

```text
answer = (q * c - s * t) / n + max(0, s + t - n)
```

Equivalently:

```text
answer = (q * c - min(s * t, (n - s) * (n - t))) / n
```

The first form is usually easier to implement.

---

### Observation 3: Why the formula is reasonable

If we tile only full `n`-blocks, the leftover corner of size `s × t` may remain unused, giving:

```text
(q * c - s * t) / n
```

graves.

However, when:

```text
s + t > n
```

a better “pinwheel” arrangement can save extra area and fit:

```text
s + t - n
```

additional graves.

So the final formula becomes:

```text
(q * c - s * t) / n + max(0, s + t - n)
```

---

## 3. Full solution approach based on the observations

We need only arithmetic with huge integers.

### Case 1: `q < n` or `c < n`

At least one side is too short for a grave in that direction.

Let:

```text
short = min(q, c)
long  = max(q, c)
```

Then only graves parallel to the long side can fit.

The answer is:

```text
short * (long / n)
```

where `/` is integer division.

---

### Case 2: `q >= n` and `c >= n`

Compute:

```text
s = q % n
t = c % n
```

The basic packing leaves an uncovered `s × t` corner, so it gives:

```text
(q * c - s * t) / n
```

graves.

If:

```text
s + t > n
```

then the pinwheel construction allows:

```text
s + t - n
```

extra graves.

Therefore:

```text
answer = (q * c - s * t) / n

if s + t > n:
    answer += s + t - n
```

---

### Correctness idea

Color every unit cell `(i, j)` by:

```text
(i + j) mod n
```

Every `n × 1` or `1 × n` grave covers exactly one cell of each color.

Therefore, the number of graves cannot exceed the number of cells of the least frequent color.

For `q = x * n + s` and `c = y * n + t`, counting the cells of each color gives the upper bound:

```text
(q * c - s * t) / n + max(0, s + t - n)
```

The described constructions achieve this bound:

- ordinary filling leaves `s * t` cells empty,
- pinwheel filling, when useful, leaves only `(n - s) * (n - t)` cells empty.

Thus the formula is optimal.

---

### Complexity

Let `D` be the number of decimal digits, up to `1000`.

The algorithm uses only a constant number of big integer operations.

```text
Time complexity:  polynomial in D
Memory complexity: O(D)
```

---

## 4. C++ implementation

Inputs have up to `1000` decimal digits, so we carry a self-contained `bigint`
struct (base-`10^9` limbs, Karatsuba multiplication, long division). The actual
algorithm is the short case analysis at the bottom of `solve()`.

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

// base and base_digits must be consistent
const int base = 1000000000;
const int base_digits = 9;

struct bigint {
    vector<int> z;
    int sign;

    bigint() : sign(1) {}

    bigint(long long v) { *this = v; }

    bigint(const string& s) { read(s); }

    void operator=(const bigint& v) {
        sign = v.sign;
        z = v.z;
    }

    void operator=(long long v) {
        sign = 1;
        if(v < 0) {
            sign = -1, v = -v;
        }
        z.clear();
        for(; v > 0; v = v / base) {
            z.push_back(v % base);
        }
    }

    bigint operator+(const bigint& v) const {
        if(sign == v.sign) {
            bigint res = v;

            for(int i = 0, carry = 0;
                i < (int)max(z.size(), v.z.size()) || carry; ++i) {
                if(i == (int)res.z.size()) {
                    res.z.push_back(0);
                }
                res.z[i] += carry + (i < (int)z.size() ? z[i] : 0);
                carry = res.z[i] >= base;
                if(carry) {
                    res.z[i] -= base;
                }
            }
            return res;
        }
        return *this - (-v);
    }

    bigint operator-(const bigint& v) const {
        if(sign == v.sign) {
            if(abs() >= v.abs()) {
                bigint res = *this;
                for(int i = 0, carry = 0; i < (int)v.z.size() || carry; ++i) {
                    res.z[i] -= carry + (i < (int)v.z.size() ? v.z[i] : 0);
                    carry = res.z[i] < 0;
                    if(carry) {
                        res.z[i] += base;
                    }
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }

    void operator*=(int v) {
        if(v < 0) {
            sign = -sign, v = -v;
        }
        for(int i = 0, carry = 0; i < (int)z.size() || carry; ++i) {
            if(i == (int)z.size()) {
                z.push_back(0);
            }
            long long cur = z[i] * (long long)v + carry;
            carry = (int)(cur / base);
            z[i] = (int)(cur % base);
            // asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur),
            // "c"(base));
        }
        trim();
    }

    bigint operator*(int v) const {
        bigint res = *this;
        res *= v;
        return res;
    }

    friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1) {
        int norm = base / (b1.z.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.z.resize(a.z.size());

        for(int i = a.z.size() - 1; i >= 0; i--) {
            r *= base;
            r += a.z[i];
            int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
            int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
            int d = ((long long)s1 * base + s2) / b.z.back();
            r -= b * d;
            while(r < 0) {
                r += b, --d;
            }
            q.z[i] = d;
        }

        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }

    friend bigint sqrt(const bigint& a1) {
        bigint a = a1;
        while(a.z.empty() || a.z.size() % 2 == 1) {
            a.z.push_back(0);
        }

        int n = a.z.size();

        int firstDigit = (int)sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
        int norm = base / (firstDigit + 1);
        a *= norm;
        a *= norm;
        while(a.z.empty() || a.z.size() % 2 == 1) {
            a.z.push_back(0);
        }

        bigint r = (long long)a.z[n - 1] * base + a.z[n - 2];
        firstDigit = (int)sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
        int q = firstDigit;
        bigint res;

        for(int j = n / 2 - 1; j >= 0; j--) {
            for(;; --q) {
                bigint r1 =
                    (r - (res * 2 * base + q) * q) * base * base +
                    (j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2]
                           : 0);
                if(r1 >= 0) {
                    r = r1;
                    break;
                }
            }
            res *= base;
            res += q;

            if(j > 0) {
                int d1 =
                    res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
                int d2 =
                    res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
                int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
                q = ((long long)d1 * base * base + (long long)d2 * base + d3) /
                    (firstDigit * 2);
            }
        }

        res.trim();
        return res / norm;
    }

    bigint operator/(const bigint& v) const { return divmod(*this, v).first; }

    bigint operator%(const bigint& v) const { return divmod(*this, v).second; }

    void operator/=(int v) {
        if(v < 0) {
            sign = -sign, v = -v;
        }
        for(int i = (int)z.size() - 1, rem = 0; i >= 0; --i) {
            long long cur = z[i] + rem * (long long)base;
            z[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        trim();
    }

    bigint operator/(int v) const {
        bigint res = *this;
        res /= v;
        return res;
    }

    int operator%(int v) const {
        if(v < 0) {
            v = -v;
        }
        int m = 0;
        for(int i = z.size() - 1; i >= 0; --i) {
            m = (z[i] + m * (long long)base) % v;
        }
        return m * sign;
    }

    void operator+=(const bigint& v) { *this = *this + v; }
    void operator-=(const bigint& v) { *this = *this - v; }
    void operator*=(const bigint& v) { *this = *this * v; }
    void operator/=(const bigint& v) { *this = *this / v; }

    bool operator<(const bigint& v) const {
        if(sign != v.sign) {
            return sign < v.sign;
        }
        if(z.size() != v.z.size()) {
            return z.size() * sign < v.z.size() * v.sign;
        }
        for(int i = z.size() - 1; i >= 0; i--) {
            if(z[i] != v.z[i]) {
                return z[i] * sign < v.z[i] * sign;
            }
        }
        return false;
    }

    bool operator>(const bigint& v) const { return v < *this; }
    bool operator<=(const bigint& v) const { return !(v < *this); }
    bool operator>=(const bigint& v) const { return !(*this < v); }
    bool operator==(const bigint& v) const {
        return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint& v) const { return *this < v || v < *this; }

    void trim() {
        while(!z.empty() && z.back() == 0) {
            z.pop_back();
        }
        if(z.empty()) {
            sign = 1;
        }
    }

    bool isZero() const { return z.empty() || (z.size() == 1 && !z[0]); }

    bigint operator-() const {
        bigint res = *this;
        res.sign = -sign;
        return res;
    }

    bigint abs() const {
        bigint res = *this;
        res.sign *= res.sign;
        return res;
    }

    long long longValue() const {
        long long res = 0;
        for(int i = z.size() - 1; i >= 0; i--) {
            res = res * base + z[i];
        }
        return res * sign;
    }

    friend bigint gcd(const bigint& a, const bigint& b) {
        return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint& a, const bigint& b) {
        return a / gcd(a, b) * b;
    }

    void read(const string& s) {
        sign = 1;
        z.clear();
        int pos = 0;
        while(pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
            if(s[pos] == '-') {
                sign = -sign;
            }
            ++pos;
        }
        for(int i = s.size() - 1; i >= pos; i -= base_digits) {
            int x = 0;
            for(int j = max(pos, i - base_digits + 1); j <= i; j++) {
                x = x * 10 + s[j] - '0';
            }
            z.push_back(x);
        }
        trim();
    }

    friend istream& operator>>(istream& stream, bigint& v) {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }

    friend ostream& operator<<(ostream& stream, const bigint& v) {
        if(v.sign == -1) {
            stream << '-';
        }
        stream << (v.z.empty() ? 0 : v.z.back());
        for(int i = (int)v.z.size() - 2; i >= 0; --i) {
            stream << setw(base_digits) << setfill('0') << v.z[i];
        }
        return stream;
    }

    static vector<int> convert_base(
        const vector<int>& a, int old_digits, int new_digits
    ) {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for(int i = 1; i < (int)p.size(); i++) {
            p[i] = p[i - 1] * 10;
        }
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for(int i = 0; i < (int)a.size(); i++) {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while(cur_digits >= new_digits) {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while(!res.empty() && res.back() == 0) {
            res.pop_back();
        }
        return res;
    }

    typedef vector<long long> vll;

    static vll karatsubaMultiply(const vll& a, const vll& b) {
        int n = a.size();
        vll res(n + n);
        if(n <= 32) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    res[i + j] += a[i] * b[j];
                }
            }
            return res;
        }

        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());

        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);

        for(int i = 0; i < k; i++) {
            a2[i] += a1[i];
        }
        for(int i = 0; i < k; i++) {
            b2[i] += b1[i];
        }

        vll r = karatsubaMultiply(a2, b2);
        for(int i = 0; i < (int)a1b1.size(); i++) {
            r[i] -= a1b1[i];
        }
        for(int i = 0; i < (int)a2b2.size(); i++) {
            r[i] -= a2b2[i];
        }

        for(int i = 0; i < (int)r.size(); i++) {
            res[i + k] += r[i];
        }
        for(int i = 0; i < (int)a1b1.size(); i++) {
            res[i] += a1b1[i];
        }
        for(int i = 0; i < (int)a2b2.size(); i++) {
            res[i + n] += a2b2[i];
        }
        return res;
    }

    bigint operator*(const bigint& v) const {
        vector<int> a6 = convert_base(this->z, base_digits, 6);
        vector<int> b6 = convert_base(v.z, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while(a.size() < b.size()) {
            a.push_back(0);
        }
        while(b.size() < a.size()) {
            b.push_back(0);
        }
        while(a.size() & (a.size() - 1)) {
            a.push_back(0), b.push_back(0);
        }
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for(int i = 0, carry = 0; i < (int)c.size(); i++) {
            long long cur = c[i] + carry;
            res.z.push_back((int)(cur % 1000000));
            carry = (int)(cur / 1000000);
        }
        res.z = convert_base(res.z, 6, base_digits);
        res.trim();
        return res;
    }
};

bigint q, c, n;

void read() { cin >> q >> c >> n; }

void solve() {
    // We pack 1xn strips into a qxc board, maximizing the count. Color cell
    // (i, j) with (i + j) mod n. A strip covers n consecutive cells in one
    // line, so it hits each of the n colors exactly once. Hence every placed
    // strip uses one cell of color k, and if N_k is the number of board cells
    // of color k, the number of strips T satisfies T <= N_k for all k, i.e.
    //
    //     T <= min_k N_k.
    //
    // Write x = q / n, s = q % n, y = c / n, t = c % n. Rows contribute residue
    // a with multiplicity (x + [a < s]) and columns residue b with (y + [b <
    // t]), so N_k = n*x*y + x*t + y*s + Q_k, where Q_k counts b in [0, t) with
    // (k - b) mod n in [0, s). As k slides, that is the overlap of a length-s
    // cyclic arc with the length-t interval [0, t) in Z_n; two arcs of lengths
    // s and t on a cycle of length n overlap in at least max(0, s + t - n)
    // cells, and that minimum is attained. Therefore
    //
    //     T <= (q*c - s*t) / n + max(0, s + t - n).
    //
    // When both q >= n and c >= n this bound is achievable. Peel off full
    // slabs whose side is a multiple of n -- the top n*(x - 1) rows (vertical
    // strips) and, in the rest, the left n*(y - 1) columns (horizontal strips)
    // -- both tile completely, leaving a single (n + s) x (n + t) corner block.
    // Filling that block trivially (a strip along each row's left part and each
    // column's top part) leaves the s x t sub-corner empty: deficiency s*t.
    // Pinwheeling it instead leaves only an (n - s) x (n - t) hole: deficiency
    // (n - s)*(n - t) = s*t - n*(s + t - n). Each arm has a side of length n,
    // so it tiles completely; the pinwheel wins (by s + t - n strips) exactly
    // when s + t > n. With s = q % n, t = c % n the corner block looks like:
    //
    //          0            t           n          n+t
    //        0 +------------+-----------+-----------+
    //          |                        |           |
    //          |          TOP           |   RIGHT   |
    //          |         s x n          |   n x t   |
    //          |      (horizontal)      | (vertical)|
    //        s +------------+-----------+           |
    //          |            |           |           |
    //          |    LEFT    |   HOLE    |           |
    //          |   n x t    |  (n-s) x  |           |
    //          | (vertical) |   (n-t)   |           |
    //        n |            +-----------+-----------+
    //          |            |                       |
    //          |            |        BOTTOM         |
    //          |            |         s x n         |
    //          |            |     (horizontal)      |
    //      n+s +------------+-----------------------+
    //
    // So the deficiency is min(s*t, (n - s)*(n - t)). This meets the upper
    // bound exactly: the pinwheel saves s*t - (n - s)*(n - t) = n*(s + t - n)
    // cells over the trivial fill, i.e. s + t - n extra strips, which is
    // precisely the min_k Q_k = max(0, s + t - n) bonus times n, so the
    // construction attains min_k N_k and is optimal. (For s = t = 2, n = 3 this
    // is the pinwheel on a 5x5 board with arms 2x3, 2x3, 3x2, 3x2 around a 1x1
    // hole: only the centre empty.)
    //
    // If min(q, c) < n only the orientation along the long side fits, because
    // the short side cannot hold a strip; the corner bonus needs both
    // orientations and vanishes. Each of the min(q, c) lines independently
    // holds floor(max(q, c) / n) strips, giving min(q, c) * floor(max(q, c) /
    // n), which is 0 when both sides are below n.

    bigint ans;
    if(q >= n && c >= n) {
        bigint s = q % n, t = c % n;
        ans = (q * c - s * t) / n;
        if(s + t > n) {
            ans += s + t - n;
        }
    } else {
        ans = min(q, c) * (max(q, c) / n);
    }

    cout << ans << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
# Python integers are arbitrary precision by default.

q = int(input())
c = int(input())
n = int(input())

# Case 1:
# Both sides are at least n, so we can use the optimal formula.
if q >= n and c >= n:
    # Leftover parts after taking full multiples of n.
    s = q % n
    t = c % n

    # Basic construction leaves an s * t corner uncovered.
    answer = (q * c - s * t) // n

    # Pinwheel improvement.
    if s + t > n:
        answer += s + t - n

# Case 2:
# One side is smaller than n, so only one orientation is possible.
else:
    short_side = min(q, c)
    long_side = max(q, c)

    # Each line along the short side contains floor(long_side / n) graves.
    answer = short_side * (long_side // n)

print(answer)
```
