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

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

Rezolvare

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()