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

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

S>>я задал аналогичный вопрос (к сожаллению не сохранил пояснений)
S>>если она попала на уже съеденный лист тут же переходит к следующему

S>Отлично! А есть ли ограничение на число прыжков, которое может сделать голодная гусеница? Если она в конце концов остановится изголодав полностью, то следующая гусеница попавшая на нею может ее съесть и продолжить путешествие?

S>Ну и так до бесконечности...

нет гучиница не может умереть по дороге она дойдет до конца всех листьев и перейдет на другое дерево (я вообще не знаю зачем они стали про гусинец говорить а не дали формальную задачу)

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

В общем, нужно посчитать количество чисел из [1..N] кратных {Ai}. Ну, или дополнение до N, если угодно.

Обозначим множество чисел из R=[1..N] кратных произвольным числам a,b,...,z как M(a,b,...z) — Multiples
Мощность |M(abc..z)| = m(abc...z)

Для одиночного множителя
m(f) = floor(N/f)

Для пары множителей
M(a,b) = M(a) U M(b)
m(a,b) = m(a)+m(b)-m(a#b) — где a#b — наименьшее общее кратное — поскольку кратные НОК'у множителей мы сосчитали дважды, то одно вхождение выкинем

Для тройки
m(a,b,c) = m(a)+m(b)+m(c)-m(a#b)-m(a#c)-m(b#c)+m(a#b#c)

Ну и так далее.
Надо подумать (сейчас немножко влом), как посчитать для K-кортежа. То ли рекурсивно, то ли рекуррентно, то ли в цикле, забегом по K-битным числам.

Разумеется, следует подумать о том, как быстро считать НОКи сочетаний чисел. Возможно, что для больших K есть смысл сперва факторизовать числа, чтобы не считать НОК каждого с каждым "с нуля".

И разумеется, следует выполнять оценку трудоёмкости: что больше, O(2^K) или O(K*N).
Для N = 10^9, K ~ 15 выгоднее на НОКах. Для N ~ 1000, K = 15 — выгоднее брутфорсом.

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

KP>Потому как с точки зрения hackerrun – ты задачу не решил. Задачи там алгоритмические и O(n) за верный ответ там обычно не считается.

с точки зрения HackerRank, ты делаешь сначала задачу как угодно, а потом в случае завала каких-то тестов(например по перфомансу)- оптимизируешь код, для данной задачи вот оптимизация на перфоманс, но это не означает что нулевое решение бы не прошло все тесты

#include <iostream>
#include <vector>
#include <algorithm>

struct caterpillars
{
    int l, eat;
    std::vector<int> ctps;
    caterpillars(std::vector<int>&& ctps, int l) : ctps(ctps), l(l), eat(){
    }
    int next_eaten()
    {
        int next = l + 1;
        for(int v: ctps){
            int c = eat - eat % v;
            while(c <= eat)
                c += v;
            next = std::min(next, c);
        }
        eat = next;
        return eat;
    }
};

int main()
{
    int l, c;
    std::cin >> l >> c;
    std::vector<int> eat(c);
    for(int i = 0; i != c; ++i)
        std::cin >> eat[i];

    caterpillars cp(std::move(eat), l);
    int ce = 0;
    for(int next = 0; next <= l;){
        next = cp.next_eaten();
        if(next <= l)
            ++ce;
    }

    std::cout << (l - ce) << std::endl;
}

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

_DA>Могу направить в нужное русло. Нам нужно посчитать количество чисел от 1 до N, таких, что они не делятся нацело ни на одно из Ai. Будем искать другую величину, количество чисел, которые делятся как минимум на одно из Ai.
_DA>Возьмем некоторое Ai. Количество чисел, делящихся на Ai будет равно N / Ai. Можем сложить все эти значения, получим верхнюю оценку ответа S.
_DA>Теперь рассмотрим все возможные пары чисел (Ai, Aj), нам нужно будет найти все числа от 1 до N, которые делятся одновременно на Ai и на Aj, так как мы эти числа посчитали на предыдущем шаге дважды (как минимум), и вычесть количество таких числе из S. Затем рассмотреть все тройки чисел и т.д. Почитать про этот способ можно вот тут: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

Решение на Haskell, может кому будет интересно

import Control.Monad

-- Реализация функции включений-исключений
countIncExc :: Num a => ([t] -> a) -> [t] -> a
countIncExc f xs = sum [sign var * f var | var <- variants xs]
  where variants xs = filterM (const [True,False]) xs          -- все возможные варианты слагаемых
        sign var = if even (length var) then (-1) else 1       -- знак слагаемого
        
-- Решение задачи        
solve :: Integral a => a -> [a] -> a
solve totalLeaves caterpillarsJumps = totalLeaves - countIncExc f caterpillarsJumps
  where f [] = 0
        f jumps = totalLeaves `div` (foldl1 lcm jumps)

Пример:

solve 10 [2,4,5]
4

solve (10^9) [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
138704065

Сложность:
Если количество листьев N, а количество гусениц K, то сложность алгоритма будет
K * (2^K) * (log N), а вернее даже
K * (2^K) * (log (max A_i))

P.S. variants написан с помощью монад — элегантно, но непонятно.
Более понятно, но длиннее будет как-то так:

variants [] = [[]]
variants (x:xs) = 
  let vs = variants xs 
  in map (x:) vs ++ vs