Problem A: Snapper Chain Solution (Google Code Jam Qualification Round 2010)
Read the question here from GCJ Qualification Round 2010:
» Problem A: Snapper Chain
Once you understand how the snapper works, it is easy. This problem can be solved in various ways, but the main observations are:
Let k be the number of times you snap your finger, n be the light’s position, and assume 0 = OFF and 1 = ON.
The configuration of the first five snappers (with the first snapper on the far left side) as k increases are:
00000 k = 0
10000 k = 1
01000 k = 2
11000 k = 3
00100 k = 4
10100 k = 5
01100 k = 6
11100 k = 7
00010 k = 8
See the pattern? The configuration of the snapper for any k is the binary representation of k itself!
For example, when k=3 and n=3, we know that the light is OFF because the snapper is in the OFF position (because the 3rd bit of k=3 is 0). When k=3 and n=2, the light is ON. However, when k=5 and n=3, the light is OFF even though the 3rd bit is 1. As the 2nd bit is 0, the electric couldn’t “flow” to the light bulb.
Therefore, in order for a bulb to light, it requires all of the bits from 1 to n to be all 1s.
The problem can still be solved using arrays representing the bits and iterate through them to check, but it is more efficient using bit manipulation. If you are familiar with bit manipulation, you can check if the bits from 1 to nare all 1s using the XOR operation and some bit shifting. My solution is shown below. This is just one sample solution. If you have a more elegant solution, you are welcome to add to that in the comments section.
|
1
2
3
4
5
6
7
8
9
10
11
|
int T, n, k;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> n >> k;
cout << “Case #” << i + 1 << “: “;
if (((1 << (n–1)) ^ (k & ((1 << n)–1))) == ((1 << (n–1))–1)) {
cout << “ON\n”;
} else {
cout << “OFF\n”;
}
}
|
Foxboro DBA 