All submissions for this problem are available.
Do you know Charles and Xavier ? Charles and Xavier are two of the volunteers we have this year from first year.
They work hard but there is one problem they don't like each other.For every assigned task Charles wants to do it better
than Xavier and vice versa.
They are assigned a task to distribute the posters. They are provided with N piles of posters. Based on the number of
posters in each pile ,the whole N piles are arranged in non-decreasing order.In order to establish superiority,
they play a game on every continuous sub-sequence of poster piles. Charles having a slight
edge over Xavier is given the first turn and then they alternate.The player in focus can choose any one pile and remove
atleast one poster from it but the overall non-decreasing order must be maintained. Both Charles and Xavier play the
game optimally.The one who makes last valid move wins.
Your task is to determine how many continuous sub-sequence of poster piles will Charles win. After the game ends for each
subsequence, the number of posters of each pile will be recovered.
Continuous sub-sequence:Atleast two piles form a subsequence.
The first line contains N, the number of poster piles.
The second line containes N space separated integers denoting the number of posters in each pile (arranged from left to right).
A single integer denoting the continuous sub-sequence of poster piles Charles wins.
A[i]=number of poster in each piles.
1 1 2 2 3
Of the 10 continuous sub-sequence of poster piles,
Charles loses in [1,1],[1,1,2],[1,1,2,2],[1,2,2,3],[2,2] and wins in[1,1,2,2,3],[1,2],[1,2,2],[2,2,3] and [2,3] and hence 5.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.