Acwing daily question three thousand five hundred and eleven

ACWing A daily topic .3511

subject ：

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

Answer key ：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

typedef long long LL;

const LL B = 10000; //  Max. per bucket 4000, So use a LL Type number to store the status of three buckets 

int C[3];
unordered_set<LL> states; //  The state of three barrels 
unordered_set<int> cs;    //  bucket C The state of 

LL get(int c[])
{
    
        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;
}

/*  Deep search ：  Input ： The volume of water already filled in three buckets   Array   function ： 1.  Add the state of three buckets states; 2.  take C The capacity of water in the bucket at this time is added cs; 3.  Pour water between the three buckets , If it doesn't appear states Internal state , Proceed to the state at this time fds; */
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); // i Bucket to j Pour water in the bucket 
                                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]}; //  The capacity of water in three barrels 
                dfs(c);
                cout << cs.size() << endl;
        }

        return 0;
}