• Зарегистрирован: 2009-08-14
  • Сообщений: 6

Тема: [acm.timus.ru 1705] Зайцы-бандиты (Gangster Hares)

Условие:
Банда из k зайцев совершила разбойный налёт на склад с капустой и похитила n кочанов. Лиса в это время пробегала мимо и предложила им поделить награбленную капусту поровну между всеми членами банды. Зайцы согласились, условившись с лисой, что всем зайцам достанется одинаковое количество кочанов капусты, а остаток размером менее k кочанов лиса сможет забрать себе как плату за эту услугу.
Между тем, при разделе капусты к банде присоединился один заяц, который не принимал участия в налёте. Он получил ровно такую же долю, как и члены банды, однако остался незамеченным. «Почему?» — спросите вы. Дело в том, что каждый заяц получил такое же количество кочанов капусты, какое получил бы, если бы самозванец при разделе не присутствовал. Найдите минимальное количество зайцев в банде, при котором такое могло произойти.
Исходные данные:
Входные данные состоят из нескольких тестов. Первая строка содержит количество тестов t, 1 ? t ? 30000. В каждой из следующих t строк записано целое число n, 1 ? n ? 10^18.
Результат:
Для каждого теста выведите в отдельной строке целое число k — минимально возможное количество зайцев в банде.

Уже достаточно давно думаю над этой задачей. Мат. модель очевидна, нужно найти такое k, что n / k = n / (k + 1). Подключил всю команду, никаких результатов. Где-то слышал, что существует формула, от которой достаточно пройтись в две стороны на небольшое количество шагов. Где-то слышал, что надо что-то колдовать с функцией F(x) = [n/x] - [n/(x + 1)]. Но ни одну из идей развить не удалось.
На каком-то из форумов видел сообщение e-maxx'a о решении какого-то псевдоквадратного уравнения, но и это мне, конечно же, не помогло.
P.S. Если идти от корня и тупо проверять, то решение очевидно получит TLE, ведь при больших N количество шагов будет порядка нескольких десятков тысяч.

2 Ответ от it4.kp Отредактировано it4.kp (2009-08-24 14:41:04)

  • it4.kp
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-07-13
  • Сообщений: 15

Re: [acm.timus.ru 1705] Зайцы-бандиты (Gangster Hares)

Я решал так:
При маленьких k величина n/k-n/(k+1) довольно большая. При k близких к корню от n она начинает приближаться к единице. Найдем первое место где n/k-n/(k+1)==1. Затем оно будет и дальше убывать на 1 пока наконец не станет нулем. Соответственно бин. поиском ищем это место.

long long solve(long long n){
    int sq = sqrt((double)n);
    long long st = n/sq;

    long long l = sq, r = sq + 100000000;
    if (n/l == n/(l+1)) return l;
    while (n/l-n/(l+1) > 1) ++l;
    if (n/l == n/(l+1)) return l;
    st = n/l;
    sq=l;

    while (l+1<r){
        long long m = (l+r)/2;
        long long srx = n/m;
        if (st-srx == m - sq) l=m; else r=m;
    }

    return l;
}
  • Зарегистрирован: 2009-08-14
  • Сообщений: 6

Re: [acm.timus.ru 1705] Зайцы-бандиты (Gangster Hares)

Спасибо, идея отличная. Конечно, должен был сам до такого додуматься. Дерзну придраться маленько.
Вот эта строка:

long long st = n/sq;

и обе вот эти:

if (n/l == n/(l+1)) return l;

не нужны и вовсе. И тогда твой код - еще более короткое решение smile Еще раз спасибо.

4 Ответ от Seyaua Отредактировано Seyaua (2009-08-26 23:35:07)

  • Seyaua
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-16
  • Сообщений: 7

Re: [acm.timus.ru 1705] Зайцы-бандиты (Gangster Hares)

На самом деле существует формула, по которой можно вычислить ответ. Я нашел ответы для всех чисел от 1 до 10000, потом для всех ответов посчитал разность между корнем (целая часть) и ответом, а затем четко прослеживается закономерность.

Вот код (нахождение ответа для заданного n): 

long long q=S(n); //S(x) = (int)sqrt(x), сделано из-за возможного переполнения, то есть это своя функция нахождения корня
long long plus; //разность ответа и корня
if ((q+1)*(q+1)-(q+1)<=n) plus=S((q+1)*(q+1)-n-1)+1; else
  {
      long long x=S(q*(q+1)-n);
      if (x*(x+1)<q*(q+1)-n) plus=x+1; else
      plus=x;
  }

Естественно этот код можно еще сократить smile

5 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: [acm.timus.ru 1705] Зайцы-бандиты (Gangster Hares)

Ох, давно это было... smile

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

Тогда мы и придумали в итоге это шаманство: мы чем-то там пренебрегли, в итоге получили квадратное уравнение относительно m, решаем его, а потом решение нашей задачи ищем вокруг этих корней.

К сожалению, что за квадратное уравнение такое, я не помню, но понятно уже, что это шаманство полное smile

Сайтe-maxx