algoprog.kz

если мы нажмем _t_ раз вверх , тогда (n - t) раз должны нажать вниз.
И мы в конце окажемся на этаже t * u - ( n - t) * d.
т.е у нас теперь есть функция f(t)=t * u - ( n - t ) * d;

и можно доказать что функция монотонная.

Prove:
f(t)= t * u - d * n + t * d => f(t)= t * ( u + d ) - d * n так как u>0&d>0 , функция будет строго возрастать. Нам надо найти минимальный _t_ , что бы функция строго была больше нуля. Так как функция монотонная можно применить бинарный поиск

upd: можно еще легче , т.е честно решить уравнение

t * u - d * n + t * d > 0
t * (u+d) > d * n
t > d * n / (u+d)

Здесь понятно что, t = d * n/(u+d)+1

Переформулируем нашу задачу на язык математики. В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их n. Значит, нам требуется представить n в виде суммы возрастающих натуральных слагаемых.

---

1 | |
---------
4 | | | | |
-----------
5 | | | | | |
-----------------
8 | | | | | | | | |
-----------------

n=1+4+5+8

Пусть в качестве первого слагаемого мы взяли L, тогда нам требуется n-L разбить на слагаемые. Но теперь добавляется дополнительное условие - слагаемые должны быть больше либо равны L+1. Значит, нам достаточно научиться считать число разбиений числа n на слагаемые не меньшие k (обозначим an,k). Есть два случая: слагаемое k либо входит в разбиение (таких способов a[n-k][k+1]), либо нет (таких способов a[n][k+1]). Так как никакое разбиение не подходит одновременно под оба эти случая, то a[n][k]=a[n-k][k+1]+a[n][k+1] Заметим, что для единицы существует единственное разбиение: 1 = 1. Значит a[1][0] = a[1][1] = 1, a[1][f] = 0, где f >= 2. a[n][k] удобно вычислять в порядке невозрастания k. При равных k - в произвольном порядке.

Данный алгоритм выполняет порядка N^2 действий.

источник: olympiads.ru

Пусть c1,c2, ... ,cn, - данная последовательность.

Покажем, как найти длину максимальной возрастающей

подпоследовательности, заканчивающуюся в элементе ck (обозначим ak).

Предположим, она уже найдена.

Удалим из нее последний элемент. Полученная подпоследовательность

является максимальной возрастающей подпоследовательностью,

оканчивающейся в некотором элементе cj (j < k).

Значит, либо ak = max{j < k, cj < ck}{aj} + 1, либо ak = 1, если

таких j не существует. Ответом на поставленную задачу будет максимум

из всех ak.

Число действий, выполненных данным алгоритмом, пропорционально N^2.

источник: olympiads.ru

на Jave есть такая функция modPow .
т.е ans=a.modPow(b,c).
а a,b,c типа BigInteger.

Сначала напишем наивное решение этой задачи :

1. cnt=0;    
2. for (int i = 1;i<(int)sqrt(n);i++)   
3.     if (n % i == 0) cnt =(cnt + 2)%2  // делители i,n/i   
4.   if (n%(int)sqrt(n) == 0) cnt=(cnt+1)%2;   

думаю здесь все понятно. Разобрав этот код мы можем привести вам умное решение!

Пробежимся циклом до sqrt(n) и для каждого делителя числа n

будем проверять условие

  if (n % i == 0) cnt =(cnt + 2)%2,

а это равно (cnt+2)%2 -> (cnt%2+2%2)%2 -> cnt%2 -> 0

т.е нет смысла выполнять FOR.

Думаю здесь можно применить динамику. Типа такого, если d[i][j] == true, тогда используя только первыe i элементов можно получить j единичных столбцов.

Подробности потом, когда я её решу =)

После прочтения этой задачи вам наверно сразу покажется что лексикон Мумба-юбийцев(или Мумбаюбов :) не очень богат,количество слов в их словаре не больше 17!Что же касается решения задачи - перебор!Вот и все!при N>17 ответ к задаче будет равен нулю (0) .

В этой задаче нам дано три окружности.И наша основная задача состоит в нахождении пересечения этих 3ех окружностей.В кратце это и должно быть решением.

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

Если же вы не знаете как это сделать советую научится)))

Прочитайте в Кормене))может там и найдете ))

Задачу можно решать, например, таким образом. Переведем заданное во входном файле время в секунды, считая началом отсчета начало суток. Например, время 12:30:00 соответствует 12 * 3600 + 30 * 60 = 45000 секундам. Аналогично переведем требуемый интервал в секунды и прибавим его к начальному моменту времени — получим требуемое время, только заданное в секундах. Затем переведем это время в требуемый формат и выведем в выходной файл. При таком решении единственная возникающая проблема заключается в том, что полученный ответ может превысить максимально допустимое значение типа данных LongInt. Для хранения числа секунд можно было использовать тип данных Int64 языка FreePascal или тип данных long long int языка GCC. Другой подход к решению состоит в том, что к начальному числу секунд прибавляется число секунд временного интервала, полученное число секунд переводится в минуты и секунды, минуты “запоминаются”, а секунды записываются как секунды ответа. Далее прибавим число минут интервала и “запомненные” минуты к начальным минутам, опять “запомним” лишние часы и т.д. При таком решении типа данных LongInt достаточно .