UVa 11495

Jump to navigation Jump to search

Summary

This is the standard problem of counting the number of inversions in a string of length ${\displaystyle n\leq 100000}$. In a sequence ${\displaystyle A}$, the pair ${\displaystyle (i,j)}$ is an inversion of ${\displaystyle A}$ if ${\displaystyle i and ${\displaystyle A_{i}>A_{j}}$.

Explanation

Given the big string length, a brute-force ${\displaystyle O(n^{2})}$ solution won't pass. Check UVa 10810 and UVa 10327 for possible solutions. First player wins if the number of inversions is odd, while the second does so if the number is even.

Gotchas

As explained in UVa 10810, worst case number of inversions possible = ${\displaystyle {\frac {n(n-1)}{2}}}$. Given the big size of ${\displaystyle n}$, a 32-bit integer holding the inversions count won't suffice.

Notes

How can we exploit the fact of having the string alphabet known beforehand?

Input

5 1 5 3 4 2
5 5 1 3 4 2
5 1 2 3 4 5
6 3 5 2 1 4 6
5 5 4 3 2 1
6 6 5 4 3 2 1
0


Output

Marcelo
Carlos
Carlos
Carlos
Carlos
Marcelo