3511. Water pouring problem

There are three cups , The capacities are A,B,C.

At the beginning ,C The cup is full of water , and A,B The cups are empty .

Now, under the condition that there is no water leakage, carry out the following operations several times ：

Put a cup x Pour the water in another cup y in , When x Empty or y Stop when it's full （ Meet one of the conditions before stopping ）.

Excuse me, , After all operations are completed ,C How many possibilities are there for the amount of water in .

Input format

Input contains multiple sets of test data .

Each group of data occupies one row , Contains three integers A,B,C.

Output format

Each group of data outputs a result , Occupy a line .

Data range

0≤A,B,C≤4000,
Each input contains at most 100 Group data .

sample input ：

0 5 5
2 2 4

sample output ：

2
3

Code ：

//  Violent search   Enumerate all States   Weight determination 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const LL B = 10000;

int C[3];
unordered_set<LL> states;
unordered_set<int> cs;

LL get(int c[]) //  Hash 
{
    
    return c[2] * B * B + c[1] * B + c[0];
}

void pour(int c[], int i, int j)
{
    
    int t = min(c[i], C[j] - c[j]);
    c[i] -= t, c[j] += t;
}

void dfs(int c[])
{
    

    states.insert(get(c));
    cs.insert(c[2]);

    int a[3];
    for (int i = 0; i < 3; i++)
    {
    
        for (int j = 0; j < 3; j++)
        {
    
            if (i != j)
            {
    
                memcpy(a, c, sizeof a);
                pour(a, i, j);
                if (!states.count(get(a)))
                    dfs(a);
            }
        }
    }
}

int main()
{
    
    
    while (cin >> C[0] >> C[1] >> C[2])
    {
    

        states.clear();
        cs.clear();
        int c[3] = {
    0, 0, C[2]};
        dfs(c);
        cout << cs.size() << endl;

    }
    return 0;
}