147 - Dollars

[raphaeljpb]

Hi, this is my first thread. I can't recognize what's problem below. The code shows correct results at least $50, but I don't know the problem for bigger amounts.
Thanks in advance.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 6001

int main() {

float quantidadeReal;
int quantidadeInteira = 0;
int tipos[] = { 1,2,4,10,20,40,100,200,400,1000, 2000 };
int i, j, numeroDeTipos = 11, c;
double * contagem;


while (1) {
scanf("%f", &quantidadeReal);
if (!quantidadeReal) break;
contagem = calloc(SIZE, sizeof(double));

quantidadeInteira = (int) (quantidadeReal * 100);
quantidadeInteira /= 5;
contagem[0] = 1.0;
for(i = 0; i < numeroDeTipos; i++) {
c = tipos;
for (j = c ; j <= quantidadeInteira; j++) {
contagem[j] += contagem[j-c];
}
}
printf("%7.2f %.0lf\n", quantidadeReal, contagem[quantidadeInteira]);

free(contagem);
}


return 0;
}

[gradientcurl]

so far, never get to see any posted test cases. Here is a test output which I'm sure I've got it wrong somewhere:

Code: Select all

300.00  181490736388615
299.95  181000196059736
299.90  180510857366624
299.85  180510857366624
299.80  180510857366624
299.75  180022694940816
299.70  179535708782312
299.65  179535708782312
299.60  179535708782312
299.55  179049898891112
299.50  179049898891112
299.45  178565265267216
299.40  178081807910624
299.35  178081807910624
299.30  178081807910624
299.25  177599526821336
299.20  177118397097689
299.15  177118397097689
299.10  177118397097689

below is my code

Code: Select all

removed after AC

[Jan]

Check the set.

Set:

Code: Select all

  0.11                0
  0.12                0
  0.13                0

Hope it helps.

[gradientcurl]

tks jan. didnt take the double to integer conversion seriously.

[shankar]

i dont no whether my algorithm is right. for higher numbers it goes wrong i guess. so can some one helpme.
thanks

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;
unsigned long long a[6001][11]={0};int limit;
void dollar()
{int i,j,d[11]={1,2,4,10,20,40,100,200,400,1000,2000};




	for(i=0;i<11;a[0][i]=a[1][i]=1,++i);
	
	for(i=2;i<=6000;i++)
	{ 	a[i][0]=1;
		for(j=1;j<11;j++)
		{
			if(i<d[j])
			{
				a[i][j]=a[i][j-1];			
			}
			else
			{unsigned long long l=0;
				while(l<=i)
				{	
					a[i][j]+=a[i-l][j-1];l+=d[j];
				}
			}
		}
	}

}
int main()	
{float g;int f,i,p,w;
	limit=1;
	for(i=0;i<6001;i++)
		for(f=0;f<11;a[i][f++]=0);
	dollar();

	while(1)
	{	scanf("%f",&g);
		f=(int)(g/0.05);
		
		
		printf("%d ",g);
		if(f==0)
			return 0;
		
		
		cout<<a[f][10]<<endl;
//		printf("%17ll\n",a[f][0]);
	}
}

[Jan]

Check the set.

Set:

Code: Select all

  0.70               24
  0.90               39
  0.11                0
  0.12                0
  0.13                0
  0.14                0

And your presentation is wrong, too.

[Itachi-Forsaken]

I have a question regarding the output
Since the output is tabbed, I assume you have to use printf (for C/C++)
So what is the symbol after % for long long? Like 'd' is for integer

Also is there a way to properly convert a float to an integer? Or do you have to use a string and analyze it..

Thanks in advance

[Jan]

'%lld' for long long.

[andysoft]

Hello!
I am solving this prob and my algo works ok (at least i think so), but I cannot output large numbers. I used and use unsigned long long type, and printf("%lld\n",ans), but values for 300.00 input are either negative (-1600..00) or too small (like 2500000). Now I threw out the printf and used cout. I hope you may help me.

Code: Select all

#include <stdio.h>
#include <math.h>
#include <iostream>
int main(int argc, char* argv[]) {
	unsigned long long a[6001];
	int d[11] = {1,2,4,10,20,40,100,200,400,1000,2000};
	float x;
	int i,j,v,c;

	for (i=1; i<=v; i++)
		a[i] = 0;
	a[0] = (unsigned long long)1;

	for (i=0; i<11; i++) {
		c = d[i];
		for (j=c; j<=6000; j++)
			a[j] += a[j-c];
	}

	while (1) {
		scanf("%f",&x);
		if (x==0.0) break;
		v = (int)floor (x*20 + 0.1);
		printf ("%6.2f",x);
		std::cout.width(17);
		std::cout << a[v] << std::endl;
	}

	return 0;
}

EDIT: Debugger watches prove that my algo's right. Ans for 300.00 in watch is 181490736388615, but how to output it??

[andysoft]

Hi again!

1) Well, I re-wrote it in Pascal in just 2 minutes and got AC from the first time, BUT I still want to know the answer to my question about C/C++ output.
2) My prog ran during 0.346 seconds and I am 1383 / 1763 in the ranking. I would like to know how can I improve my code, if its structure is like this:

Code: Select all

1. Precompute all values from 1 to 6000 with usual for-loop: for each coin cost C do a[i] += a[i-C], a - 1..60000.
2. Read the input real number, multiply it by 25 and write the needed value from array a.
3. Types are: integer (int) everywhere except array a. It is int64 (long long)

[emotional blind]

All coin coin value is multiple of 5c
so just divide all coins by 5
and coins will be {2000c,1000c,400c,200c,100c,40c,20c,10c,4c,2c,1c}

Also divide your input by 5c

so you will require array of size 6000 only

thanks

[andysoft]

Yes, I have made it: divided everything needed by five.

[Kallol]

where am I wrong ??

here is my code :

Code: Select all

removed after AC

I checked almost all the input I got , I am getting WA . Is my output style wrong ??

[mmonish]

>>Kallol
Try this case

Code: Select all

Input
5.10
Output
  5.10             6622

Try to avoid double calculation.It gives u WA.
Hope it helps.

[Kallol]

I am really very much astonished with the behaviour of double in C.

double x = 5.10

x*=100;

printf("%0.lf",x);

and u will get 5.09 !!!


this is just horrible ...I thought , this floating point error is not there in double precision which was in the float data type. But it exists even in Long double .

Neway thanks for helping me with that tricky input. How could u guess and generate that input anyway ?? double gave me correcty answer in almost every othe cases