I want a proof or a counter example

[Sedefcho]

Basically I reduce the 4's with 6's following this IDEA:

Let's say we can group the 4's into N groups ( N is even )
where in each group we have three 4's.

Now each group I substitute with 2 elements of value 6.

So for each i = 1 to N, we do n[6] +=2;


Then I reduce the 5's with 6's following this IDEA:

Let's say we can group the 5's into N groups ( N is even )
where in each group we have six 5's.

Now each group I substitute with 5 elements of value 6.

So for each i = 1 to N, we do n[6] +=5

Apparently this is not logically OK. ?!
Or ?

[Sedefcho]

I found the error in my reasoning.

I think I know how to do it now. I will try it.

[Sedefcho]

Yes, right, I have it
Accepted P.E.
now.

I found the problem with my reasoning.

Actually the code I posted here and the reasoning behind it
was completely wrong.

Thanks, little joey!

[little joey]

Yes, it's realy quite simple once you see the light.
This problem took me months of struggling, an account of which can be found elsewhere on the board. But it's a good exercise in logic reasoning and it teaches you not to go after premature conclusions too fast.

[ThanhNhan]

Tricks to solve it fast are very cool. but Optimized DP is good enough to get accepted, not very fast around .3 second.

Running time : O(sum)

a[] is the input
t[] is the boolean function.

for (i = 1; i <= 6; i++)
if (a)
for (j = sum; j >= 0; j--)
if (t[j])
for (k = 1; k <= a; k++)
if (j + i * k > sum || t[j + i*k]) break;
else t[j + i * k] = 1;