Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 05.09.2008, 18:04
гость

 
Сообщений: n/a

111 Very Simple Problem
Как решать?
бинарным поиском слишком долго.
что ещё, алгоритм извлечения корня?
  #2  
Старый 05.09.2008, 19:28
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

ну понятно, что количество цифр в ответе равно (k + 1) / 2.
будем их перебирать от старших, т. е. на старшее место ставим 9, возводим в квадрат, если получилось больше того, что на входе, то уменьшаем ее на 1, и т. д.
__________________
Irreparabilium felix oblivio rerrum.
  #3  
Старый 05.09.2008, 19:28
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

да k - количество цифр в исходном числе =)
__________________
Irreparabilium felix oblivio rerrum.
  #4  
Старый 09.09.2008, 21:43
гость

 
Сообщений: n/a

ага и сколько это операций получается в худшем случае для 1000значного числа ? ((: т.е. вы предлагает перебрать все 500 значные числа.
у меня двоичный поиск в таком интервале не справляется.
  #5  
Старый 11.09.2008, 17:26
cmd cmd вне форума
Пользователь

Отправить личное сообщение для cmd Посмотреть профиль Найти все сообщения от cmd
 
Регистрация: 10.12.2006
Адрес: VSTU[Volgograd]
Сообщений: 53

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

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

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

А вообще на этой задаче у меня бинпоиск прошел на яве
  #6  
Старый 24.09.2008, 18:14
гость

 
Сообщений: n/a

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

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

 
Сообщений: n/a

написал извлечения корня в столбик.. сдал!
только так не интересно, хочу бинарным поиском сдать, буду оптимизирвать
(a+-2^n)^2
  #8  
Старый 09.11.2009, 06:40
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

Моя реализация на 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();
  }
}
__________________
Irreparabilium felix oblivio rerrum.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Timus 1113 (Jeep problem) гость Задачи 2 23.01.2008 03:41
Problem: распил двоичного дерева ExPerT Реализация, исходники, языки 1 04.11.2007 14:07