×

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.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

19.8k350498541

 0 # include int res[100]; int p=0; void display(int m) { res[p++]=m; } int main() { int i, j, g, k, count[10][10], a[10][3], t, m; char s[10][10]; clrscr(); scanf("%d", &t); for(m=0;m

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 ?

-112
accept rate: 0%

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

(25 Jun '14, 17:40) 4★
 0 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 2★arpan_ 1 accept rate: 0%
 0 @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 answered 22 Jan '16, 19:37 1 accept rate: 0%

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&lt;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??

1
accept rate: 0%

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

1★arus_47
1
accept rate: 0%

 0 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 :) ) answered 25 Jan '17, 11:32 15.4k●1●20●66 accept rate: 18%

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==1||q==2) cout<<h<<endl; } else { if(i==q) cout<<h<<endl; else cout<<h+1<<endl; }

  }


} return 0; }

1
accept rate: 0%

 0 can anyone tell me what's wrong in this..? https://www.codechef.com/viewsolution/14978375 answered 15 Aug '17, 16:20 43●5 accept rate: 0%
 0 I am using the same logic but getting time limit exceeded error. Here is my code: Click Here answered 14 Nov '17, 08:44 1★nmsjha 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,719
×1,662
×952
×281
×17

question asked: 12 Nov '12, 18:20

question was seen: 10,241 times

last updated: 14 Nov '17, 08:46