Game U-turn is a card game of patience, played by a single player. Given a sequence
of cards with some cards face up and others face down at arbitrary positions, a player is
required to perform a series of operation called U-turn to make all cards face up without
altering positions of cards in the sequence. A U-turn operation is performed on a sub-string of
cards of any length to u-turn the face of each card in the sub-string, i.e., if the face of a card is
up then put it down and if it is down then put it up, without altering positions of cards in the
sub-string. The effort of a U-turn operation is the length of the sub-string on which the
operation is performed. The series of U-turns should be such that the effort of each U-turn
operation is distinct and the total effort of the series of operations is minimum.
Write a program to find the total minimum effort required to make all cards of a given
sequence face up using a series of U-turn operation. Assume that the sequence of cards is
represented by a string of 0’s and 1’s where a zero represents a card with face up and a one
represents a card with face down.
Input may contain multiple test cases.
Each test case has a single input line containing a string of 0’s and 1’s. The length of the string is fifteen or less.
Input terminates with a line containing 0 as the input for a test case.
For each test case, print the total minimum effort required.
1000101 001100010 1010100000 0
9 3 7
Migrated from old NTUJ.
ICPC Kanpur, 2008
| No. | Testdata Range | Score |
|---|