# UVa 11259 - Coin Changing Again

`# include <cstdio># include <map># include <set>using namespace std;struct State{ State (int v1, int v2, int v3, int v4) {  V1 = v1; V2 = v2; V3 = v3; V4 = v4; } int getPart2(int Value = 0) {  int Part2 = 0;  Part2 = (V4 >> 13);  Part2 |= (Value << 4);  return Part2; } unsigned long long getPart1() {  unsigned long long Part1 = 0;  Part1 = V1;  Part1 |= (V2 << 17);  Part1 |= ((unsigned long long)V3 << 34);  Part1 |= ((unsigned long long)V4 << 51);  return Part1; } int V1, V2, V3, V4;};map <int, set<unsigned long long> > States;map <int, set<unsigned long long> > Solutions;int c1, c2, c3, c4, q, d1, d2, d3, d4, v;unsigned long long Result ;bool CheckVisited (unsigned long long Part1, int Part2){ if (States[Part2].count (Part1)) return true; States[Part2].insert (Part1); return false;}void Solution (State & s, int Value){ unsigned long long Part1 = s.getPart1(); int Part2 = s.getPart2(Value); if (!Value) {  Solutions[Part2].insert (Part1);  return; } if (CheckVisited(Part1, Part2)) return; if (s.V1 - 1 >= 0 && Value - c1 >= 0) {  s.V1--;  Solution (s, Value - c1);  s.V1++; } if (s.V2 - 1 >= 0 && Value - c2 >= 0) {  s.V2--;  Solution (s, Value - c2);  s.V2++; } if (s.V3 - 1 >= 0 && Value - c3 >= 0) {  s.V3--;  Solution (s, Value - c3);  s.V3++; } if (s.V4 - 1 >= 0 && Value - c4 >= 0) {  s.V4--;  Solution (s, Value - c4);  s.V4++; }}int main(){ freopen ("Input.txt", "r", stdin); freopen ("Scratch.txt", "w", stdout); int N; scanf ("%d", &N); State s (0, 0, 0, 0); while (N--) {  scanf ("%d%d%d%d%d", &c1, &c2, &c3, &c4, &q);  while (q--)  {   scanf ("%d%d%d%d%d", &s.V1, &s.V2, &s.V3, &s.V4, &v);   Result = 0;   States.clear();   Solutions.clear();   Solution (s, v);   for (map<int, set<unsigned long long> >::iterator it = Solutions.begin(); it != Solutions.end(); it++)    Result += it->second.size();   printf ("%lld\n", Result);  } }}`