Комментарии 23
Тут вопрос о вероятности, а не о времени.
Время — любое в интервале 7-12 часов (ибо скорости не постоянные), а вероятность 100%
Примем объем ванной за N литров, и выразим скорости прибывания горячей как N/18, холодной как N/15, а убывания как N/10. Тогда итоговая скорость наполнения будет N/18 + N/15 — N/10 = 2N/90. Отсюда время наполнения N/ (2N/90) = 45 минут
В сумме за минуту заполнится 1/15 +1/18 — 1/10 = 1/45, значит вся ванна заполнится за 45 минут.
В задаче 1 нестыковка — если мы можем нажать только кнопки выше, ниже, левее или правее текущей, то как получаются комбинации 00, 11, 22 и т.д.? Ведь сама текущая кнопка под это определение не подходит.
1/(1/15 + 1/18 - 1/10)
= 1/(1/(3*5) + 1/(2*3*3) - 1/(2*5))
= (2*3*3*5) / (2*3 + 5 - 3*3)
= 90 / 2
= 45В задаче 2 непонятно — можно нажимать только кнопки в 1-окрестности от заданной?
Т.е. если задана кнопка 0 и длина 3, то можно получать {'0','8'}*3?
Если так, то задача тупая. Для каждой кнопки мы знаем основание степени:
0 — 2
1 — 3
2 — 4
3 — 2
и т.д.
И возвести это основание в показатель длины.
Если же имеется в виду, что можно нажимать эту-и-соседние кнопки, то задача будет о количестве путей заданной длины в графе.
В этом случае берём матрицу смежности и возводим в N-ную степень в кольце (макс,+)...
Если у нас есть O(N) дополнительной памяти и не жалко рекурсивно спускаться, то заводим табличку "оригинал-копия".
std::map<node*, node*> copies;
node* clone(node* original) {
if (!original) return NULL;
node*& copy = copies[original];
if (copy) return copy;
copy = new node;
// принципиально, что мы сперва создаём и регистрируем копию в таблице,
// а уже потом рекурсивно спускаемся (возможно, попадая на самих себя!)
node->key = original->key;
node->left = clone(original->left);
node->right = clone(original->right);
node->random = clone(original->random);
return node;
}Если жалко, то придётся изгаляться.
Например, если у нас есть гарантии того, что это именно дерево, то поступим следующим разрушающим образом:
1) построим двудольное дерево: нечётный слой (оригинал) ссылается на чётный (копию) через random, а чётный (копия предыдущего) — на следующий нечётный оригинал.
2) расслоим дерево: нечётные слои ссылаются на нечётные, чётные — на чётные
void duplicate(node* o) {
if (!o) return;
node* c = new node(o);
o->random = c;
duplicate(c->left);
duplicate(c->right);
}
void separate(node* o) {
node* c = o->random;
c->left = c->left ? c->left->random : NULL;
c->right = c->right ? c->right->random : NULL;
node* r = c->random;
c->random = c->random ? c->random->random : NULL;
o->random = r;
separate(o->left);
separate(o->right);
}
node* copy(node* root) {
if (!root) return NULL;
duplicate(root);
node* c = root->random;
separate(root);
return c;
}Вроде бы, не налажал.
Вычисляем среднее количество страниц которые нужно читать каждый день. Читаем главу, смотрим на количество страниц следующей главы, если прочитав следующую главу читатель отклонится от среднего количества страниц к прочтению больше чем в данный момент, читатель останавливается. В противном случае — продолжает читать.
Пример 2: {8, 5, 6, 12} — среднее количество страниц 10,(3)
Д1 — Читаем 8 страниц (отклонение 2,(3)), если прочитаем ещё 5 (8 + 5 = 13) получим отклонение 2,(6), что больше, значит нужно остановится.
Д2 — Читаем 5 страниц (отклонение 5,(3)), если прочитаем ещё 6 получим отклонение 0,(6), значит продолжаем, если прочитаем ещё 12 получим отклонение больше, значит нужно остановится.
Д3 — Читаем оставшееся.
Пример 3: {8, 5, 10, 12} — среднее количество страниц 11,(6)
Д1 — Читаем 8 страниц (отклонение 3,(6)), если прочитаем ещё 5 (8 + 5 = 13) получим отклонение 1,(4), значит читаем дальше, если прочитаем ещё 10 страниц получим большее отклонение значит останавливаемся.
…
Метод не сработает при {20,1,1,1} и k=3. Все оставшиеся страницы будут прочитаны в 1 день. Нужно наверное корректировать среднее на оставшиеся дни.
К задаче 3.
Как точно сформулировать критерий оптимальности? Чтобы минимизировать максимальное отклонение от среднего количества страниц, или чтобы минимизировать среднеквадратичное отклонение, к примеру?
Кажется, можно придумать набор данных, при котором результаты по этим критериям будут различаться.
Подумал и понял, что нам пофиг на вид целевой функции.
Лишь бы она была (тут я забыл линейную и абстрактную алгебры, как называется класс таких структур...).
Это задача на динамическое программирование!
Пусть у нас N глав по p0, p1, p2, ..., p[N-1] страниц, итого P страниц, и K дней.
(Если N <= K, то решение тривиально)
В среднем выходит M = P/K страниц в день — это базовая линия.
В первый день прочитали 0..N глав (на самом деле, 1..N-K+1 — если требовать не менее 1 главы в день).
Это s[k] = 0 + p0 + p1 +… + p[k-1] страниц в сумме.
Что дало нам отклонения первого дня d0… dN.
Для макса это абсолютное отклонение dk=|M-sk|, для скво — квадрат отклонения dk=(M-sk)^2 — это член суммы для дисперсии.
Во второй день ещё прочитали — от первого дня до 0..N главы включительно.
s'[i,k] = p[i] +… + p[k-1] — прочитано во второй день
d'[i,k] = delta(M, s'[i,k]) — отклонение второго дня.
d"[i,k] = union(d[i], d'[i,k]) — отклонение за два дня
Для макса — это максимум, для скво — сумма (мы потом должны поделить и искоренить, но не будем торопиться).
Итого за два дня мы получаем новые значения d[k] = min(i) d"[i,k] — наилучшие результаты для каждого количества глав.
Третий день — аналогично второму.
И т.д.
Чуть позже напишу на питончике
import itertools
# выбор целевой функции - и соответствующих операций.
# delta - считает отклонение
# union - складывает отклонения
if 1:
# максимальное отклонение
def delta(M, s):
return abs(M-s)
def union(s1, s2):
return max(s1, s2)
else:
# дисперсия (и, соответственно, скво - но нам проще считать дисперсию)
def delta(M, s):
return (M-s)**2
def union(s1, s2):
return (s1 + s2)
def paginate(p, K, verbose=True):
'''
разбивает главы на дни
p - количество страниц в каждой главе
K - количество дней
verbose - отладочный вывод
'''
assert p
assert K
# посчитаем бегущие суммы, чтобы быстро находить сумму страниц меж глав i:j
# с этого момента нам страницы не нужны (и это мог быть итератор, а не список)
s = [0] + list(itertools.accumulate(p))
# sum(p[:j]) = s[j]
# sum(p[i:j]) = s[j]-s[i]
def sij(i, j):
return s[j] - s[i]
assert len(s) > K
# количества прочтённых глав, от 0 до N+1
range_N1 = range(len(s))
# среднее количество страниц в день
M = s[-1] / K
# отклонение за один день, меж глав i:j
def dij_daily(i,j):
return delta(M, sij(i,j))
# отклонения предыдущего дня (инициализировано первым днём)
d_prev = [dij_daily(0,j) for j in range_N1]
# наилучшие решения предыдущего дня
# списки количества страниц за каждый день
# (инициализировано первым днём - прочли всё по 0:j'ю главу)
h_prev = [[sij(0,j)] for j in range_N1]
# итоговое отклонение (предыдущий + текущий дни)
def dij_total(i,j):
return union(d_prev[i], dij_daily(i,j))
if verbose:
print('day 0:')
for j in range_N1:
print(f' {j} : {p[0:j]}={h_prev[j]} @ {d_prev[j]}')
print()
# для следующих дней - динамическое программирование
for day in range(1, K):
if verbose:
print(f'day {day}:')
# новые результаты будут здесь
d_next = [None for _ in s]
h_next = [None for _ in s]
# для каждого итогового количества глав, прочтённых к этому дню
for j in range_N1:
# находим лучшее предыдущее количество глав
i = min(range(j), default=0, key=lambda i:dij_total(i,j))
# компоненты наших формул (для отладочного вывода)
# суммы страниц предыдущего дня, этот день, к концу этого дня
hi, hij = h_prev[i], sij(i,j)
hj = hi + [hij]
# отклонение предыдущего дня, этого дня, к концу этого дня
di, dij, dj = d_prev[i], dij_daily(i,j), dij_total(i,j)
# записываем результат.
d_next[j] = dj
h_next[j] = hj
if verbose:
print(f' {i}->{j} : {hi} @ {di:.2f} + {p[i:j]}={hij} @ {dij:.2f} => {hj} @ {dj:.2f}')
if verbose:
print()
# был день текущий, стал предыдущий
d_prev, h_prev = d_next, h_next
# возвращаем последний список страниц - охватывающий все главы.
return h_prev[-1]
Выпуск#23: ITренировка — актуальные вопросы и задачи от ведущих компаний