111 Very Simple Problem

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

[=[miKroZ]=]

ну понятно, что количество цифр в ответе равно (k + 1) / 2.
будем их перебирать от старших, т. е. на старшее место ставим 9, возводим в квадрат, если получилось больше того, что на входе, то уменьшаем ее на 1, и т. д.

[=[miKroZ]=]

да k - количество цифр в исходном числе =)

ага и сколько это операций получается в худшем случае для 1000значного числа ? ((: т.е. вы предлагает перебрать все 500 значные числа.
у меня двоичный поиск в таком интервале не справляется.

[cmd]

он предлагает не все 500 значные числа

перебираем цифры от 9 до 0 умножаем на 10^текущего_разряда, смотрим больше меньше, как нашли цифру наибольшую при которой не больше квадрат получается чем данное число, то переходим к следующему разряду

получим k * 10 * действия_с_длинной_арифмет� �кой действий
а можно эту цифру искать бин поиском =) тогда k*log10 * BigInt

А вообще на этой задаче у меня бинпоиск прошел на яве

Я наверно опять не понял, все равно ведь получается медленнее чем бинарный поиск.

в худшем случае мы имеем при K == 500 ;
500* 10 * (длинная арифметика)
двоичный поиск же дает даёт результат
log(10^500-10^400) * (длинная арифметика)
легко показать что logx < 5000
т.к 2^5000 приблизительно равно 10^1500

написал извлечения корня в столбик.. сдал!
только так не интересно, хочу бинарным поиском сдать, буду оптимизирвать
(a+-2^n)^2

[=[miKroZ]=]

Моя реализация на Java

import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {
  public void run() throws Exception {
    Scanner in = new Scanner(new File("input.txt"));
    PrintWriter out = new PrintWriter(new File("output.txt"));
    
    String str = in.next();
    int n = str.length();
    
    if (n % 2 != 0) {
      str = "0" + str;
      ++n;
    }
    
    int k = n >> 1;
    BigInteger num = BigInteger.ZERO;
    BigInteger ans = BigInteger.ZERO;
    BigInteger ten = new BigInteger("10");
    BigInteger hundred = new BigInteger("100");
    BigInteger nine = new BigInteger("9");
    BigInteger one = BigInteger.ONE;
    BigInteger two = new BigInteger("2");
    BigInteger dig, mul;
    
    for (int i = 0; i <= k; i++) {
      String s = str.substring(i << 1, Math.min(n, (i << 1) + 2));
      if (s.length() == 0) {
        break;
      }
      num = num.multiply(hundred).add(new BigInteger(s));
      dig = nine;
      mul = ans.multiply(two).multiply(ten).add(dig);
      mul = mul.multiply(dig);
      while (mul.compareTo(num) > 0) {
        dig = dig.subtract(one);
        mul = ans.multiply(two).multiply(ten).add(dig);
        mul = mul.multiply(dig);
      }
      ans = ans.multiply(ten).add(dig);
      num = num.subtract(mul);
    }
    
    out.println(ans.toString());
    
    in.close(); out.close();
  }

  public static void main(String[] args) throws Exception {
    new Main().run();
  }
}