Run Or No Run
All submissions for this problem are available.
The T20 Cricket Tournament, Indian League of Premiers is just around the corner….and as usual the favorites are the Coding Super Kings.The team managers are working very hard and the players are also preparing day in and day out.
One such player is Ash. He is an off-spinner, with plenty of experience to his name in T20 cricket. But Ash this time wants to perform much better than how he did in his previous years. He feels that apart from regular training, he should also look into his previous stats to check where and how he can improve his game. He makes a list of all T20 games he has bowled in. Let this number be ‘N’. He then writes down the result of each and every ball he has bowled in all the games. The result can only be a ‘0’ or a ‘1’. ‘0’ implies a wicket or no(zero) run. ‘1’ implies he has conceded runs. The number of balls in each game can be taken as the variable ‘L’.
If he has bowled in 2 games, with 5 and 6 balls respectively in each game, he would have made something like this.. 10101, 011010
If some ball has not been specified, like the 6th ball in the former case, then assume it to be ‘0’. The extra ball should be added to the extreme left end.
Using these details, he wants to find the following…
For each game X in the list of ‘N’ games, if there exists some other game Y such that at the same ball(for all balls in the game) in both X and Y, runs have not been scored off, that is both TOGETHER should NOT be a 1(that is either one of them can be a 1 or none of them can be a 1), then count it. If no such game Y exists for a given X, then do not count it. Now ash wants to count the number of games for which the above condition holds good.
Since Ash is highly experienced, he has bowled a large number of games, he cannot find the answers manually. So he requests you to help him. But Ash also has another condition. He will give you the decimal notation for the balls in each game. For example… 10101 would be represented as 21.
For 2 games, 10 and 4. The binary equivalents are 1010 and 100. For the game 10, 4 satisfies the rule that no two balls have got 1 at the same instance. Hence for 10 the answer is 4. Similar explanation can be given for 4 whose answer is 10. So the count will be 2.
For the case 4, 2, 3 …
4 -> 100
2 -> 010(Add extra ball to the extreme left)
3 -> 011(Add extra ball to the extreme left)
(4,2) -> satisfies the rule that at no two balls for 4 and 2 exists two 1s.
(4,3) -> satisfies the rule.
(2,4) -> satisfies
(2,3) -> does not satisfy. The 2nd ball from the right are 1s in both the games.
(3,4) -> satisfies
(3,2) -> does not satisfy
Since 4,2 and 3 all satisfy the condition, the answer for this case is 3.
In T20 cricket, the maximum number of balls bowled by a bowler in each game is limited to 24.
Could you solve the above problem for him…?
The first line consists of T, the number of testcases. This is then followed by N, the number of games for each testcase. This is then followed by N space separated numbers denoting the decimal equivalent of the score of each game.
The Output consists of 1 line representing the answer for each testcase followed by a new line.
1 <= T <= 100
1 <= N <= 1,000,000
1 <= L <= 24
1 2 3
2 3 4 5
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.