| Автор: | А. Жуплев, А. Кленин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 8 Мб | |
| Выходной файл: | output.txt |
Несмотря на быстрый рост производительности компьютеров, некоторые вычислительные задачи по прежнему требуют долгих расчётов. Дешёвым и эффективным методом решения части таких задач являются вычислительные кластеры. Кластер — это группа разнородных компьютеров, связанных локальной сетью, между которыми распределяется работа. Кластер обычно имеет центральный сервер, который занимается разделением исходной задачи на подзадачи и сбором решения из частичных решений, полученных компьютерами, входящими в кластер.
Пусть кластер состоит из N компьютеров и сервера. Компьютеры имеют разную производительность, так что i-й компьютер заканчивает расчёт одной подзадачи за ti секунд. По окончании расчёта компьютер отправляет результаты на сервер, получает в ответ следующую подзадачу, тратит на неё ещё ti секунд, и т.д. Таким образом, в одну секунду на сервер могут прийти ответы от нескольких компьютеров.
Поскольку количество компьютеров в кластере можно легко наращивать, центральный сервер часто становится узким местом, ограничивающим общую производительность. Требуется написать программу, которая определит, через сколько секунд после начала работы кластера нагрузка на сервер впервые достигнет максимума — все N компьютеров одновременно отправят ответы на сервер.
В выходном файле должно содержаться количество секунд до максимальной загрузки. Так как это число может быть очень велико, оно должно быть выведено в виде разложения на простые множители. При этом множители должны быть отсортированы по возрастанию и разделяться символом '*' (ASCII 42). Если степень вхождения простого числа больше единицы, следует указать её вслед за числом, разделив их символом '^' (ASCII 94).
Например: число 25 будет иметь вид: 5^2, а число 3000 — 2^3*3*5^3.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|