Если вы такой же идиот в геометрии, как и я, то сделайте 2 вложенных тернарных поиска по углам и все пройдет :).  Удачи

Some authors solved this problem with very good time and very small memory. But if we store input data without compressing it is necessary near 1Mb. Maybe there exist solution without storing input at all?
Who can help me to understand how it is possible?

Wa3 - answer is 0.00. there you should check the longest block ;)

I counted radius with precision 1e-10, upper bound is 1e6.
P.s. dont forget cases there center of circle is outside(like sample)

Statement lies: there are test cases when crosses needs two moves to win.

That pisses me off, because it's always a great challange to understand the right meaning of a statement, but this one just doesn't give you a chance to do that.

please give me some tests.All test that I found in other topic my programm pass.

I can't find mistake, help!!


#include <iostream>
#include <cmath>
using namespace std;
int main() {
    __int64 n,k;
    int s = 0;
    cin>>n>>k;
    int step;
    step = log(k)/log(2);
    if(n-pow(2,step+1)>=0) {
        n -= pow(2,step+1);
        s = (step+1)+ceil(n*1./k);
    } else {
        s = ceil(log(n)/log(2));
    }
    cout<<s;
}

just the rule of multiplication in combinatorics...

Formula:

ceil(log2(min(n, k))) + ceil((double)(n - (1 << (int)(ceil(log2(min(n, k))))))/ k)

Edited by author 29.07.2018 13:01

Edited by author 09.09.2018 17:50

This test helped me to get ac after wa16:
5
1 2
1 3
2 5
3 4

Edited by author 28.07.2018 15:42

sol.push_back(ceil((double)n/2))
(sol is vector in c++)
If you solved it using such code, please explain why it works.

Проверяйте пограничные ситуации, когда номер билета на входе 000000 или 999999

double check lazy calculations

Edited by author 25.10.2012 03:55

deleted

Edited by author 26.10.2021 22:50

I think my idea completely right What's wrong??????


import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        String s[][] = new String[n][3];
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                s[i][j] = in.next();
            }
        }
        boolean all[][] = new boolean[n][3];
        String ss[][] = new String[3*n][3*n];
        ss[0][0] = "Isenbaev";
        int []index = new int[3*n];
        for(int i=0;i<n;i++){
            index[i] = 0;
        }
        index[0] = 1;
        int d = 1;
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(s[i][j].equalsIgnoreCase("Isenbaev"))all[i][j] = true;
            }
        }
        boolean BOR = false;
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(s[i][j].equalsIgnoreCase("Isenbaev"))BOR = true;
            }
        }
        for(int q=0;q<3*n;q++){
            boolean bormi = false;
            for(int i=0;i<n;i++){
                boolean bor = false;
                for(int j=0;j<3;j++){
                    for(int t=0;t<index[d-1];t++){
                        if(ss[d-1][t].equalsIgnoreCase(s[i][j])){
                            bor = true;
                            break;
                        }
                    }if(bor)break;
                }
                if(bor){
                    for(int j=0;j<3;j++){
                        if(!all[i][j]){
                            ss[d][index[d]++] = s[i][j];
                            all[i][j]  = true;
                            bormi = true;
                            for(int g=0;g<n;g++){
                                for(int h=0;h<3;h++){
                                    if(s[g][h].equalsIgnoreCase(s[i][j]))all[g][h] = true;
                                }
                            }
                        }
                    }
                }
            }
            if(bormi)d++;
        }
        String []sss = new String[3*n];
        int []son = new int[3*n];
        for(int i=0;i<3*n;i++){
            son[i] = -1;
        }
        int koef = 0;
        for(int i=0;i<d;i++){
            if(i==0){
                if(BOR){
                    BOR = false;
                }else i++;
            }
            for(int j=0;j<index[i];j++){
                sss[koef] = ss[i][j];
                son[koef++] = i;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(!all[i][j]){
                    boolean top = true;
                    for(int p=0;p<koef;p++){
                        if(sss[p].equalsIgnoreCase(ss[i][j]))top = false;
                    }
                    if(top)sss[koef++] = s[i][j];
                }
            }
        }


        n = koef;
        for(int i=0;i<n-1;i++){
            if(sss[i].compareTo(sss[i+1])>0){
                String S = sss[i];
                sss[i] = sss[i+1];
                sss[i+1] = S;
                int SS = son[i];
                son[i] = son[i+1];
                son[i+1] = SS;
                i=-1;
            }
        }

        for(int i=0;i<koef;i++){
            if(son[i]!=-1)System.out.println(sss[i] + " " + son[i]);
            else System.out.println(sss[i] + " undefined" );
        }
    }
}

Edited by author 25.07.2018 00:30

Edited by author 27.07.2018 23:09

You can make this problem even harder by setting TL to 1s. My current solution runs in 0.96s and there are two optimizations that aren't too hard to come up with that can speed up program significantly (probably sub 0.1s).

Firstly, for any complete graph on N vertices the answer is 2^N.
Secondly, if you program has TL issues look up 3-regular graphs, they are the worst case of my algorithm.

My solution uses no random, there is a nice deterministic solution, i.e. no hashes or shuffling.

The following tests should be enough to get rid of all WAs

Tests:

3
001
000
100

Answer: 5

6
000001
001001
010000
000001
000000
110100

Answer: 11

6
010010
101010
010100
001011
110100
000100

Answer: 15

4
0011
0000
1001
1010

Answer: 9

4
0110
1011
1101
0110

Answer: 12

4
0001
0000
0000
1000

Answer: 6

10
0001111111
0011111111
0101111111
1110111101
1111011110
1111100111
1111100111
1111111000
1110111001
1111011010

Answer: 195

7
0111101
1011110
1100111
1100111
1111000
0111001
1011010

Answer: 39

Edited by author 24.07.2018 19:09

> I use the segment tree,but I can't find anything wrong...
> Could you please give me some tests so that I can find out my program's problem?
> Thank you.

But now I got WA #5,and I have considered the following tests:
6
+ 9
- 3
- 3
+ 3
+ 3
+ 3
And I think the answer is:
9
9
9
9
9
3
But I still WA #5,Could someone can give me some hints or some tests?

Edited by author 20.06.2013 10:52

Edited by author 20.06.2013 10:52

#include <iostream>

using namespace std;

int main(){
    int n(0),m(0),last(0),temp_f(0),temp_s(0),end_(0);
    cin >> n >> m;
    for(int i = 0;i<n;++i){
        cin >> temp_f >> temp_s;
        last += temp_f-2-temp_s;
    }
    end_ = last + (m - 2);
    if(end_ < 0)cout << "Big Bang!";
    else cout << end_;

    return 0;
}

can I import the numpy library

type
a = array[1..50000] of integer;
b = array[1..50000] of integer;


  Var c,d,i,k,g: integer;
  Var n: a; Var p: b;

  begin
  d:= 0;
  read(c);
  for i:= 1 to c do read(n[i]);
  read(k);
  for i:= 1 to k do read(p[i]);

  for i:=1 to c do
  for g:=1 to k do
  begin
  if (n[i] + p[g] = 10000) then
  begin
  writeln('YES');
  exit;
  end
  else if (i = c) and (g = k) and (n[i] + p[g] <> 10000) then
  begin
  writeln('NO');
  exit;
  end;
  end;
  end.