simulare OJI 2023 clasa 8 | tema

This was the problem page during the contest. Access the current page here.
Time limit: 0.3s Memory limit: 128MB Input: tema.in Output: tema.out

Macarie a primit ca temă la Informatică următorul enunț de problemă: „Se consideră un șir AA cu NN numere naturale nenule, numerotate începând de la 11 până la NN. 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 11 și de el însuși, iar un număr este prim dacă are exact doi divizori naturali distincți, pe 11 și pe el însuși.”.

Știm că numărul 11 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 00. De asemenea, suma valorilor prime dintr-o secvență care conține un singur număr prim XX este egală cu XX; în mod similar, suma valorilor compuse dintr-o secvență care conține un singur număr compus YY este egală cu YY.

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 AA pentru care costul ei este mai mic sau egal decât un număr natural nenul KK.
  2. Presupunem că fiecare număr compus din șirul AA 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 11. 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 CC, NN și KK, în această ordine, separate prin câte un spațiu, unde CC este numărul cerinței care trebuie rezolvată (1 sau 2), iar NN și KK au semnificația din enunț. Pe a doua linie se află NN numere naturale nenule, separate între ele prin câte un spațiu, reprezentând, în ordine, termenii șirului AA.

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=1C=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=2C = 2.

Restricții și precizări

  • 2N100 0002\leq N \leq 100 \ 000;
  • 1K10181\leq K \leq 10^{18}; Numărul KK nu are niciun rol pentru cerința 22;
  • 1Ai1 000 0001\leq A_i \leq 1 \ 000 \ 000, pentru fiecare ii: 1iN1 \leq i \leq N;
  • În cazul ambelor cerințe, există o secvență soluție ce are lungimea cel puțin egală cu 22;
  • Există cel puțin un element diferit de 11 în șirul AA.
  • Pentru 1010 puncte, C=1C = 1 și N=2N = 2;
  • Pentru 2525 de puncte, C=1C = 1 și N4 000N \leq 4 \ 000;
  • Pentru 1515 puncte, C=1C = 1 și 5 000<N5 \ 000 < N;
  • Pentru 1010 puncte, C=2C = 2 și N=2N = 2;
  • Pentru 2525 de puncte, C=2C = 2 și N4 000N \leq 4 \ 000;
  • Pentru 1515 puncte, C=2C = 2 și 5 000<N5 \ 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=1C=1, N=10N=10 și K=45K=45. Secvența (2,3,1,4,5)=(A2,A3,A4,A5,A6)(2, 3, 1, 4, 5)=(A_2, A_3, A_4, A_5, A_6) are costul egal cu (2+3+5)×4=40(2 + 3 + 5) \times 4 = 40. Nu există, în șirul AA, o secvență de lungime mai mare și de cost mai mic sau egal decât 4545.

Exemplul 2

tema.in

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

tema.out

5 8

Explicație

C=2C=2, N=10N=10 și K=20K=20. După modificări, șirul AA devine: (1,2,4,4,14,49,7,21,1,21)(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 11: (2,4,4,14)(2,4,4,14) (poziția în șir a primului element este 22, iar c.m.m.d.c.-ul elementelor sale este 22), respectiv (14,49,7,21)(14, 49, 7, 21) (poziția în șir a primului element este 55, iar c.m.m.d.c.-ul elementelor sale este 77). 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)=(A5,A6,A7,A8)(14,49,7,21)=(A_5, A_6, A_7, A_8).

Log in or sign up to be able to send submissions!