Когда жители N (количество деревень) встретятся снова?
Таким образом, проблема — часть прошлой статьи соревнования по программированию, с которой я столкнулся. Учитывая число N, представляющее количество деревень вокруг центра города, жители первой деревни каждые несколько дней ходят в город, чтобы купить свои припасы, жители второй деревни каждые 2 дня и т. Д. Все жители деревни встречались. сегодня в центре города. Нас просят найти, когда жители по крайней мере Деревни N-1 снова посетят центр города в тот же день!
ПРИМЕРЫ:
ПРИМЕР 1:
ВХОД 1: 1 2 3 4 5 6 7 8 9 10 -> ВЫХОД: 360 7
В приведенном выше примере все жители деревни, кроме жителей 7-й деревни, встретятся снова через 360 дней.
ПРИМЕР 2:
ВХОД: 10 14 15 30 21 5 40 4 8 -> ВЫХОД: 840 0 (все жители встретятся снова через 840 дней).
ПРИМЕР 3:
ВХОД: 25065 3575 12305 88590 1758 -> ВЫХОД: 25845383485350 4 (поэтому после 25845383485350 все жители деревни, кроме жителей 4-й деревни, встретятся снова).
Есть ли подход, который не использует рекурсию? Спасибо!
Решение
Ваша проблема, по сути, является наименее распространенным множителем (Если жители города посещают каждые 5 дней и посещают день 0, они также посещают дни 5, 10, 15, 20 … это явно кратно.)
Следовательно, хороший способ решить эту проблему — разделить числа на простые множители, и для каждого простого множителя использовать максимально найденную потенцию.
С примером 2:
10, 14, 15, 30, 21, 5, 40, 4, 8 = 2 * 5, 2 * 7, 3 * 5, 2 * 3 * 5, 3 * 7, 5 2 ^ 3 * 5, 2 ^ 2 , 2 ^ 3
-> принимая максимальные потенции: 2 ^ 3 * 3 * 5 * 7 = 840
Если вы измените проблему, чтобы иметь смещения («жители деревни 1 были в городе 10 десятков лет назад»), вы, кстати, можете использовать теорему об остатках в Китае.
Редактировать:
Что касается варианта деревни N-1, сделайте так:
Создайте главные факторы снова, но на этот раз посчитайте, какая сила какого простого числа встречается и как часто. Снова создайте максимальные потенции, а затем итерируйте по деревням, чтобы увидеть, сколько времени потребуется деревням, чтобы встретиться, игнорируя эту конкретную деревню. Имея счет потенции, вы можете легко увидеть эффект удаления деревни.
Я думаю, что знания этой идеи достаточно, чтобы написать код, но если вам нужно, чтобы я уточнил, просто скажите.
Разрабатывая это:
Для каждого простого числа сохраняйте, какую потенцию можно найти как часто.
С примером 2:
10, 14, 15, 30, 21, 5, 40, 4, 8 = 2 * 5, 2 * 7, 3 * 5, 2 * 3 * 5, 3 * 7, 5 2 ^ 3 * 5, 2 ^ 2 , 2 ^ 3
- Для 10 = 2 * 5 мы храним:
- 2 имеет потенции 1 (х1)
-
5 имеет потенции 1 (х1)
-
Для 14 = 2 * 7 мы обновляем это так:
- 2 имеет потенции 1 (х2)
- 5 имеет потенции 1 (х1)
- 7 имеет потенции 1 (х1)
-> в конце:
- 2 имеет потенции 1 (х3), 2 (х1), 3 (х2)
- 3 имеет потенции 1 (х3)
- 5 имеет потенции 1 (х5)
- 7 имеет потенции 1 (х2)
Теперь мы снова просматриваем весь список, убираем текущие потенции, если они были найдены только один раз, и затем видим их продукт. Мы сохраняем минимум этого продукта.
Мы инициализируем минимум со всем продуктом, в данном случае 840.
- Мы оцениваем 10 = 2 * 5. Ни потенцию 1 из 2, ни потенцию 1 из 5 не обнаруживают только один раз, поэтому продукт остается 840.
- То же самое верно для всех других чисел, за исключением потенции 2 из 2, как найдено в 4 = 2 ^ 2
- Но так как у нас также есть потенция 3 из 2, это не имеет значения, и мы остаемся с нашими 840.
Давайте сделаем наш собственный пример: 72, 74, 75 и 296 = 2 ^ 3 * 3 ^ 2 2 * 37 3 * 5 ^ 2 и 2 ^ 3 * 37
->
- 2 имеет потенции 1 (х1), 3 (х2)
- 3 имеет потенции 2 (х1), 5 (х1)
- 5 имеет потенции 2 (х1)
- 37 имеет потенции 1 (х2)
Пока все деревни не встретятся снова, мы должны ждать (2 ^ 3)(3 ^ 5)(5 ^ 2) * 37 = 1798200 дней
- Если мы вынимаем 72, мы теряем одну потенцию 3 из 2 и одну 2 из 3. Первая не имеет значения, так как она существует более одного раза, вторая тоже, поскольку существует более высокая эффективность 3 (^ 5).
- Если вынуть 74, то же самое верно
- Однако, если мы достанем 75, мы обнаружим, что его потенция 2 из 5 является единственной, и мы можем ее убрать. (2 ^ 3) * (3 ^ 5) * 37 = 71928, что является нашим новым минимумом
- 296 снова не имеет значения, так как 2 ^ 3 найден дважды и 37 ^ 1 тоже.
Таким образом, мы получаем, что в следующий раз, когда встретятся деревни N-1, пройдет 71928 дней, когда присутствуют все, кроме 75 человек.
Это помогло?
Другие решения
Других решений пока нет …