If you are getting WA#1, try this.

Input:
8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3

Output:
1 1
RT,
R,
T,
T,
R,
T,
,
.

Всем привет! Долго пытаюсь решить задачу, не вижу никаких логических ошибок(плохо знаком с JAVA и,может быть, ошибка в реализации). Тот, кто решил, подскажите, в чём проблема.

Решаю так: беру n-ю точку, произвожу инверсию относительно n-й точки (R=1). Затем ищу прямую, делящую плоскость на 2 части, чтобы в каждой части было ровно  (N-3)/2 точек (кроме n-й и 2х выбранных для прямой). Выбранные 3 точки и есть ответ.
Ищу прямую так (среди конечных точек): найдём самую нижнюю точку, сделаем её n-1 -й; она войдёт в ответ; перенесём СК в эту точку; затем отсортируем относительно неё (точки) оставшиеся точки и выберем из них среднюю.
Почему алгоритм корректен? После инверсии имеем n-1 конечные точки и 1 бесконечную. Заметим, что нет прямой, проходящей через 3 конечные точки (если такая есть, то возможны 2 варианта: 1)прямая проходит через О - тогда при обратной инверсии она проходит через О и при этом содержит 4 точки; 2)прямая не проходит через О - тогда при обратной инверсии она перейдёт в окружность, проходящую через О, тогда эти 3 точки и бесконечная точка лежат на одной окружности). А тогда можно найти прямую, разделяющую плоскость на 2 части, в каждой из которых содержится равное число конечных точек. Одна часть полуплоскости перейдёт во внутреннюю часть окружности, другая - во внешнюю.


import java.math.*;
import java.util.*;

public class BigNumbers
{
   final int nmax=5005;

   public static BigInteger Px[], Py[], z[];
   public static int n;

   public static boolean Equal(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)
   {
      BigInteger A = (x1.multiply(z2)).subtract(x2.multiply(z1));
      BigInteger B = (y1.multiply(z2)).subtract(y2.multiply(z1));
      return (A.compareTo(BigInteger.ZERO)==0 && B.compareTo(BigInteger.ZERO)==0);
   }

   public static boolean Less(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)   //полярный угол строго меньше
   {
         if(Equal(x1,y1,z1,x2,y2,z2)) return false;

         if(y1.compareTo(BigInteger.ZERO)==0) return x1.compareTo(BigInteger.ZERO)==1;
         else
         {
            if(x1.compareTo(BigInteger.ZERO)==1)
            {
               if(x2.compareTo(BigInteger.ZERO)!=1) return true;
               BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1));
               return v.compareTo(BigInteger.ZERO)==1;
            }
            else
            {
               if(x1.compareTo(BigInteger.ZERO)==0) return x2.compareTo(BigInteger.ZERO)==-1;
               else
               {
                  BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1));
                  return (x2.compareTo(BigInteger.ZERO)==-1 && v.compareTo(BigInteger.ZERO)==1);
               }
            }
         }
   }

   public static boolean More(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)  //полярный угол строго больше
   {
         return Less(x2,y2,z2,x1,y1,z1);
   }

   public static void QSort(int L, int R)
   {
      int m=(L+R)/2;
      int i=L;
      int j=R;

      while(i<=j)
      {
         BigInteger xi,yi,zi,xj,yj,zj,xm,ym,zm;

         xm=(Px[m].multiply(z[n-1])).subtract(z[m].multiply(Px[n-1]));  //здесь перемещаем СК относительно n-1 - й точки
         ym=(Py[m].multiply(z[n-1])).subtract(z[m].multiply(Py[n-1]));
         zm=z[m].multiply(z[n-1]);

         xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1]));
         yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1]));
         zi=z[i].multiply(z[n-1]);

         while(Less(xi,yi,zi,xm,ym,zm))
         {
            i++;
            if(i<=n)
            {
               xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1]));
               yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1]));
               zi=z[i].multiply(z[n-1]);
            }
         }

         xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1]));
         yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1]));
         zj=z[j].multiply(z[n-1]);
         while(More(xj,yj,zj,xm,ym,zm))
         {
            j--;
            if(j>=1)
            {
               xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1]));
               yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1]));
               zj=z[j].multiply(z[n-1]);
            }
         }

         if(i<=j)
         {
            BigInteger v;
            v=Px[i]; Px[i]=Px[j]; Px[j]=v;
            v=Py[i]; Py[i]=Py[j]; Py[j]=v;
            v=z[i]; z[i]=z[j]; z[j]=v;
            i++;
            j--;
         }
      }
      if(L<j) QSort(L, j);
      if(i<R) QSort(i, R);
   }


   public static void main(String args[])
   {
      Scanner sc=new Scanner(System.in);

      n=sc.nextInt();

      Px=new BigInteger[n+1];
      Py=new BigInteger[n+1];
      z=new BigInteger[n+1];

      for(int i=1;i<=n;i++)
      {
         Long x, y;
         x=sc.nextLong();
         y=sc.nextLong();
         Px[i]=BigInteger.valueOf(x);
         Py[i]=BigInteger.valueOf(y);
      }

      for(int i=1;i<=n-1;i++)        //относительно n-й точки производим инверсию
      {
         Px[i]=Px[i].subtract(Px[n]);
         Py[i]=Py[i].subtract(Py[n]);
         z[i]=(Px[i].multiply(Px[i])).add(Py[i].multiply(Py[i])); //теперь все координаты(кроме n точки) имеют вид ((xi-xn)/zi, (yi-yn)/zi)
      }

      for(int i=1;i<=n-2;i++)   //ищем самую нижнюю точку-она должна стать n-1 - й
      {
         BigInteger v1=z[n-1].multiply(Py[i]);
         BigInteger v2=z[i].multiply(Py[n-1]);
         if(v1.compareTo(v2)==-1)
         {
            BigInteger v;
            v=Px[i]; Px[i]=Px[n-1]; Px[n-1]=v;
            v=Py[i]; Py[i]=Py[n-1]; Py[n-1]=v;
            v=z[i]; z[i]=z[n-1]; z[n-1]=v;
         }
      }

      QSort(1,n-2);//сортируем по полярному углу от 0 до Pi

      Px[n-1]=Px[n-1].add(Px[n]);   //получаем начальные коорд.
      Py[n-1]=Py[n-1].add(Py[n]);

      int m = (n-1)/2;
      Px[m]=Px[m].add(Px[n]);
      Py[m]=Py[m].add(Py[n]);

      System.out.println(Px[n-1]+" "+Py[n-1]);
      System.out.println(Px[m]+" "+Py[m]);
      System.out.print(Px[n]+" "+Py[n]);
   }
}

Edited by author 27.01.2018 13:53

2
1000000000000000000
4561565

Answer: 3736220


1000000000000000000
1000000000000000000
1000000000000000000

Answer: 999999999999999999


1000000000000000000
2
1000000000000000000

Answer: 207504272460937501


101654687486400
2
10054654646101

Answer: 6318728278733


5000
4000
3000

Answer: 0

Some one give me some kind of this test pls thanks.

There were rumors that it is hard to get AC with hashes.
Got AC in 0.031 using standard N log^2 N suffix array. Hashes modulo 2^64 (so there is no explicit divisions in code).
There are couple of tricks, but they all are very easy to code.

1) gethash(i + l, i + mid) == gethash(j + l, j + mid)
&& memcmp(s + i + l, s + j + l, mid - l) == 0
instead of just
gethash(i, i + mid) == gethash(j, j + mid)
in binary search (lcp computing)

2) std::::stable_sort is preferable over std::sort when comparisons are heavy. std::stable_sort makes more assignments in average, but much less comparisons.

0.031 sec, 62 lines of code (including 10 empty, "return 0", 4 includes and so on).

как стать богатым в беларуси?
если у нас ничего нету

Text says "Pierre intends to use one-digit integers supplemented with a leading zero and two-digit integers only." but it seems like you cannot have one digit numbers in the original sequence.

For example, for test case 2, if you output "10 00" (which would translate to sequence 01 00, which ARE two consecutive numbers), you'll get wrong answer. Moral of the story, start checking for numbers from 10.

I have WA#1, but my program is correct.
Give me some tests And answer for this tests:
Input  1 : 120
My answer : 15

Input  2 : 1081
My answer : 46

Input  3 : 1073845
My answer : 1465

Input  4 : 500500
My answer : 1000

Input  5 : 11325
My answer : 150

Input  6 : 17391
My answer : 186

Input  7 : 122750946
My answer : 15668


Input  8 : 906531
My answer : 1346

Input  9 : 154290
My answer : 555

Input  10 : 7620753696
My answer : 123456

Thanks Advanced !!!!

вообще не могу понять что не так. проходят пробные тесты,проходят тесты которые нашла в обсуждениях.
если не трудно может покидаете тесты, плииз...

var a,a1,a2,s1,s,ap,al,sm1p,sm2p,sm3p,smap,sm1l,sm2l,sm3l,smal,s2,s3:Integer;
begin
ReadLn(a);
a1:=a+1;
a2:=a-1;

ap:=a1 div 1000;
al:=a1 mod 1000;

sm1p:=ap div 100;
sm2p:=ap mod 100 div 10;
sm3p:=ap mod 10;
smap:=sm1p+sm2p+sm3p;

sm1l:=al div 100;
sm2l:=al mod 100 div 10;
sm3l:=al mod 10;
smal:=sm1l+sm2l+sm3l;

if smal=smap then Writeln('YES')
     else
     begin
     ap:=a2 div 1000;
     al:=a2 mod 1000;

     sm1p:=ap div 100;
     sm2p:=ap mod 100 div 10;
     sm3p:=ap mod 10;
     smap:=sm1p+sm2p+sm3p;

     sm1l:=al div 100;
     sm2l:=al mod 100 div 10;
     sm3l:=al mod 10;
     smal:=sm1l+sm2l+sm3l;
     if smal=smap then Writeln('YES')
             else
                  WriteLn('NO');
     end;
end.

Hello guys,

those, who have wa on 7'th case may try to change output precision to some big number. As for me, it worked on 15 signs.

I have no idea why this happens ^,^

If ever dear admins may be interested in case, please compare:
id 4772942 has wa7
id 4772947 has ok (line 167).

Best regards, mq.

Passed all the test given in the discussion
I ran 1 bfs from 'r' and another bfs from 's' where i also kept data for those nodes who can have multiple parents.
than I while restoring path from destination to source I selected the node who has higher level from 'r' (that selection occurs if only the node has possibility multiple parents)
returned the ans which is the minimum among the final path

I got AC with 0.015s,216Kb
I had read the problem several time until understand.
N is the length of the digit number.
It will be something like that
a1 a2 a3 ...an
for each ai in a1 a2 a3..an, 0 <= ai < K.
The output number i used was interger (compiler C++ 2010). (no big number).

hope it can help you.
And sorry for my poor English.

Edited by author 25.04.2014 23:05

https://ideone.com/Ocpa4V

I can't figure out what's wrong with my code. I used 'Queue' data structure.

Edited by author 23.01.2018 16:02

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;



vector<long long > C(20000,0);
void mult(vector<long long> A,vector<long long> B)
{
    int d=0;
    for(int i=0;i<300;i++)
    {
        for(int j=0;j<300;j++)
        {
            C[i+j]+=B[i]*A[j];
            C[i+j+1]=C[i+j+1]+C[i+j]/100000000;
            C[i+j]=C[i+j]%100000000;
        }
    }
    C[0]++;
    for(int i=0;i<6000;i++)
    {
        C[i+1]=C[i+1]+C[i]/100000000;
        C[i]=C[i]%100000000;
    }
}
vector<long long> D(20000,0);
void mult1(vector<long long> A,vector<long long> B)
{
    int d=0;
    for(int i=0;i<300;i++)
    {
        for(int j=0;j<300;j++)
        {
            D[i+j]+=B[i]*A[j];
            D[i+j+1]=D[i+j+1]+D[i+j]/100000000;
            D[i+j]=D[i+j]%100000000;
        }
    }
    for(int i=0;i<6000;i++)
    {
        D[i+1]=D[i+1]+D[i]/100000000;
        D[i]=D[i]%100000000;
    }
}
void write(vector<long long> A)
{
    bool f=false;
    for(int i=9999;i>=0;i--)
    {
        if(A[i]!=0)
            f=true;
        if(f)
            cout<<A[i];
    }
    cout<<"\n";
}
int main()
{
#ifdef _DEBUG
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
#endif
    int n;
    cin>>n;

    vector<long long> A(10000,0);
    vector<long long> B(10000,0);
    A[0]=1;
    B[0]=1;
    for(int i=0;i<n;i++)
    {
        mult(A,B);
        mult1(A,B);
        for(int i=0;i<4000;i++)
        {
            B[i]=D[i];
        }
        for(int i=0;i<4000;i++)
        {
            A[i]=C[i];
        }
        for(int i=0;i<4000;i++)
        {
            C[i]=0;
            D[i]=0;
        }
        write(A);
    }
}

Вот код, скорее всего он не пройдет макс тест, но при запуске на первом тесте он выдает мне в студии ответ правильный, а тут нет

I don't understand!!! How given (2, aa) answer is 6. I think that must be 4!!!  Please help, who know that!!!!! (Я не понел Как 2 и аа могут дать ответ 6 Я думаю что должно быть 4 Помогите------------)

I am getting WA 5   Can anyone provide me the test case 5..  or hint to test case 5..

var a,b,c,d,cen,k:integer;
begin
read(a,b,c,d);
while k<>1 do begin
if (a+b>c) then begin
k:=1;cen:=c;end
else a:=a+b;
if(c-d<a)then begin
k:=1;cen:=a;end
else c:=c-d;end;
writeln(cen);
end.

try to change your variables to double, and don't use int.

I think it's clear for the system of linear equations, that if M<N, than it's impossible. If M=N then it may be possible (and I know how to check). How about case M>N? We need to select N pairs that get an unambiguous solution?