Всем привет! Хотелось бы услышать ваши соображения по поводу задачки:
На столе стоят N (1 ≤ N ≤ 10000) занумерованных фарфоровых канареек. Каждая канарейка покрашена в какой-то цвет, зашифрованный с помощью чисел (всего цветов не более 1000). Роботу даётся несколько запросов в виде двух целых чисел: A (1 ≤ A ≤ 10000) и B (1 ≤ B ≤ 1000). Робот окрашивает всех канареек с порядковым номером кратным A в цвет B. В случае если A = 1 робот окрашивает канареек, с номером являющимся простым числом или 1. Робот красит канареек вне зависимости от их первоначального цвета. Вам необходимо за наименьшее число запросов и наименьшее число окрашиваний добиться того, что все канарейки покрашены в один цвет. В качестве ответа на задачу выведите в любом порядке последовательность команд.
UPD: Внесено уточнение. Не сразу заметил, что первая канарейка никогда не перекрашивается. Спасибо riadwaw!
Можно заметить, что нужно красить в цвет первой канарейки(т.к она не меняет цвет)
Далее если бы никто не был такого же цвета, как первая, можно было бы выбрать все простые до корня(они точно нужны для чисел — квадратов) и (обычно) 1
Пока не понятно, как решать в общем случае
riadwaw, дело в том, что изначально канарейки покрашены в один какой-то цвет. И нужно написать минимально возможную последовательность таких команд, чтобы было минимальное число перекрашиваний.
Более того, может случиться так, что все канарейки с номером кратным какому-нибудь p не выгодно перекрашивать, т.к. они уже покрашены в нужный цвет (канареек данного цвета дольше всего до перекрашиваний).
Вот если бы было в 1 цвет, тогда было бы как раз легко:)
Да, я понимаю, поэтому и говорю, что
Поменял условие. Понял, что с налажал с единицей, спасибо! А вот относительно цветов, я просто не так выразился)
Если научиться решать для фиксированного цвета первой, то можно перебрать в какой цвет мы ее покрасим и решать также.