## Sunday, April 21, 2013

### UVa 11259 - Coin Changing Again

This took lot of my time and I managed to come up with this Top-down Dynamic Programming solution. This approach times out. Any suggestions? Problem Statement : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2226
```# 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);
}
}
}
```