http://code.google.com/codejam/contest/dashboard?c=433101#s=p0

You can find the problem description above! Believe me it's so much of fun to solve this!!

Go ahead and try!!!! I could not believe after I got the solution!.....Ufffff.......

Hint :: Think in bits!!

Approach ::

Lets say we have 2 snappers (N =2)-

Initially both are in OFF state

Remember : With a snap, only the snapper receiving power changes state!!!

See the bit pattern ?? Lets say OFF = 0; and ON = 1

So, if there are N snappers, we will turn the light on when K = [2 (power) N ] - 1

In the above case, N = 2, K = pow(2,2)-1 = 3. , After that, a snap will get us to the initial state!!

Isn't it simple and great!!!!!!!!

===================================================

You can find the problem description above! Believe me it's so much of fun to solve this!!

Go ahead and try!!!! I could not believe after I got the solution!.....Ufffff.......

Hint :: Think in bits!!

Approach ::

Lets say we have 2 snappers (N =2)-

Initially both are in OFF state

Remember : With a snap, only the snapper receiving power changes state!!!

OFF | OFF | Initial State |

ON | OFF | After snap k =1 |

OFF | ON | After snap k =2 |

ON | ON | After snap k =3 |

OFF | OFF | Snap k =4 |

See the bit pattern ?? Lets say OFF = 0; and ON = 1

0 | 0 | Initial State K=0 |

1 | 0 | K=1 |

0 | 1 | K=2 |

1 | 1 | K=3 |

0 | 0 | K=4 |

So, if there are N snappers, we will turn the light on when K = [2 (power) N ] - 1

In the above case, N = 2, K = pow(2,2)-1 = 3. , After that, a snap will get us to the initial state!!

Isn't it simple and great!!!!!!!!

===================================================

```
int main () {
int n,k,num_cases;
int factor,i;
FILE *fp;
fp = fopen("A-large-practice.in","r");
if (!fp) {
exit(0);
}
fscanf(fp,"%d",&num_cases);
for (i = num_cases ; i > 0; i--) {
fscanf(fp,"%d %d", &n, &k);
factor = pow(2,n);
printf("Case #%d: ",num_cases-i+1);
if (k%factor == (factor-1))
printf("ON\n");
else
printf("OFF\n");
}
fclose(fp);
```

```
}
```

## No comments:

Post a Comment