Editing 3778 - Pian

== Enunt ==
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
<br>

== 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
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
from math import gcd

def main():
    C = int(input())
    N = int(input())
    times = list(map(int, input().split()))

    if C == 1:
        # Cerința 1
        total_time = 0
        for i in range(N):
            total_time += gcd(times[i], times[i + 1]) if i < N - 1 else times[i]
        print(total_time)
    elif C == 2:
        # Cerința 2
        operations = []
        for i in range(N):
            if gcd(times[i], times[i + 1]) < times[i] or gcd(times[i], times[i + 1]) < times[i + 1]:
                operations.append(i + 1)
        print(len(operations))
        print(*operations)

if __name__ == "__main__":
    main()

</syntaxhighlight>