Bytelandian gold coins

#include
using namespace std;
int main()
{
unsigned long int g,c; int t=10;
while(t–)
{cin>>g;
c=g/2;
c=c+g/3;
c=c+g/4;
if(g>c)
cout<<g;
else
cout<<c;

}

return 0;
}

This cannot be the final solution. When you have a gold coin worth g, you exchange it with coins worth g/2,g/3,g/4.

Now to make maximum profit, you must still exchange coins worth g/2,g/3,g/4.

Example:

for 12, you may exchange them to 5,4,3 totalling 13. Further exchange of coins 5,4,3 would not give any profit.

for 24, on exchanging, you get 12,8,6 totalling 26. 8,6 on further exchanges would not give any profit. But 12 on exchanging gives coins worth 13. So this is optimal. And thus answer for 24 is 27.

1 Like