#include<iostream>
#include<cmath>
using namespace std;

int func(int k, int n, int m)
{
    if(n == 0)
        return 1;
    else
        return func(k, n-1, m)*k%m;
}

int main()
{
    int n, m, y, x, i = 0;
    int b;
    bool flag = true;
    cin >> n >> m >> y;
    if((n >0 && n < 999) && (m > 1 && m < 999)  && (0 < y && < 999))
    {
    while(i < m)
    {
        x = func(n, i, m);
        if(x == y)
        {
                cout << i << ' ';
                flag = false;
        }
        i++;
    }
    if(flag)
        cout << "-1";
}
else
cout << "-1";

    return 0;
}

Edited by author 08.02.2018 02:25

Edited by author 08.02.2018 02:27

Firstly, the problem asks to find number of edges in minimum edge cover
Secondly, the number of such edges plus the number of maximum matching equals to number of vertices, that is N + M
Thirdly, you can find the number of max. matching easily with dfs-like algorithm (you can find code online).

The answer is N + M - (number of max. matching)

I get TLE on 21 test. What can you advise?

i think 212 in the Example test is wrong cause we have 2 remix of "I miss you" when the most remix that we can reach is 1 .

Edited by author 21.01.2018 23:56

in:
9
+ 10
+ 10
+ 10
- 10
- 10
+ 5
- 10
- 5
+ 123
out:
10
10
10
10
10
5
5
1
123
GL. Sqrt decomposition works fine in this problem.

N = int(input())

if N == 1:
    print(1,1)
    exit()

for P in range(round(N**0.5)+1,0,-1):
    A = (2*N - P**2 + P) / (2*P)
    if A % 1 == 0:
        print(int(A),P)
        exit()

This problem isn't hard! Just use Burnside's lemma.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication25
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine()), Sum=0;
            if (Math.Abs(N)<10000)
            {
                while (N != 1)
                {
                    if (N > 1)
                    {

                        Sum = Sum + N;
                        N--;


                    }
                    else
                    {
                        Sum = Sum + N;
                        N++;


                    }
                }
            }
            Console.WriteLine(Sum+1);
        }
    }
}

I've got Runtime error in Test 2. I've written the code in Java. Could anybody share the test case for the Test2?

My solution pass's all tests presented here in the forum.
But i get WA at 36 test, authors please help what's there????

<code>
#include <iostream>
using namespace std;

int main()
{
    __int64 n, i, a, b, c, maxC1 = 1, maxC2 = 1, maxC = 1;
    cin >> n;
    for (i = 1; i*i < 1000000; i += 2)
    {
        if (n % i == 0)
        {
            a = n/i;
            b = sqrtl((long double)a);
            c = sqrtl((long double)i);

            if (b*b == a && a > maxC1) {
                maxC1 = a;
            }

            if (c*c == i && i > maxC2) {
                maxC2 = i;
            }

            maxC = max(maxC1, maxC2);
        }
    }

    cout << maxC;
    return 0;
}
</code>
Do I need to write own sqrt ? What the problem is ?



Edited by author 22.01.2015 17:54

#include <iostream>
using namespace std;

const int kmax=105;

int K[kmax];
int L,n;

int R(int x, int y)
{
   if(x%y==0) return x/y;
   else return x/y+1;
}

int main()
{
   cin>>L>>n;
   for(int i=1;i<=n;i++) cin>>K[i];

   if(n==1)
   {
      if(L<K[1]) cout<<"YES";
      else cout<<"NO";
      return 0;
   }

   int t1=R(L, K[1])*K[1], t2=K[1];
   if(t1==t2) t1+=K[1];

   for(int i=2;i<=n;i++)
   {
      t2+=K[i];
      if(t1<t2)
      {
         cout<<"YES";
         return 0;
      }
      t1=t2+R(t1-t2,K[i])*K[i];
      if(t1==t2) t1+=K[i];
   }

   cout<<"NO";

   return 0;
}


and


#include <iostream>
using namespace std;

const int kmax=105;

int K[kmax];
int L,n;

int main()
{
   cin>>L>>n;
   for(int i=1;i<=n;i++) cin>>K[i];

   if(n==1)
   {
      if(L<K[1]) cout<<"YES";
      else cout<<"NO";
      return 0;
   }

   int t1=(L/K[1]+1)*K[1], t2=K[1];

   for(int i=2;i<=n;i++)
   {
      t2+=K[i];
      if(t1<t2)
      {
         cout<<"YES";
         return 0;
      }
      t1=t2+(1+(t1-t2)/K[i])*K[i];
   }

   cout<<"NO";

   return 0;
}

?????????????????????????????????????????????

https://oeis.org/A281795

Edited by author 29.01.2018 22:10

#include <bits/stdc++.h>
using namespace std;
int main(){
int n, sana,s;
char k[21];
cin>>n;
cin.getline(k,sizeof(k));
sana = strlen(k)-1;

if (1<=n&&n<=10&&1<=sana&&sana<=20){

if(n%sana==0) { s=sana;}
else          { s=1;}
while(n>0){
    s*=n;
    n=n-sana;}
cout << s << endl;
}
}

Edited by author 28.01.2018 23:09

divide three euler angle into 50 pieces  each of them is 2*pi/50;enum each euler angles and
compute minmimum max different of distance to three faces.

for(alpha=0;alpha<=2*pi;alpha+=dtheta)
{
     if(min_dist>compute(alpha))
     {
          min_dist=compute(alpha);
          ch=alpha;
     }
}
low=ch-dtheta;
high=ch+dtheta;
then ternary search [low,high]..
Do you understand?

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;
  var  a:array [0..110,0..110] of integer;
  d:array [0..2000] of string;
  k:array[0..2000,1..2] of integer;
  x1,y1,x,y,i,sc,l,j,n,f,b1,c1:integer;
  puk:string;

  procedure ar (b,c,m:integer);
  var res:string;
  begin
  res:='';
  k[m,1]:=b; k[m,2]:=c;
   if a[b+1,c]=1 then begin a[b+1,c]:=0; res:=res+'R' end;
   if a[b,c+1]=1 then begin a[b,c+1]:=0; res:=res+'T' end;
   if a[b-1,c]=1 then begin a[b-1,c]:=0; res:=res+'L' end;
   if a[b,c-1]=1 then begin a[b,c-1]:=0; res:=res+'B' end;
  d[m]:=res;
  end;

begin
  readln (n);
  for i:= 0 to 11 do
  for j:= 0 to 11 do
   a[i,j]:=0;
   read (x1); readln (y1);
   a[x1,y1]:=0;
   writeln (x1,' ',y1);
  for i:= 2 to n do begin
  read (x);
  readln (y);
  a[x,y]:=1;
  end;
  f:=1;
  sc:=1;
  ar(x1,y1,f);
  repeat
  b1:=k[sc,1];c1:=k[sc,2];
  puk:=d[sc];
    l:=length(puk);
    if l>0 then
    for i:= 1 to l do begin
     case puk[i] of
     'R': begin f:=f+1; ar(b1+1,c1,f); end;
     'T': begin f:=f+1; ar(b1,c1+1,f); end;
     'L': begin f:=f+1; ar(b1-1,c1,f); end;
     'B': begin f:=f+1; ar(b1,c1-1,f); end;
     end;
    end;
    inc(sc)
  until sc=n;

  if f>1 then for i:= 1 to f-1 do writeln (d[i],',');
  writeln (d[f],'.')
end.

Program work ideally on my computer.

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