Excellent Numbers (excellent)

Aiuto
1

Ciao, vorrei risolvere questo problema, e vedendo il testo pensavo di implementare il problema con combinazioni o permutazioni, ma chiedendo anche a chat gpt mi dice di poterla risolvere anche con il greedy search, solo che io non so come implementarlo e stessa cosa come funzionano le combinazioni e le permutazioni.

2

Immagina di avere un numero composto da N cifre tutte uguali a 1. Quanti 1 devi cambiare in 5 perché il numero risulti divisibile per 3?

3

Mmh, non saprei, forse fino a quando la somma delle cifre non é divisibile per 3?

4

risolto, questo é il codice, praticamente creo un vettore e carico 1 in base a N e pian piano sommo, poi faccio un for e controllo se la somma é divisibile altrimenti tolgo alla somma 1 in base all’indice e metto 5, poi lo aggiungo alla somma.
uso anche un valore boolean isDivisible, cosí se la somma é divisibile per tre lo imposto a true e mi fermo, e alla fine controllo che se é divisibile, stampo i numeri nel vettore altrimenti stampo -1

#include <bits/stdc++.h>
using namespace std;

void run_case(int n){
    vector<int> a(n);
    int sum = 0;
    bool isDivisible = false;

    for(int i=0; i<n; i++){
        a[i] = 1;
        sum+=a[i];
    }

    for(int i=0; i<n; i++){
        if(sum%3 == 0){
            isDivisible = true;
            break;
        } else {
            sum -= a[i];
            a[i] = 5;
            sum += a[i];
        }
    }

    if(isDivisible){
        for(int i=0; i<n; i++){
            cout << a[i];
        }
    } else {
        cout << -1 << endl;
    }
}

int main() {
    int n;
    cin >> n;

    run_case(n);
}
5

ah, il vettore puó essere inizializzato cosí togliendo il primo for:
vector a(n, 1) e la somma é n