Just think of an increasing sequence. The program caculates n+1 times for an increasing sequence with n elements. And then divide it into two subsequences. One is the leftmost element, and anthoer is the left elements. It ends at the length of sequence is 2. Thus, the sum is (n+1) + n + (n-1) + ... + 3 = (n+4)(n-1)/2 = (n*n + 3*n - 4)/2. So output 1 to n is ok.

?

 Everybody who knows quick sort will recognize that the tsar's program is quick sort of N numbers. Let we have a sorted array with n numbers. Let l-r+1=k. Then function P() will increase the value of c by k+1 because it will visit all x elements to distribute them into part smaller than or equal to x and part greater or equal to x. That increases c by k. But the i and j iterators must be equal so there is also one additional increase of c. Because we have a sorted array function P() will partition him into part consisting of 1 element and part consisting of l-r elements. The part consisting of 1 element will be ignored and there won't be any increase of c. In the part with l-r elements it will do the same - partitioned it into 1 and l-r-1. So let begin with l-r+1=N. Then the function Q() will go to l-r+1=N-1 and so on to l-r+1=2. For those calls of function Q() c will be increased with:
N+1 + N + N-1 + ... + 5 + 4 + 3 = (N+1)*(N+1+1)/2 - 1 - 2 = N*N + 3*N + 2/2 - 3 =
=N*N + 3*N + 2 - 3*2/2 = N*N + 3*N - 4 / 2.
So if we give a sorted array to the tsar's program it will print what we want. What is more, we prove that for sorted array quick sort is very bad algorithm with such bad complexity.

Note: If the median element was chosen in a different way the solution won't be so easy. But it can be done if we try all permutations of array with elements from [1;n] and check for c.

Edited by author 21.08.2013 22:19

There is one typo in both codes: Beautiful, not Beutiful.

s

let sequence be 1,2,3,...,n

I.    in each P( l, r ) there will be 1 + r-l+1 times ++ c.

II.   in each Q( l, n ) = Q( l, l ) there will be 0 time ++ c.

III.  in each Q( n, r ) = Q( n+1, r ) + P( n, r ).

IV.   Let F( n ) is the total times of ++ c, so we get F( n ) = F( n-1 ) + n + 1 and F( 1 ) = Q( r, r ) = 0;

the sum of ++ c is 3 + 4 +... + n+1 = n*(n-1)/2 + 2*(n-1) = (n-1)*(n+4)/2 = (n*n+3*n-4)/2

Edited by author 24.05.2011 11:12

Edited by author 24.05.2011 11:13

its quick sort function ! just write a program to print from 1 to n !!!! =))

I looked at program version on C, and found interesting strings:
int main(void)
 {
  c=0;
  for(long i=0; i<N; ++i)
   scanf("%ld", &A[i]);
 ....
This code can' be compile on C. Because variable “i” can be declared in operator “for”(according to C standard)!!!!Check it!

when do you have a online contest?

Write numbers from 1 to n, that's enough! You should be
accepted.