Решение задачи Число - 3 с Acmp

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


Дано натуральное число N. Над ним можно произвести следующий набор операций:

вычитать единицу;
делить на три, если число кратно трем;
делить на два, если число четное.
После выполнения одной из операций к полученному результату также можно применить указанные операции, и делается это до тех пор, пока результат не окажется равным 1.


Код

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> a;
    a.push_back(0);
    a.push_back(1);
    a.push_back(1);
    for(int i = 3; i < n; ++i){
        int s = i + 1;
        if(s % 2 == 0 && s % 3 == 0){
            a.push_back((min(a[i - 1],min(a[i/2],a[i/3]))) + 1);
            //cout << a[i] << " ";
        }
        else
            if(s % 2 == 0){
                a.push_back((min(a[i - 1],a[i/2])) + 1);
              //  cout << a[i] << " ";
            }
        else
            if(s % 3 == 0)
                a.push_back((min(a[i - 1],a[i/3])) + 1);
            //cout << a[i] << " ";
        else
            a.push_back(a[i - 1] + 1);
    }
    cout << a[n - 1];
    return 0;
}

         

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




Комментарии

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