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

так как у нас образовался клуб любителей hackerrun которые не быдлокодят формочки
вопрос с моего собеседования на hackerrun на решение дели 15 минут
если надо могу пояснить условие задачи




K caterpillars are eating their way through N leaves. Each caterpillar falls from leaf to leaf in a unique sequence. All caterpillars start at a twig in position 0 and fall onto the leaves at positions between 1 and N. Each caterpillar i has an associated 'jump-number' Ai. A caterpillar with jump number j eats leaves at positions that are multiples of j. It will proceed in the order j, 2j, 3j, ... till it reaches the end of the leaves, then it stops and builds it cocoon.



Given a set A of K elements, we need to determine the number of uneaten leaves.



Input Format:

N = number of leaves
K = number of caterpillars

A = Array of integer jump numbers (one per line).



Constraints:

1 < N < 10^9

1 < K < 15

1 < A[i] < 10^9

Output Format:

Print an integer denoting the number of uneaten leaves.

Sample Input:

10
3
2
4
5

Sample Output:

4

Explanation: [2,4,5] is the 3-member set of jump numbers. All leaves which are multiples of 2, 4, and 5 are eaten. Only 4 leaves which are numbered 1,3,7,9 are left.

Здравствуйте, sergey2b, Вы писали:
S>вопрос с моего собеседования на hackerrun на решение дели 15 минут

ушло меньше 15 минут:

#include <iostream>
#include <vector>

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];

    int cl = 0;
    for(int i = 1; i <= l; ++i)
    {
        bool e = false;
        for(auto& v: eat){
            if(!(i % v)){
                e = true;
                break;
            }
        }
        if(!e)
            ++cl;
    }
    std::cout << cl << std::endl;
}

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

10^9 это 10 в 9 степени те 1 000 000 000 и масcив шагов может быть 1 000 000 000 и гусинец 15

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

S>10^9 это 10 в 9 степени те 1 000 000 000 и масcив шагов может быть 1 000 000 000 и гусенец 15

и что? минутки за 3 просчитает невижу тут причин для оптимизации преждевременной)

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


S>>10^9 это 10 в 9 степени те 1 000 000 000 и масcив шагов может быть 1 000 000 000 и гусенец 15

S>и что? минутки за 3 просчитает невижу тут причин для оптимизации преждевременной)

вас здесь некто за язык не тянул — а реальная разработка это когда гуи формочки и простенькие sql запросики?

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

S>вас здесь некто за язык не тянул — а реальная разработка это когда гуи формочки и простенькие sql запросики?

вы приписываете какие-то воображаемые требования к задаче(например по использованию cpu), которых небыло изначально?

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


S>>вас здесь некто за язык не тянул — а реальная разработка это когда гуи формочки и простенькие sql запросики?

S>вы приписываете какие-то воображаемые требования к задаче(например по использованию cpu), которых небыло изначально?

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

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

S>>вопрос с моего собеседования на hackerrun на решение дели 15 минут
S>ушло меньше 15 минут:

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

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

Какое то не полное условие. А что будет с гусеницей, когда она прыгнет и попадет на уже съеденный лист? Сдохнет? Будет прыгать дальше? Или я что-то пропустил в условии? Что будет если на один лист попадут две гусеницы? Съедят его в 2 раза быстрее? Тогда надо вводить "шаги" это процесса и уметь их дробить. Одна съест другую? по какому критерию? После этого она останется на этом листе в следующем шаге или окуклится?

Не люблю, когда ради оживляжа берут математическую проблему и начинают накручивать вокруг нее какую-то "историю". Тем кому интересна математика это не надо, кому математика не интересна все равно читать не будут. А иногда получается вот такая же чушь...

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

S>и что? минутки за 3 просчитает невижу тут причин для оптимизации преждевременной)

Гусеницы всё равно медленнее прыгают, как бы голодны они ни были.

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

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

S>Какое то не полное условие. А что будет с гусеницей, когда она прыгнет и попадет на уже съеденный лист? Сдохнет? Будет прыгать дальше? Или я что-то пропустил в условии? Что будет если на один лист попадут две гусеницы? Съедят его в 2 раза быстрее? Тогда надо вводить "шаги" это процесса и уметь их дробить. Одна съест другую? по какому критерию? После этого она останется на этом листе в следующем шаге или окуклится?

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

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

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

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

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

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

нет все гусеницы идут до посленего листа в списке и потом на другое дерево

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

S>Здравствуйте, sergey2b, Вы писали:
S>>вопрос с моего собеседования на hackerrun на решение дели 15 минут

S> for(int i = 1; i <= l; ++i)

А мне по условию показалось, что листья с нуля нумеруются.

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

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

S>так как у нас образовался клуб любителей hackerrun которые не быдлокодят формочки
S>вопрос с моего собеседования на hackerrun на решение дели 15 минут

Это за 15 минут надо было накодировать что ли? Или придумать решение?

S>если надо могу пояснить условие задачи

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

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

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

Hackerrank? Или есть еще какой-то hackerrun?

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

_DA>Hackerrank? Или есть еще какой-то hackerrun?

Нету, конечно, речь о Hackerrank.

Тут вроде сводится к нахождению взаимно съеденных листьев, т.е. таких, которые могла бы съесть данная гусеница, но которые были съедены до нее другой.
Например: если сначала была гусеница с шагом 4, а затем с шагом 6, то на ее пути будут съедены листья с индексами, кратными 12.
Это количество можно найти как (всего листьев / НОК (шаг пред, шаг)).
НОК можно посчитать зная НОД.
НОД, в свою очередь, можно посчитать по алгоритму Евклида, который описан у Кнута в 4.5.2.
Для каждой следующей гусеницы надо учитывать съеденное всеми предыдущими.

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


_DA>Это за 15 минут надо было накодировать что ли? Или придумать решение?

накодировать собеседование в Блумбрег

Здравствуйте, sergey2b, Вы писали:
_DA>>Это за 15 минут надо было накодировать что ли? Или придумать решение?

S>накодировать собеседование в Блумбрег

Жесткие они.. интересно вот, им реально нужны именно олимпиадники? ) Слабо верится, что человек, никогда не участвовавший в алгоритмических соревнованиях, за 15 минут напишет работающее решение.

А как решать задачу понятно стало?