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

please give me some tests

It works on my laptop! I have Pascal ABC.

var a,b,c:integer;
begin
readln(a,b);
if a>b then c:=ceil(2*a/b) else c:=2;
write(c);
end.

Edited by author 08.09.2011 17:57

广东话不好学咩？

what's wrong in my code:
#include <stdio.h>

main()
{
      int a;
      scanf("%d",&a);
      if( a >= 0 )
          printf("%d",a*(a+1)/2);
      else
      {
          a = -a;
          printf("-%d",a*(a+1)/2-1);
      }
      return 0;
}

Edited by author 25.08.2012 15:05

Edited by author 25.08.2012 15:06

some trick?

I had a stupid mistake
Instead of:
shop[want] -= q[r].amount;
I had:
shop[want] = q[r].amount;

New tests were added, and time limit was decreased to 0.5 sec. 183 authors lost AC after rejudge.

I think that second test contains line which begins with 0. This case is not allowed because in problem statement is written that (1 ≤ N ≤ 14999). Please check if I'm right.

In one of my solution I checked (using assert from cassert) if N is greater than 0 and I received WA2. When I removed assert I've received AC.

10 3 3 1
1 3
1 3
1 3

My solution way getting TLE - on test 32 - while my complexity was O(n ^ 2) I think;
but by changing some parameters - coordinates for example - from int to short int, (a 4 byte variable to a 2 byte one) got AC in .3 s.
I thought may help you!
Good luck :)

Определение:
n!!…! = n(n−k)(n−2k), где k - количество знаков "!".
При расчете на любом этапе не должно получатся отрицательного числа.

И все.
Я только с таким условием получил "Accepted".

Where do I have a problem?

I used binary search and got time limit on test 2. But when I use N*N1 speed I pass test 2 and get time limit on test 10.

Can you please check my code. I believe it is correct.


#include <iostream>

using namespace std;

bool binary_search (long* b , long a , long from ,long to)
{
    while (from != to)
    {
        long mid = (from + to )/2;
        if (b[mid] + a == 10000) return true;
        if (b[mid] + a > 10000)
        {
            from = mid;
        }
        if (b[mid] + a < 10000)
        {
            to = mid;
        }
    }
    return false;
}
int main ()
{
    long n , n1;
    long* a , *b;
    cin >> n;
    a = new long[n];
    for (int i =0 ; i < n ; i++)
    {
        cin >> a[i];
    }
    cin >> n1;
    b = new long[n1];
    for (int i =0 ; i < n1 ; i++ )
    {
        cin >> b[i];
    }
    bool tr = false;
    for (int i = 0 ; i < n ; i++)
    {
        tr = binary_search (b , a[i] , 0 , n1);
        if (tr) break;
    }
    if(tr) cout << "YES";
    else cout << "NO";
}

I do not see error here, but didn't pass the 17'th test
var p,q: extended;
    a,b: longint;
BEGIN
    read(p,q); p:=p/100; q:=q/100;
    a:=1;
    while (true) do begin
       b:=1;
     while (a/b>=q) do inc(b);
     if (a/b>p) then begin
          write(b);
          halt(0);
       end else inc(a);
    end;
END.

 I read some previous topics because my soluton was getting WA1. I tried this test which was Leo's test with some empty lines:

4



0 00 0


0 11

10 1 1


11 011

And then I fixed my program.

Edited by author 15.08.2013 16:58

Edited by author 15.08.2013 16:59

Why it is so slowly??? I use standard formula with "sqrt(8*N-7)".

            int L = int.Parse(Console.ReadLine());
            string answer = "";
            for (int i = 0; i < L; i++)
            {
                if (Math.Sqrt(8 * long.Parse(Console.ReadLine()) - 7) % 1 == 0) answer += "1 ";
                else answer += "0 ";
            }
            Console.Write(answer);

I can't imagine shortest solution... What's the matter?
Many people has used C# successful in problem 1209.

Edited by author 28.11.2011 03:09

Thanks for it!