 CAKEWALK

# PROBLEM

In the game of Coin Flip there are initially N coins on the table. All these coins are either showing Heads or Tails. Let us say that the coins are arranged in a line, numbered from 1 to N.

You have to perform N operations in which you flip all the coins from position 1 to i in the ith round. You are to report the number of Heads / Tails after all the operations are complete.

# QUICK EXPLANATION

It is easy to see that at the end of the game the coins would be in alternating positions, starting with either Heads or Tails. Therefore, either

```HTHTHTHT...
```

Or,

```THTHTHTH...
```

Therefore, you can easily deduce the number of Heads or Tails at the end of the game.

# EXPLANATION

First, let us prove that the situation at the end of the game is indeed, alternating Heads and Tails.

Each coin is flipped a fixed number of times.

• The first coin has been flipped N times. Once in each round.
• The second coin has been flipped N-1 times. Once in each round except the first.
• And so on…
• The last coin has been flipped once.

We use the following insights,

• A coin flipped even number of times, will show the same side, as it did initially.
• A coin flipped odd number of times, will show the opposite side, of the one it did initially.

Now Let us consider two cases.

## N is even

We can use the following insights,

• All the coins at odd positions will be in their initial configuration.
• All the coins at even positions will be opposite to their initial configuration.
• There are as many even positions as there are odd positions.

Hence, no matter what the initial position is

• The number of coins facing Head and Tail are equal.

Thus, the answer will always be N/2, for the query of Heads as well as Tails.

## N is odd

We can use the following insights,

• All the coins at even positions will be in their initial configuration.
• All the coins at odd positions will be opposite to their initial configuration.
• There are floor(N/2) coins in even positions, and ceil(N/2) coins in odd positions.

Hence, no matter what the initial position is

• The number of coins that match the initial configuration are equal to floor(N/2).
• The number of coins that do not match the initial configuration are equal to ceil(N/2).

Thus, assuming integer division, the answer will be N/2, for the query that matches the initial configuration. Otherwise the answer will be N/2 + 1.

This can be summerized as in the code below.

```if (N % 2 == 0 || I == Q)
print(N/2)
else
print(N/2 + 1)
```

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.

4 Likes

# include <stdio.h>

``````int res;
int p=0;
void display(int m)
{
res[p++]=m;

}

int main()
{
int i, j, g, k, count, a, t, m;
char s;
clrscr();
scanf("%d", &t);
for(m=0;m<t;m++)
{
scanf("%d",&g);
for(i=0; i<g; i++)
{
scanf("%d %d %d", &a[i], &a[i], &a[i]);
for(j=0; j<a[i]; j++)
{
if (a[i] == 1)
s[i][j] = 'H';
else
if (a[i] == 2)
s[i][j] = 'T';
}
s[i][j] = '\0';
for(j=1; j<=a[i]; j++)
{
for(k=0; k<j; k++)
{
if(s[i][k] == 'H')
s[i][k]='T';
else
s[i][k]='H';
}

}
}
for(i=0; i<g; i++)
{
count[m][i]=j=0;
if(a[i] ==1)
while(s[i][j]!='/0')
{
if(s[i][j] == 'H')
count[m][i]++;
j++;
}
else
if(a[i] ==2)
while(s[i][j]!='/0')
{
if(s[i][j] == 'T')
count[m][i]++;
j++;
}
display(count[m][i]);
}
}
for(i=0;i<p;i++)
printf("%d\n",res[i]);
return 0;

}
``````

I have compiled my code even with linux, but it it showing runtime error. I am facing such problems for a long time. Please help.

#include<stdio.h>
#include<stdlib.h>
main()
{
int t,g,i,q;
long int n,j,ctr,k;
int a;
scanf("%d",&t);
while(t–)
{
ctr=0;
scanf("%d",&g);
while(g–)
{
scanf("%d%ld%d",&i,&n,&q);
a=(int
)malloc(n*sizeof(int));
for(j=1;j<=n;j++)
{
a[j]=i;
}
for(j=1;j<=n;j++)
{
for(k=1;k<=j;k++)
{
if(a[k]==1)
{
a[k]=2;
}
else if(a[k]==2)
{
a[k]=1;
}
}
}
for(j=1;j<=n;j++)
{
if(a[j]==1)
ctr++;
}
}
if(q==1)
{
printf("%ld\n",ctr);
}
else
{
printf("%ld\n",n-ctr);
}
}
return 0;
}

i have compiled and run my code in my turbo c++ dosbox and it ran correctly but it shows runtime error ie. sigsegv on the online judge… ie segmentation error… how to over come this ?

I have more or less used the same logic but my submission gives wrong answer.
http://www.codechef.com/viewsolution/5963715

Could someone tell me the corner cases?

@arpan…you’re not checking if i==q…in case n is odd…no of coins=n/2+1 when i is not equal to q…but n/2 if i==q

#include<stdio.h>
char replace(char);
int main()
{
int n,i,I,k,q,h=0,t=0,T,G;
char arr;
scanf("%d",&T);
while(T–)
{
while(G–)
{
scanf("%d",&G);
scanf("%d%d%d",&I,&n,&q);
for(i=0;i<n;i++)
{
if(I==1)
{
arr[i]= ‘h’;
}
else
{
arr[i]= ‘t’;
}
}
for(i=0;i<n;i++)
{
if(I==1)
{
arr[i]=‘t’; }
else
{
arr[i]=‘h’;}
for(k=i-1;k>=0;k–)
{
arr[k]= replace(arr[k]);
}
}
for(i=0;i<n;i++)
{
if(arr[i]==‘h’)
{
h++;
}
else
{
t++;
}
}
if(q==1)
{
printf("%d",h);
}
else{
printf("%d",t);
}
}
}

``````return 0;
``````

}
char replace(char ch)
{
if(ch==‘h’)
{
ch=‘t’;
}
else
{
ch=‘h’;
}
return(ch);
}

its showing runtime error. please someone tell me why??

#include
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
void coin1()
{
long int t,j,k,i,n,g,c=0,d=0,m,q;
cin>>t;
while(t>=1)
{
cin>>g;
char a[g];
while(g>=1)
{

``````			cin>>i>>n>>q;
for(j=1;j<=n;j++)
{
if(i==1)
{
a[j]='H';
}
else if(i==2)
{
a[j]='T';
}
}
for(k=1;k<=n;k++)
{
for(j=1;j<=n;j++)
{
if(j<=k)
{
if(a[j]=='H')
{
a[j]='T';
}
else if(a[j]=='T')
{
a[j]='H';
}
}

}
}
j=1;
while(j<=n)
{
if(a[j]=='H')
{
c++;
//cout<<c<<endl;
}
else if(a[j]=='T')
{
d++;
}
j++;
}
if(q==1)
{
cout<<c<<endl;
}
else if(q==2)
{
cout<<d<<endl;
}
c=0;
d=0;
g--;
}
c=0;
d=0;

t--;
``````

}
}

``````int main()
``````

{
coin1();
}

Firstly, I removed that “include<bits stdc++.h=”">" as it led to fatal error.

After that, I put in custom input of Sample case and your code passed. I think that line was the problem.

I suggest removing “include<bits stdc++.h=”">" from your code

(EDIT-The correct code is #include < bits/stdc++.h > Also, the ‘#’ were missing in first three lines. Please see to it dear!) (Upvote if you like my answer, so that I can also ask questions )

1 Like

#include
using namespace std;
int main()
{
int t,n,i,g,q;
cin>>t>>n;
while(t–)
{
while(n–)
{
int h=0;
cin>>i>>g>>q;
h=g/2;
if(g%2==0)
{
if(q==1||q==2)
cout<<h<<endl;
}
else
{
if(i==q)
cout<<h<<endl;
else
cout<<h+1<<endl;
}

``````  }
``````

}
return 0;
}

can anyone tell me what’s wrong in this…?

https://www.codechef.com/viewsolution/14978375

I am using the same logic but getting time limit exceeded error.
Here is my code:

My Code Exceeds Time Limit
Can anyone help me with this code
https://ide.geeksforgeeks.org/UWvwhmGwH0

@jatin_b it seems you have removed conio.h but have forgotten to remove clrscr(); from your code…
I wonder how can your code posted can compile sucessfully in linux then…
Resubmit it now…
Hope it doesn’t show RTE then…

You are declaring too much memory for a . The limit for n is 1 ≤ N ≤ 10^9 .you can`t have so much memory . In turbo C++ also if you also try to run for such big value I am sure it won`t run . try to do this without having so much memory .

### Can anyone tell me what is the problem with this code?

``````// Problem Code: CONFLIP on codechef
#include<iostream>
#include<math.h>

using namespace std;

int main(){
int T;
cin>>T;

for(int t=1;t<=T;t++){
int G;
cin>>G;
for(int g=1;g<=G;g++){
int I,N,Q;
cin>>I>>N>>Q;

int coinsInterested = Q==1? (I==1?N:0) : (I==2?N:0) ;

int changes = ceil(float(N)/2);

if(coinsInterested==0){
coinsInterested+=changes;
}
else{
coinsInterested-=changes;
}

cout<<coinsInterested<<endl;
}
}

return 0;
}
``````

Can you please identify the issue with this code? It’s a short solution won’t take much of your time. I have been stuck at this for more than an hour now. What’s wrong?

The sample cases run okay. But in submission, I get wrong answer.
Also, I am failing the following case (someone mentioned in the comments on a post) -
Input -
2
2
1 5 1
1 5 2
1
1 5 1

Expected Output -
2
3
2

But my program terminates after the second line.

``````#include <iostream>
using namespace std;

int main() {
int tcases; cin >> tcases;

// declare variables
int g,i,q=0; long int n=0;

for(int i = 0; i < tcases; i++){

cin>>g;
for (int j = 0; j < g; j++)
{
cin>>i>>n>>q;
if(n%2==0) cout<<n/2;
else (q==i) ? (cout<<(n-1)/2):(cout<<(n+1)/2);
printf("\n");
}

}
return 0;
}``````

You should take G as input before the while loop of G

you are using i for the test cases loop and also for initial state of the coins,it is causing conflict.Use k or some other variable in the tcases loop instead of i,it will run perfectly.

I am using the same logic but still getting the wrong answers. Can anyone helps me?

if name == “main”:
try:
t = int(input())
for i in range(t):
g = int(input())
for j in range(g):
arr = list(map(int,input().split()))
if arr%2 == 0:
print(arr//2)
break
else:
if arr == arr:
print(arr//2)
elif arr != arr:
print((arr//2) + 1)
except EOFError:
pass

Here is my code in python.