# PBinfo #3778 – Pian – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Ian este un copil pasionat de muzică, așa că părinții săi i-au cumpărat de ziua lui un pian. Pianul lui Ian este mai special, acesta are N clape. Întrucât pianul nu este nou, clapele se mișcă mai greu, astfel apăsarea celei de-a i-a clape durează t[i] secunde.

Deoarece Ian este foarte nerăbdător, s-a hotarât să repare clapele pianului pentru ca apăsarea unei clape să fie cât mai rapidă. Acesta poate selecta două clape vecine i și i+1 ce necesită t[i], respectiv t[i+1] secunde pentru a fi apăsate și le lustruiește. În urma lustruirii, cele două clape vor necesita doar cmmdc(t[i],t[i+1]) secunde pentru apăsarea fiecăreia. Practic, o operație va efectua următoarea transformare asupra clapelor: t[i] = t[i + 1] = cmmdc(t[i], t[i+1]).

Ian consideră ca pianul este lustruit dacă timpul de apăsare al fiecărei clape este minim posibil.

Cerința

Cerința 1: Ian vrea să facă un riff (adică să apese fiecare clapă o singură dată) și vrea să știe care ar fi durata de timp a unui riff pe pianul lustruit.
Cerința 2: Pentru că Ian nu are timp de pierdut cu lustruitul, acesta vrea o listă de instrucțiuni de lungime minimă asfel încât dupa efectuarea instrucțiunilor pianul să fie lustruit.

Date de intrare
Fișierul de intrare pian.in conține pe prima linie numărul C ce reprezintă cerința care trebuie rezolvată. Pe următoarea linie se află N, numărul de clape ale pianului. Pe următoarea linie se vor afla N numere separate prin câte un spațiu, al i-lea număr reprezentând durata inițială t[i] necesară pentru apăsarea clapei cu indicele i.

Date de ieșire
În fișierul pian.out se vor afișa în funcție de cerință următoarele:


Dacă C = 1, atunci fișierul va conține o singură linie cu un singur număr S, ce reprezintă răspunsul pentru prima cerință.
Dacă C = 2, atunci fișierul va conține pe prima linie un număr M care reprezintă numarul minim de operații pe care Ian trebuie să le facă, iar pe următoarea linie M numere separate prin câte un spatiu, al i-lea număr x[i], reprezentând faptul că a i-a operație de lustruire a clapelor se va face între clapele cu indicii x[i] și x[i]+1.

Restricții și precizări

C ∈ {1, 2}
1 ≤ N ≤ 100.000
1 ≤ v[i] ≤ 1.000.000, pentru orice i ∈ {1, 2, ..., N}
1 ≤ x[j] < N, pentru orice j ∈ {1, 2, ..., M}
Daca pentru cerința 2 există mai multe soluții cu număr minim de operații se acceptă oricare.

Exemplul 1:
pian.in

1
5
2 4 6 8 10
pian.out

10
Explicație
Ian poate lustrui pianul în doar 2 instrucțiuni în următorul mod:


Aplicăm operația pe clapele 2 și 3. Obținem șirul 2 2 2 8 10
Aplicăm operația pe clapele 4 și 5. Obținem șirul 2 2 2 2 2

În final se va obține șirul de clape: 2 2 2 2 2. Astfel, durata unui riff va fi de 10 secunde.

Exemplul 2:
pian.in

2
5
2 4 6 8 10
pian.out

2
2 4

## Cod sursă C++

```cpp
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX = 100000;
const int VMAX = 1000000;
int v[NMAX + 5], f[VMAX + 5], n;
vector <int> d[NMAX + 5];
vector <int> sol;
int gcd(int a, int b) {
    int r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
void solve_fact(int poz, int x) {
    if (x % 2 == 0) {
        d[poz].push_back(2);
        while (x % 2 == 0) {
            x /= 2;
        }
    }
    for (int i = 3; i * i <= x; ++i) {
        if (x % i == 0) {
            d[poz].push_back(i);
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x != 1) {
        d[poz].push_back(x);
    }
}
void print_sol() {
    printf("%d\n", sol.size());
    for (int i = 0; i < sol.size(); ++i) {
        printf("%d ", sol[i]);
    }
    printf("\n");
}
void solve_part() {
    int first = -1, last = -1;
    for (int i = 1; i < n; ++i) {
        if (v[i] == 1) {
            if (first == -1) {
                first = i;
            }
            last = i;
        }
        else if (v[i + 1] != 1 && gcd(v[i], v[i + 1]) == 1) {
            sol.push_back(i);
            v[i] = v[i + 1] = 1;
            if (first == -1) {
                first = i;
            }
            last = i + 1;
            ++i; // fortez trecerea la pasul urmator
        }
    }
    for (int i = first - 1; i > 0; --i) {
        sol.push_back(i);
        v[i] = 1;
    }
    for (int i = last + 1; i <= n; ++i) {
        sol.push_back(i - 1);
        v[i] = 1;
    }
    for (int i = 1; i < n; ++i) {
        if (v[i] != 1) {
            sol.push_back(i - 1);
            v[i] = 1;
        }
    }
    print_sol();
}
int valid(int len) {
    memset(f, 0, sizeof(f));
    int cnt = 0;
    for (int i = 1; i < len; ++i) {
        for (int j = 0; j < d[i].size(); ++j) {
            ++f[d[i][j]];
            if (f[d[i][j]] == len) {
                ++cnt;
            }
        }
    }
    for (int i = len; i <= n; ++i) {
        for (int j = 0; j < d[i].size(); ++j) {
            ++f[d[i][j]];
            if (f[d[i][j]] == len) {
                ++cnt;
            }
        }
        if (cnt == 0) {
            return i - len + 1;
        }
        for (int j = 0; j < d[i - len + 1].size(); ++j) {
            --f[d[i - len + 1][j]];
            if (f[d[i - len + 1][j]] == len - 1) {
                --cnt;
            }
        }
    }
    return -1;
}
int main() {
    freopen("pian.in", "r", stdin);
    freopen("pian.out", "w", stdout);
    int t, ans;
    scanf("%d %d\n", &t, &n);
    scanf("%d", &v[1]);
    ans = v[1];
    for (int i = 2; i <= n; ++i) {
        scanf("%d", &v[i]);
        ans = gcd(ans, v[i]);
    }
    if (t == 1) {
        printf("%lld\n", 1LL * n * ans);
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        v[i] /= ans;
        solve_fact(i, v[i]);
    }
    for (int i = 1; i < n; ++i) {
        if (gcd(v[i], v[i + 1]) == 1) {
            solve_part();
            return 0;
        }
    }
    int st, dr, mij, last, pos_l, pos_r, rez;
    st = 3; dr = n;
    while (st <= dr) {
        mij = (st + dr) / 2;
        rez = valid(mij); /// Cautam o solutie pt lungimea mij
        if (rez != -1) {
            pos_l = rez;
            pos_r = rez + mij - 1;
            dr = mij - 1;
        } else {
            st = mij + 1;
        }
    }
    for (int i = pos_l; i < pos_r; ++i) {
        sol.push_back(i);
    }
    v[pos_r - 1] = 1;
    v[pos_r] = 1;
    for (int i = pos_r + 1; i <= n; ++i) {
        sol.push_back(i - 1);
        v[i] = 1;
    }
    for (int i = pos_r - 2; i > 0; --i) {
        sol.push_back(i);
        v[i] = 1;
    }
    print_sol();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3778)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3778/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3778/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)