Mixtures

how do we know the input limit??

@hrishikesh Read input until you encounter an EOF.

how do I use EOF with scanf ?

scanf() returns the number of characters successfully read from stdin. Use this information to use EOF with scanf.

Can the color of the mixture repeat ?

I meant in a given set, could there be multiple mixtures of the same colors ?

There might be test cases like that.

No. They are in a line.

can we mix 40 and 20 skipping the 60 in between?

I just answered that in the comment directly above yours..

Hello Stephen

can someone paste some tricky test case for this problem.Have broken my head but can't figure out the problem with my solution.

Have you checked your program for values of N for which you can verify the solution using brute-force?

Is there a limit to the size in which final answer of smoke would fit in ?

im using

while(scanf("%d",&n) > 0){  // take n inputs and print output }

i guess it should terminate when there is no input?

anybody who has solved this problem using memoization or using simple recurssion without getting TLE ? ? ?

@Ankush.. dude everyone has solved the problem via DP.. and if you are getting TLE and u think that u have implemented the DP correctly, the only probable reason is that you are not detecting the EOF properly.. thats why your code is never able to stop!!

can ne1 post the solution of this prob...nt able to solve this...me a novice :(

i am learning dp could anyone tell that is this is dynamic problem or greedy problem and how can i check out that is this dynamic problem or greedy.....???

can u people pls tell me the commands for taking the no if test cases pls...pls

Hey what will be the o/p of the following i/p

5
40 60 20 9 10

My ans is 2400

Succesfull submitter answers 2870

40*60 will be used first since (40+60)%100 gives us 0 that makes rest 0 , so the answer should be 2400

Yups answer is 2870 .. i forgot to add rest smoke..

hint : matrix multiplication problem

please tell me for what input it will give incorrect answer.............??

#include<stdio.h>

int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int col[n+1],i,j,min,temp,x,y,k;
unsigned int fume;   
fume=0;
for(i=0;i<n;i++)
{
scanf("%d",&col[i]);
}
i=0;
j=1;
min=1000;

while(n>1)
{
i=0;
j=1;
while(i!=n-1)
{
while(j!=n)
{
temp=(col[i]+col[j])%100;
if(temp<min)
{
min=temp;
x=i;
y=j;
}
j++;
}
i++;
}
fume=fume+col[x]*col[y];
col[x]=min;
min=1000;
for(k=y;k<n-1;k++)
{
col[k]=col[k+1];       
}
n--;
}
printf("%dn",fume);
}           
return 0;
}

sir,

will u give me the input file for which it gives the incorrect answer............???

can anyone pls tell me if the following approaach is correct or not

everytime we chose those two adjacent mixtures which giv least value of  (a+b)mod 100 as compared to other pairs

Can you prove that will always lead to the best answer? If you can't prove it, it's normally wrong.

thanx alot stephen ala got AC

@Stephen: Can you please give me a testcase where my solution is giving the incorrect result?

Hi Stephen, I've tried many testcases and all given correct answers. I'm not sure which one creating the problem. Can you please help me by providing a testcase? 

Your code doesn't even work on the sample input.

Hi Stephen, In my end it is perfectly work for the sample input as well as the inputs written in the comments. I also tried with 100 inputs and got the correct result. Can you please let me know the poblem testcase?

Understood the problem. I've taken input from console instead of the file.

Nothing is wrong with taking the input from a console; but your program only outputs 342 for the sample input; it never gets to output 2400 as well.

http://www.codechef.com/viewsolution/475504

can sum1 tell what is wrong in my solution. It is giving correct answers for the sample input and also of the random inputs. I have checked it with solutions submitted by other persons. But on submitting my solution it shows wrong answer.

Those who are getting wrong answers,can check some test cases here:https://www.spoj.pl/forum/viewtopic.php?f=3&t=4007&p=16920&hilit=MIXTURES#p16920

7
60 44 33 67 9 90 34

for this case on the mention site answer is 8207

and my ans is 6159

60*44+33*67+0*4+4*9+13*90+3*34=6159

it can cum as

60 44 0 9 90 34

04 0 9 90 34

4 9 90 34

13 90 34

3 34

37

so explain this answer...

leave it i was checking from wrong soln by mistake..