Google CodeJam 2010 has begun! In the valiant struggle with program debugging and algorithm optimization, the winners (top 24 wordwide) are going to be generously awarded (1st Prize is $5000).
To enter the contest, you need clear a qualification round (took place on 8th May 2010) which lasts for 24hrs. Presented with 3 problems, the contestant is expected to get a score of 33 to qualify for Round 1. The finals is going to be held at Dublin.
Well, coming to the problems that came up in the qualifier round, I solved 2 /3. Had only 3 hours for the event to end when I came online yesterday (thanks to crappy bsnl broadband!)
Problem 1: Snapper Chain
The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.
When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers -- making a clicking sound -- any Snapper receiving power at the time of the snap toggles between the ON and OFF states.
In hopes of destroying the universe by means of a singularity, I have purchased N Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper.
Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.
I keep doing this for hours. Will the light be on or off after I have snapped my fingers K times? The light is on if and only if it's receiving power from the Snapper it's plugged into.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each one contains two integers, N and K.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "ON" or "OFF", indicating the state of the light bulb.
Limits
1 ≤ T ≤ 10,000.
Small dataset
1 ≤ N ≤ 10; 0 ≤ K ≤ 100;
Large dataset
1 ≤ N ≤ 30; 0 ≤ K ≤ 108;
Sample
Input:
4
1 0
1 1
4 0
4 47
Output:
Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON
My Solution:
Language Used: C++
Code:
//Vignesh M
#include<iostream.h>
#include<fstream.h>
#include<stdio.h>
using namespace std;
int Solution(int n, long long double k);
long long double PowerFx(long long double expov)
{
long long double ExpValue=1;
for(long long double MyTicker=0;MyTicker<expov;MyTicker++)
ExpValue*=2;
return(ExpValue);
}
int main()
{
int n;
long long double k;
ifstream inStream;
inStream.open("myQuestion.in");
ofstream outStream;
outStream.open("myAnswer.out");
int T=0; inStream>>T;
for(int tcount=0;tcount<T;tcount++)
{
inStream>>n;
inStream>>k;
if(Solution(n,k)) outStream<<"Case #"<<tcount+1<<": ON\n";
else outStream<<"Case #"<<tcount+1<<": OFF\n";
}
return 0;
}
int Solution(int n, long long double k)
{
int TickingMyTicker=1;
long long double IncrementValue;
IncrementValue= (PowerFx(n)-1)+((TickingMyTicker-1)*PowerFx(n));
int res=-1,SwitchStateFlag=0;
if(k<IncrementValue)
{
res=0;
SwitchStateFlag=1;
}
else if(k==IncrementValue) res=SwitchStateFlag=1;
else
{
while(k>IncrementValue)
{
TickingMyTicker++;
IncrementValue= (PowerFx(n)-1)+((TickingMyTicker-1)*PowerFx(n));
if(k < IncrementValue)
{
res=0;
SwitchStateFlag=1;
}
else if(k==IncrementValue)res= SwitchStateFlag=1;
}
}
if(!SwitchStateFlag) res=0;
return res;
}
The Program works for both small and large datasets.