All submissions for this problem are available.
A was playing with N piles of cubic stones of same dimensions. Each pile could be increased or decreased by adding or removing stones to it. So, he decided to put them in such a order that
the stones in ith pile is equal to the stones in (N+1-i)th, i.e., H[i] = H[N+1-i].
It is also said that the height of each pile indexed from 1 to N/2 are in single step increasing order and then from N/2 to N it decreases in single step. Output the number of piles on which he should work to make the required pattern
Required pattern of piles are shown in two figures 1 and 2.
Figure 1 shows the pattern when N is 8 (i.e., even).
Figure 2 shows the pattern when N is 9 (i.e., odd).
- First line contains T denoting the number of test cases.
- Next T lines contains N the numbers of piles.
- Next line contains N space separated heights of each pile.
- Print minimum number of piles on which he should increase or decrease the stones so that he obtains the required pattern.
- 1 <= T <= 100
- 1 <= N <= 100000
- 1 <= H[i] <= 100000
Input: 2 4 1 2 2 1 5 1 2 1 3 1 Output: 0 2
Case 1 : Here all the piles are in increasing and then decreasing order of single step.So no pile need to be worked upon.
Case 2 : Here we need to make the given input of heights in 1 2 3 2 1. For that we need to remove and add only in 4th and 3rd pile respectively.So the answer is 2.
|Time Limit:||0.5 - 0.85 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.