| Submit | All submissions | Best solutions | Back to list |
TAILS - Tails all the way |
John and James planned to play a game with coins. John has 20 coins and he places it on the table in a random manner (i.e. either with heads(1) or tails(0) facing up). John asked James to convert all heads into tails in minimum number of flips with the condition that if a coin is flipped the coins present immediately to the right and left of the chosen coin should also be flipped.
Input
A single line with 20 space-separated integers
Output
The minimum number of coin flips necessary to convert all heads into tails (i.e. to 0). For the inputs given, it will always be possible to find some combination of flips that will manipulate the coins to 20 tails.
Example
Input: 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 Output: 3
Explanation of the Sample
Flip coins 4, 9, and 11 to make them all tails:
- 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state]
- 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping coin 4]
- 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping coin 9]
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping coin 11]
| Added by: | Infinity |
| Date: | 2011-03-21 |
| Time limit: | 1s |
| Source limit: | 5000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ADA95 ASM32 ASM64 BASH CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO ICON ICK LUA NEM NICE OCAML PIKE PRLG-swi SCM guile SCM qobi ST WHITESPACE |
| Resource: | Own |
hide comments
|
2019-08-19 18:23:45
https://www.spoj.com/problems/CERC07B/ 2-D version of the problem with better constraints and better test cases. |
|
|
2019-08-19 18:20:56
For people confused with 00000000000000000001 Solution doesn't exist. Hence, as per the problem statement, this case won't appear in set of test cases. (Would've been better had the statement asked to print -1 in such cases). |
|
|
2017-02-13 20:59:35
first try Last edit: 2017-02-13 20:59:50 |
|
|
2012-08-22 13:20:28 AC Srinivas
@Mathan Kumar i think there is no solution for this 00000000000000000001 |
|
|
2012-04-01 08:18:19 Mathan Kumar
What is the answer for 00000000000000000001 |
|
|
2012-02-26 13:51:39 Saikat Debnath
Test data is wrong.. For I/p : 11100000000000000000 If my output is : 1 WA and if my output is : 13 AC!! Guess I am making the same mistake as the problem setter.. :D :D |
|
|
2011-03-23 08:10:15 :D
In this problem you HAVE to print a newline after the result number. Infinity/Admin, please switch to "standard judge" in this and other problems and rejudge. It is causing pointless WA's. |
|
|
2011-03-23 08:10:15 Infinity
Solutions Rejudged. For the first coin only its right neighbour is flipped. And for the last coin only its left neighbour is flipped. |
|
|
2011-03-23 08:10:15 abhijith reddy d
Test Data is definitely wrong. |
|
|
2011-03-23 08:10:15 Oleg
Have strange feeling that something wrong with testcases... what happen if we flip first coin? |
RSS