Решение задачи "Подели на три, умножь на два" с Codeforces

Без пояснения   Просмотров: 9


Поликарп любит играть с числами. Он берет некоторое целое положительное число x, выписывает его на доску, и выполняет с ним n−1 операцию двух видов:

поделить число x на 3 (число x должно быть кратно 3);
умножить число x на 2.
После каждой операции Поликарп выписывает результат операции на доску, а число x заменяет на результат операции. Таким образом, на доске окажутся ровно n чисел.

Вам задана последовательность длины n — числа, которые выписал Поликарп. Эта последовательность задана в произвольном порядке, то есть порядок чисел может не соответствовать порядку их записи на доску.

Ваша задача — переупорядочить элементы последовательности так, чтобы она соответствовала возможной игре Поликарпа в порядке записи чисел на доску. Таким образом, каждое следующее число в последовательности должно быть либо ровно в три раза меньше предыдущего, либо ровно в два раза больше предыдущего.

Гарантируется, что ответ существует.

Код

#include <bits/stdc++.h>

using namespace std;
pair <long long,long long> a[200];
int n;
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i].second;
        long long tmp=a[i].second;
        while (tmp%3==0)
        {
            a[i].first--;
            tmp/=3;
        }
    }
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++)
        cout<<a[i].second<<" ";
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться