 #1

CAKEWALK

# PREREQUISITES

Ad Hoc, Simple Math

# 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.

#2

# 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*, &a*, &a*);
for(j=0; j<a*; j++)
{
if (a* == 1)
s*[j] = 'H';
else
if (a* == 2)
s*[j] = 'T';
}
s*[j] = '\0';
for(j=1; j<=a*; j++)
{
for(k=0; k<j; k++)
{
if(s*[k] == 'H')
s*[k]='T';
else
s*[k]='H';
}

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

",res*);
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.

#3

#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
“,ctr);
}
else
{
printf(”%ld
",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 ?

please help/

#4

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?

#5

@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

#6

#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*= ‘h’;
}
else
{
arr*= ‘t’;
}
}
for(i=0;i<n;i++)
{
if(I==1)
{
arr*=‘t’; }
else
{
arr*=‘h’;}
for(k=i-1;k>=0;k–)
{
arr[k]= replace(arr[k]);
}
}
for(i=0;i<n;i++)
{
if(arr*==‘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??

#7

#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();
}

#8

i have also runtime error problem please help

#9

I executed your code @arus_47

Firstly, I removed that "include" 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" 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 :) )

#10

#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;
}

#11

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

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

#12

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

#13

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

#14

@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…

#15

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 .

#16

### 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;
}
``````