Can any one explain me the 4th test case of the above question. How the answer is 8?
The link to the problem is as below:
Thanks in advance.
Naomi : 0.186 0.300 0.389 0.557 0.832 0.899 0.907 0.959 0.992 Ken : 0.215 0.271 0.341 0.458 0.520 0.521 0.700 0.728 0.916
In deceitful war Naomi will fake as follows:
Original Faked Result
0.186 0.915 Ken will choose 0.916 and Ken wins
0.300 0.729 Ken will choose 0.215 and Naomi wins
0.389 0.730 Ken will choose 0.271 and Naomi wins
0.557 0.731 Ken will choose 0.341 and Naomi wins
0.832 0.832(no need to fake) Ken will choose 0.458 and Naomi wins
0.899 0.899(no need to fake) Ken will choose 0.520 and Naomi wins
0.907 0.907(no need to fake) Ken will choose 0.521 and Naomi wins
0.959 0.959(no need to fake) Ken will choose 0.700 and Naomi wins
0.992 0.992(no need to fake) Ken will choose 0.728 and Naomi wins
The trick here is that Ken chooses weight by greedily looking at best for the current situation, so when Naomi fakes 0.915 Ken looks for a weight just greater than 0.915 and finds 0.916 but when Naomi fakes 0.729 Ken couldn’t find a weight greater than 0.729 so he chooses 0.215( Minimum available weight , as he knows that he’ll lose this round anyhow he selects the lightest weight to keep his future chances bright).
5 Likes
My solution yesterday(unmodified):small input correct.
enter code here
#include<stdio.h>
#include<conio.h>
#include<fstream.h>
#include<io.h>
void main()
{
clrscr();
FILE *fp1,*fp2;
fp1=fopen(“test.txt”,“r”);
fp2=fopen(“out1.txt”,“w”);
int tot,i;
fscanf(fp1,"%d",&tot);
for(i=1;i<=tot;i++){
printf(“Case #%d: “,i);
int n;
fscanf(fp1,”%d”,&n);
i=1;long float naomi[10],ken[10];
for(i=0;i<n;i++){
long float temp;
fscanf(fp1,"%lf",&temp);
naomi[i]=temp;}
i=0;
for(i=0;i<n;i++){
long float temp;
fscanf(fp1,"%lf",&temp);
ken[i]=temp;}
i=0;
int j=0;
int decwar=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(ken[i]<naomi[j])
{
decwar=decwar+1;goto step;
}
}
step:}
printf("%d ",decwar);
int war=0;
//for naomi
i=0;j=0;
int x=naomi[i],pos;i++;
while(i<n){
if(x<naomi[i]){x=naomi[i];pos=i;i++;}
else{i++;}
}
int maxnaomi=x;
//for ken
i=0;j=0;
int x1=ken[i],pos1=0;i++;
while(i<n){
if(x1<ken[i]){x1=ken[i];pos1=i;i++;}
else{i++;}
}
int maxken=x;
while(maxnaomi>maxken){
war=war+1;
i=0;
int x2=ken[i];int pos2=0;i++;
while(i<n){
if(x2>ken[i]){x2=ken[i];pos2=i;i++;}
else{i++;}
}
int minken=x2;
naomi[pos]=0;
ken[pos2]=0;
//for naomi
i=0;
int x=naomi[i],pos;i++;
while(i<n){
if(x<naomi[i]){x=naomi[i];pos=i;i++;}
else{i++;}
}
int maxnaomi=x;
//for ken
i=0;j=0;
int x1=ken[i],pos1=0;i++;
while(i<n){
if(x1>ken[i]){x1=ken[i];pos1=i;i++;}
else{i++;}
}
int maxken=x1;
}
printf("%d\n",war);
}
getch();
}}
}
Thanks a lot.