Edited by author 23.08.2015 14:38

18 32
5 11
9 2
17 16
16 7
2 12
13 2
16 4
5 17
4 13
14 17
17 17
11 3
11 15
9 3
13 10
3 8
16 13
7 16
10 11
11 13
14 8
7 4
16 10
1 11
15 2
2 12
13 12
1 14
3 14
8 6
14 1
18 1

ans:65

If you use newton's method to find a square root make sure that your division algorithm for 2 big integers is fast enough to handle quickly a lot of divisions that requires newtons method, otherwise you will get TL ... even with O(n*log(BASE)) time complexity division algorithm your going to get TL.
Faster division at O(n) is described in Knuth's The Art of Computer Sience 2 edition, page 298 or 299...

So in case if yo get TL with newton's method (which has got actually better time complexity than binary search root finding) just use binary search algo for root with BASE = 10^9 for you big integers, it needs only division by 2, *, +, and - operations needed for big integer.
If input contains 600 digits you will only need 600 / 9 array elements to store that number ... and with less divisions you will get AC!

take care ...

Edited by author 09.07.2015 18:17

Found the mistake :)

Edited by author 09.07.2015 01:22

I solved the problem by using a topological sorting.The vertices are segments.The arcs of the graph characterize nesting

4
0 1
-1 4
-2 10
-3 3

Edited by author 07.05.2009 17:46

program ideone;
const TH : integer = 200000; //you can set it less or greater to speed up
INF : Cardinal = 2147483647+2;

var in1, reg, i,j,inx,i1,i2, shift, max, greater:Cardinal;
    n:Cardinal;
    var a :array of Cardinal;

    procedure QSort ( first, last: Cardinal);
   var L, R, c, X: Cardinal;
   begin
      if first < last then
      begin
         X:= a[(first + last) div 2];
         L:= first;
         R:= last;
            while L <= R do
            begin
               while a[L] < X do
                  L:= L + 1;
               while a[R] > X do
                  R:= R - 1;
               if L <= R then
               begin
                  c:= a[L];
                  a[L]:= a[R];
                  a[R]:= c;
                  L:= L + 1;
                  R:= R - 1;
               end;
           end;
        QSort(first, R);
        QSort(L, last);
     end;
end;

begin
    Read(n);

    if (n=1) then
    begin
        Readln(in1);
        writeln(in1);
        halt;
    end;
    shift :=0;
    max := 0;
    if (n>TH) then
    begin
        shift := n-TH;
        n := TH;
    end;
    setLength(a, n+1);

    for i:=1 to n do
    begin
        Read(in1);
        a[i] := in1;
    end;

    Qsort(1,n);
    max := a[n];

    for i:=1 to shift do
    begin
        Read(in1);
        if (in1>max) then
        begin
            a[i] := INF;
            greater := greater + 1;
        end else
        a[i] := in1;
    end;
    Qsort(1,n);

    n := n+shift;
    if (n mod 2=1) then
    begin
        writeln(a[n div 2+1 - shift]);
    end else
    begin
        inx := a[n div 2- (shift)] mod 2;
        inx := inx + a[n div 2 +1- (shift)] mod 2;
        write(a[n div 2- (shift)] div 2  + (a[n div 2 +1 - (shift)] div 2));
        if (inx=1) then
        begin
            write('.5');
        end;
    end;

end.

Я получил АС! Сложность O(N+M)=O(2N). Стандартный обход в глубину, но несколько изменённый. Важно что-то заметить про висячие вершинки.

Edited by author 07.07.2015 00:02

Edited by author 07.07.2015 00:02

Edited by author 07.07.2015 00:02

hi,
in the acceptable answer the answer of 5 4 is 7 but you can easily understand that the real answer is 6(you can test it by drawing a simple 5 4 table).

here is a sample answer:

#include <iostream>

using namespace std;

int main() {
    int unsigned long long N , M , turn = 0;
 cin >> N >> M;



 while( N > 2 && M > 2){
     turn += 4;
     N -= 2;
     M -= 2;
 }
 if (N == 2 && M > 1 || M == 2 && N > 1)  turn += 2;

 if (M == 1 && N > 1) turn += 1;
  cout << turn << endl;

  system ("PAUSE");
  return 0 ;

}

using System;
class Program{
    static void Main(){
        string[] input = Console.ReadLine().Split(new char[]{' ', '\t', '\n'}, StringSplitOptions.RemoveEmptyEntries);
        string Result = "";
        double temp;
        for (int i = 1; i <= Int32.Parse(input[0]); i++){
        temp = Math.Sqrt(((Int32.Parse(input[i]) - 1) * 8) + 1);
            temp = (temp - 1) / 2;
            if (temp % 1 == 0)
                Result += "1 ";
            else
                Result += "0 ";
        }
        Console.WriteLine(Result);
    }
}

Edited by author 04.07.2015 10:47

Can you give me some TEST  i have WA 30. Thank you

#include<stdio.h>
#include<deque>
#include<algorithm>
using namespace std;
class node{
    public:
    int x,y,num;
}dum;
bool func(node i,node j)
{
    if(i.y > j.y)
    return true;
    return false;
}
int main()
{
    deque<node> city;
    int n;    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&dum.x,&dum.y);
        dum.num = (i+1);
        city.push_back(dum);
    }
    if(n == 0)
    {printf("0");return 0;}
    sort(city.begin(),city.end(),func);
    for(int i=0;i<n;i+=2)
    {
        printf("%d %d\n",city[i].num,city[i+1].num);
    }
}

Simple Descending sort

#include <stdio.h>
#include<math.h>
 int main(){
     int a=1;
     while ( a!= 0){


     scanf("%d",&a);
        if (a>=1)
        if (a<=4)
        printf("few\n");
        if (a>=5)
        if (a<=9)
        printf("several\n");
        if (a>=10)
        if (a<=19)
        printf("pack\n");
        if (a>=20)
        if (a<=49)
        printf("lots\n");
        if (a>=50)
        if (a<=99)
        printf("horde\n");
        if (a>=100)
        if (a<=249)
        printf("throng\n");
        if (a>=250)
        if (a<=499)
        printf("swarm\n");
        if (a>=500)
        if (a<=999)
        printf("zounds\n");
        if (a>=1000)
        printf("legion\n");
}

     return 0;
 }

Edited by author 02.07.2015 03:53

Or should we have our program do all calculations?

Try this
+1.111e+3
5

I got TL although i'm using the binary tree , and when I looked for a solution on the net i found the same of mine but in another words
here is my code:

#include <cstdio>
#include <cstring>

using namespace std;
#define max 32002
int a[max];
void update(int i,int n,int v)
{
    while(i<=n)
    {
        a[i]+=v;
        i+=i&(-i);
    }

}
int read(int i)
{
    int v=0;
    while(i>0)
    {
        v+=a[i];
        i-=i&(-i);
    }
    return v;

}

int main()
{
    int n;
    scanf("%d",&n);

    int b[15010];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);


        b[read(x)]++;
        update(x,32002,1);
    }
    for(int i=0;i<n;i++)
        printf("%d \n",b[i]);
    return 0;
}

so please help me cause i'm about to lose my mind!!!

0 0
5 0
6 1
1 1

Answer: 0

Sandro't have anywhere to teleport him to stay in the point (0;0). Simply calculate the distance of most distant demon!