Здравствуйте, Caracrist, Вы писали:

C>Bonus: solve this for K eggs and N stories

Элементарно.
Схема та же самая:
первое яйцо поднимаем с большими шагами до самого верха,
второе яйцо поднимаем с предпоследней до последней-1 попытки первого яйца,
и т.д.

Можно переиначить задачу, найти функцию N от K,T, где T — максимальное число попыток.

N(1,T) = T.
N(K,T) = N(K-1,T-1) + N(K-1,T-2) + ... + N(K-1,1)

и понятно, что O(N) = O(T**K).
N(2,T) = T*(T+1)/2
N(3,T) = T*(T+1)*(T+2)/6

N(K,T) = C(T+K-1,K)

То есть, функция очень лихо растёт, поэтому найти корень T :
N(K,T-1) < N <= N(K,T)
бисекцией будет очень быстро. Решать тырнадцатеричные уравнения аналитически — необязательно.

Здравствуйте, Caracrist, Вы писали:

C>Bonus: solve this for K eggs and N stories

	Элементарно.
	Схема та же самая: первое яйцо поднимаем с большими шагами до самого верха, второе яйцо поднимаем с предпоследней до последней-1 попытки первого яйца, и т.д. Можно переиначить задачу, найти функцию N от K,T, где T — максимальное число попыток. N(1,T) = T. N(K,T) = N(K-1,T-1) + N(K-1,T-2) + ... + N(K-1,1) и понятно, что O(N) = O(T**K). N(2,T) = T*(T+1)/2 N(3,T) = T*(T+1)*(T+2)/6 N(K,T) = C(T+K-1,K) То есть, функция очень лихо растёт, поэтому найти корень T : N(K,T-1) < N <= N(K,T) бисекцией будет очень быстро. Решать тырнадцатеричные уравнения аналитически — необязательно.

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