PROBLEM LINKDIFFICULTYCAKEWALK PREREQUISITESAd Hoc, Simple Math PROBLEMIn 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 i^{th} round. You are to report the number of Heads / Tails after all the operations are complete. QUICK EXPLANATIONIt 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. EXPLANATIONFirst, 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.
We use the following insights,
Now Let us consider two cases. N is evenWe can use the following insights,
Hence, no matter what the initial position is
Thus, the answer will always be N/2, for the query of Heads as well as Tails. N is oddWe can use the following insights,
Hence, no matter what the initial position is
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 SOLUTIONCan be found here. TESTERS SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Nov '12, 18:20

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. answered 13 Nov '12, 01:53
@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..
(13 Nov '12, 02:04)

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? answered 22 Jan '15, 22:02

include<stdio.h>char replace(char); int main() { int n,i,I,k,q,h=0,t=0,T,G; char arr[1000]; 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="i1;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); } } }
} char replace(char ch) { if(ch=='h') { ch='t'; } else { ch='h'; } return(ch); } its showing runtime error. please someone tell me why?? answered 14 Aug '16, 16:55

include<iostream>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) {
} }
{ coin1(); } answered 24 Jan '17, 02:15

I executed your code @arus_47 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 (EDITThe 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 :) ) answered 25 Jan '17, 11:32

include<iostream>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==1q==2) cout<<h<<endl; } else { if(i==q) cout<<h<<endl; else cout<<h+1<<endl; }
} return 0; } answered 11 Jul '17, 21:16

can anyone tell me what's wrong in this..? answered 15 Aug '17, 16:20

I am using the same logic but getting time limit exceeded error. Here is my code: Click Here answered 14 Nov '17, 08:44
