A Horcrux is an object in which a Dark wizard or witch has
hidden a fragment of his or her soul for the purpose of attaining
immortality. Constructing a Horcrux is considered Dark magic of the
foulest, most evil kind, as it violates laws of nature and morality, and
requires a horrific act (a.k.a. murder) to accomplish.
There are two kinds of horcruxes, the white one, denoted as △, and the black one, denoted as ▲.
Topper has got N horcruxes, and he wants to destroy them to win the
Dark wizard. Toper places all the horcruxes in a line from left to
right, one by one, and then says a magic spell to destroy them. In order
to make the magic spell works, Toper needs to know the number of the
white horcruxes.
Since the horcruxes also has magic, when placing the horcruxes, they
will change color from white to black or from black to white under the
following rules:
When Topper places the i-th horcrux and i is an even number: If the
i-th horcrux and the rightmost horcrux have different colors, all
consecutive horcruxes of the same color on the right change its color.
For example, suppose the horcruxes on the line are:
△△▲▲△△△
After placing 7 horcruxes.
If the 8-th horcrux is white, since its color and the color of the
rightmost horcrux are the same. Therefore, the horcruxes on the line
become as follows:
△△▲▲△△△△
If the 8-th horcrux is black, since its color and the color of the
rightmost horcrux are different, the 3 consecutive white stones on the
right change their color. Therefore, the stones on the line become as
follows:
△△▲▲▲▲▲▲
You see, it’s not an easy job to beat the Dark wizard. So write a program to help Topper.
There are some test cases. In each test case, the first line
contains a positive integer n (1≤n≤100,000), which is the number of
horcruxes. The following n lines denote the sequence in which Topper
places the horcruxes. 0 stands for white horcrux, and 1 stands for black
horcrux.
For each test case, output one line containing only the number of white horcruxes on the line after Topper places n horcruxes.
#include <stdio.h>
typedef struct _Node{
int color;
int num;
}Node;
void main(){
int n, t, whites, i, tmp;
Node stack[100000];
int top = -1;
while(scanf(" %d", &t) != EOF){
i = 0;
top = -1;
while(t--){
i++;
scanf(" %d", &n);
if(top < 0){
stack[++top].color = n;
stack[top].num = 1;
continue;
}
if(n != stack[top].color){
if(i%2 == 0){
tmp = stack[top--].num + 1;
if(top<0){
top = 0;
stack[top].num = tmp;
stack[top].color =n;
}else{
stack[top].num += tmp;
stack[top].color = n;
}
}else{
stack[++top].color = n;
stack[top].num = 1;
}
}else{
stack[top].num++;
}
}
whites = 0;
while(top>=0){
if(stack[top].color == 0){
whites += stack[top].num;
}
top--;
}
printf("%d\n", whites);
}
}