Школа179: /Информатика//Информатика / Олимпиады/2008?//Информатика / Олимпиады / 2008 / Школьная//Информатика / Олимпиады / 2008 / Школьная / Разбор?/D ...

 

Разбор задачи D


Условия задачи четвертого тура


Пусть n – исходное число. Если n=1, то ответом является 1. Иначе будем нам необходимо представить n в виде произведения нескольких чисел (цифр) от 2 до 9.


При этом нам необходимо чтобы суммарное количество цифр было как можно меньше (тогда удастся составить меньшее число), кроме того, желательно использовать как можно бoльшие цифры, тогда другие цифры получатся меньше и также можно будет составить меньшее число. Например, если необходимо представить требуемым образом число 24, то лучше использовать делитель 8, т.к. тогда удастся представить число 24=3*8. Если же не использовать делитель 8, а использовать делитель 6, то получится худшее представление: 24=4*6.


Таким образом, будем делить число последовательно на цифры 9, 8, 7, 6, 5, 4, 3, 2, пытаясь получить в разложении большие цифры. Для нахождения минимального числа полученные цифры необходимо будет записать в обратном порядке.


Также следует учесть проблему переполнения результата: например, если исходное число равно 510=9765625, то правильный ответ будет иметь вид 5555555555, и его невозможно будет записать в переменной типа int. Поэтому результат будем записывать в строку Result.


int n;
cin >> n;

// Отдельно разберем случай n==1
if(n==1)
{
    cout<<1<<endl;
    return 0;
}
        
string Result; // Для записи ответа
int digit;       // Переменная – перебираемая цифра

// Цикл по всем цифрам от 9 до 2        
for(digit=9;digit>=2;--digit)
{
    // Будем делить число n на цифру digit пока это возможно
    while(n%digit==0)
    {
        n/=digit;
        // Цифру digit дописываем в начало строки Result
        Result=(char)('0'+digit)+Result;
    }
}

// Если в результате не получилось число 1, то n имеет простые делители, большие 9
// поэтому выведем 0, иначе выведем всю строку Result
if(n!=1)
    cout<<0<<endl;
else
    cout<<Result<<endl;


 
Файлы[Скрыть файлы/форму]