h2. Date de ieșire
Pe prima linie a fișierului de ieșire $tema.out$:
* se scrie un număr natural nenul, reprezentând lungimea maximă determinată pentru prima cerință, dacă $*C* = 1$;
* se scriu două numere naturale nenule, separate printr-un spațiu, reprezentând, în ordine, pozițiile primului, respectiv ultimului element din secvența de lungime maximă, determinată conform celei de a doua cerințe, dacă $*C* = 2$.
* se scrie un număr natural nenul, reprezentând lungimea maximă determinată pentru prima cerință, dacă $[*C*] = 1$;
* se scriu două numere naturale nenule, separate printr-un spațiu, reprezentând, în ordine, pozițiile primului, respectiv ultimului element din secvența de lungime maximă, determinată conform celei de a doua cerințe, dacă $[*C*] = 2$.
h2. Restricții și precizări
* $2 ≤ *N* ≤ 100 000$;
* $1 ≤ *K* ≤ 10[^18^]$; *Numărul $K$ nu are niciun rol pentru cerința $2$*;
* $1 ≤ *A[~i~]* ≤ 1$*C* = 1 000 000$, pentru fiecare $*i*$: $1 ≤ *i* ≤ *N*$;
* $1 ≤ *A[~i~]* ≤ 1 000 000$ pentru fiecare $*i*$: $1 ≤ *i* ≤ *N*$;
* *În cazul ambelor cerințe, există o secvență soluție ce are lungimea cel puțin egală cu $2$*;
* Există cel puțin un element diferit de $1$ în șirul $*A*$.
table{width: auto;}.
|_. # |_. Punctaj |_. Restricții |
| 1
| 10
| _*C*_ = 1 și _*N*_ = 2
|
| 2
| 25
| _*C*_ = 1 și _*N*_ ≤ 4000
|
| 3
| 15
| _*C*_ = 1 și 5000 < _*N*_
|
| 4
| 10
| _*C*_ = 2 și _*N*_ = 2
|
| 5
| 25
| _*C*_ = 2 și _*N*_ ≤ 4000
|
| 6
| 15
| _*C*_ = 2 și 5000 < _*N*_
|
h2. Exemple
table(example).
| 1 10 45
10 2 3 1 4 5 8 2 6 3
|5
| $*C*=1$, $*N*=10$ și $*K*=45$. Secvența $(2, 3, 1, 4, 5)=(A[~2~], A[~3~], A[~4~], A[~5~], A[~6~])$
are costul egal cu $(2 + 3 + 5) * 4 = 40$. Nu există, în șirul $A$, o secvență de lungime
mai mare și de cost mai mic sau egal decât $45$.
| [*C*] = 1, [*N*] = 10 și [*K*] = 45. Secvența (2, 3, 1, 4, 5) = (A[~2~], A[~3~], A[~4~], A[~5~], A[~6~])
are costul egal cu (2 + 3 + 5) * 4 = 40. Nu există, în șirul [*A*], o secvență de lungime
mai mare și de cost mai mic sau egal decât 45.
|
|2 10 20
1 2 32 4 42 49 7 21 1 63
|5 8
| $C=2$, $N=10$ și $K=20$. După modificări, șirul $A$ devine: $(1,2,4,4,14,49,7,21,1,21)$.
| [*C*] = 2, [*N*] = 10 și [*K*] = 20. După modificări, șirul A devine: (1,2,4,4,14,49,7,21,1,21).
Există două secvențe de lungime maximă pentru care cel mai mare divizor comun („c.m.m.d.c.”)
al numerelor din care sunt formate este diferit de $1$: $(2,4,4,14)$ (poziția în șir a primului
element este $2$, iar c.m.m.d.c.-ul elementelor sale este $2$), respectiv $(14, 49, 7, 21)$
(poziția în șir a primului element este $5$, iar c.m.m.d.c.-ul elementelor sale este $7$).
al numerelor din care sunt formate este diferit de 1: (2,4,4,14) (poziția în șir a primului
element este 2, iar c.m.m.d.c.-ul elementelor sale este 2), respectiv (14, 49, 7, 21)
(poziția în șir a primului element este 5, iar c.m.m.d.c.-ul elementelor sale este 7).
Pentru că sunt două secvențe de lungime maximă, în enunț este precizat că se va alege cea
pentru care poziția primului său element este maximă, adică, în acest caz,
$(14,49,7,21)=(A[ 5 ], A[ 6 ], A[ 7 ], A[ 8 ])$.
(14,49,7,21)=(A[~5~], A[~6~], A[~7~], A[~8~]).
|
== include(page="template/taskfooter" task_id="tema") ==
