The Two Towers
All submissions for this problem are available.Ajeyaa and Sriram are experimenting with a block simulator. The simulator generates a tower of $N$ blocks. Each block in the tower has a unique value assigned to it. Both of them decide to rearrange the tower to make it look aesthetically more pleasing, with each having thought of a different way of doing it. Ajeyaa wants to arrange them such that the block values are in ascending order from top to bottom, while Sriram wants the block values in descending order from top to bottom. To move a block, one can take it out and insert it between any 2 blocks. It can also be placed on top or inserted at the bottom. It takes 2 seconds to move one block from its original position to any other position. Unable to decide upon which method to use, both of them agree to use the method which uses the shortest time (that is, they will arrange the blocks either in ascending or descending order from top to bottom, depending on which method takes the shortest time). Find whose arrangement will be final and also find the minimum number of blocks which need to be moved. ###Input: The first line contains one integer $N$, the number of blocks present. The next line consists of $N$ integers $a,a,...,a[N]$, which represent the values present on the block from top to bottom. ###Output: The first line should be whose arrangement is used, i.e, $Ajeyaa$ or $Sriram$. If both of the methods use the same time, then output the word "$Both$" (without " "). The next line should be the minimum number of blocks which need to be moved. ###Constraints: - $1\leq N \leq100000$ - $1\leq a[i] \leq10^9$ ###Sample Input: 7 10 163 89 5 73 15 49 ###Sample Output: Sriram 3 ###Explanation: To obtain the arrangement 5 10 15 49 73 89 163 (ascending order from top to bottom) we need to move at least 4 blocks. First, from the initial arrangement, take 73 and insert it at the bottom. Take 89 and 163 and then do the same. Then insert 10 between 5 and 15. To obtain 163 89 73 49 15 10 5 (descending order from top to bottom) however we only need to move 3 blocks. We just have to insert 15, 10 and 5 at the bottom. Thus, Sriram's method (descending order from top to bottom) is faster.
|Tags||binary-search, bluishgreen, dynamic-programming, easy-medium, jp2018|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions