3778 - Pian
Enunt[edit | edit source]
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[edit | edit source]
- 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[edit | edit source]
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[edit | edit source]
Î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[edit | edit source]
- 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[edit | edit source]
- pian.in
1 5 2 4 6 8 10
- pian.out
10
Explicație[edit | edit source]
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[edit | edit source]
- pian.in
2 5 2 4 6 8 10
- pian.out
2 2 4
Rezolvare[edit | edit source]
<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>