simulare OJI 2023 clasa 8 | tema

Macarie a primit ca temă la Informatică următorul enunț de problemă: „Se consideră un șir $A$ cu $N$ numere naturale nenule, numerotate începând de la $1$ până la $N$. Numim secvență o succesiune de termeni situați pe poziții consecutive în șir, iar lungimea secvenței o reprezintă numărul de termeni din care este formată. Costul unei secvențe este egal cu produsul dintre suma valorilor prime din secvență și suma celor compuse. Numărul compus este un număr care are cel puțin un divizor natural diferit de $1$ și de el însuși, iar un număr este prim dacă are exact doi divizori naturali distincți, pe $1$ și pe el însuși.”.

Știm că numărul $1$ nu este nici număr prim, nici compus, deci nu influențează costul niciunei secvențe în care se găsește. Evident, costul unei secvențe care nu conține niciun număr prim sau al unei secvențe care nu conține niciun număr compus este egal cu $0$. De asemenea, suma valorilor prime dintr-o secvență care conține un singur număr prim $X$ este egală cu $X$; în mod similar, suma valorilor compuse dintr-o secvență care conține un singur număr compus $Y$ este egală cu $Y$.

Cerințe

Ajutați-l pe Macarie să rezolve următoarele două cerințe ale temei:

1. Să se determine lungimea maximă a unei secvențe din șirul $A$ pentru care costul ei este mai mic sau egal decât un număr natural nenul $K$.
2. Presupunem că fiecare număr compus din șirul $A$ este înlocuit cu produsul dintre cel mai mic factor prim al său și cel mai mare factor prim al său. Să se determine secvența de lungime maximă din șirul nou obținut, pentru care cel mai mare divizor comun al numerelor din care este formată este diferit de $1$. Se vor afișa pozițiile primului și ultimului element din secvență. Dacă sunt mai multe astfel de secvențe de lungime maximă, se va afișa cea pentru care poziția primului său element este maximă.

Date de intrare

Pe prima linie a fișierului de intrare tema.in se află trei numere naturale nenule $C$, $N$ și $K$, în această ordine, separate prin câte un spațiu, unde $C$ este numărul cerinței care trebuie rezolvată (1 sau 2), iar $N$ și $K$ au semnificația din enunț. Pe a doua linie se află $N$ numere naturale nenule, separate între ele prin câte un spațiu, reprezentând, în ordine, termenii șirului $A$.

Date de ieșire

Pe prima linie a fișierului de ieșire tema.out:

1. se scrie un număr natural nenul, reprezentând lungimea maximă determinată pentru prima cerință, dacă $C=1$;
2. 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$.

Restricții și precizări

• $2\leq N \leq 100 \ 000$;
• $1\leq K \leq 10^{18}$; Numărul $K$ nu are niciun rol pentru cerința $2$;
• $1\leq A_i \leq 1 \ 000 \ 000$, pentru fiecare $i$: $1 \leq i \leq 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$.
• Pentru $10$ puncte, $C = 1$ și $N = 2$;
• Pentru $25$ de puncte, $C = 1$ și $N \leq 4 \ 000$;
• Pentru $15$ puncte, $C = 1$ și $5 \ 000 < N$;
• Pentru $10$ puncte, $C = 2$ și $N = 2$;
• Pentru $25$ de puncte, $C = 2$ și $N \leq 4 \ 000$;
• Pentru $15$ puncte, $C = 2$ și $5 \ 000 < N$.

Exemplul 1

tema.in

1 10 45
10 2 3 1 4 5 8 2 6 3

tema.out

5

Explicație

$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) \times 4 = 40$. Nu există, în șirul $A$, o secvență de lungime mai mare și de cost mai mic sau egal decât $45$.

Exemplul 2

tema.in

2 10 20
1 2 32 4 42 49 7 21 1 63

tema.out

5 8

Explicație

$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$). 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)$.