Fişierul intrare/ieşire:optime.in, optime.outSursăONI 2019 clasa a 6-a
AutorVioleta GreceaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.6 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Optime (clasa a 6-a)

Maria iubeşte numerele prime. Ea scrie pe o foaie de hârtie, în ordine strict crescătoare, un şir format din numerele prime care au cel puţin 2 cifre. Apoi, din numerele care conţin mai mult de 2 cifre taie cifrele din stânga, astfel încât să rămână exact 2 cifre. Dacă după tăierea cifrelor numărul obţinut nu este cuprins între 10 şi 99, numărul este eliminat din şir. De exemplu, numărul prim 101, care are 3 cifre, nu va fi scris, deoarece i se taie cifra din stânga, rezultând numărul 01, adică 1, care nu are exact 2 cifre, deci după tăiere va fi eliminat din şir.

Maria umple un tabel cu 2*k linii şi k coloane, astfel încât, parcurgându-l pe linii, de sus în jos şi fiecare linie de la stânga la dreapta, se obţin numerele din şir. Studiind numerele din tabel, constată că printre acestea se află şi numere care nu sunt prime.

De exemplu, pentru k=4, tabelul arată ca în imaginea din dreapta.

Cerinţe

Cunoscând un număr natural k nenul şi un număr natural x, ajutaţi-o pe Maria:

  1. Să determine suma numerelor din tabel care nu sunt prime. Dacă nu există numere care nu sunt prime, suma are valoarea 0.
  2. Să aleagă x coloane consecutive din tabel, astfel încât acestea să conţină, în total, un număr maxim de numere prime. Dacă există mai multe posibilităţi, se va alege secvenţa de coloane consecutive care are o valoare cât mai mare a coloanei de început din secvenţă. Să se determine numărul primei coloane din secvenţa aleasă, precum şi numărul total de numere prime din secvenţă.

Date de intrare

Fişierul de intrare optime.in conţine pe prima linie o cifră c care poate să fie doar 1 sau 2. Dacă c=1, pe linia a doua se găseşte un număr natural nenul k cu semnificaţia din enunţ. Dacă c=2, pe linia a doua se află două numere naturale nenule, k şi x, cu semnificaţia din enunţ.

Date de ieşire

Dacă valoarea lui c este 1, atunci se va rezolva numai punctul 1 din cerinţă. În acest caz, fişierul de ieşire optime.out va conţine pe prima linie un număr natural reprezentând valoarea sumei determinate.

Dacă valoarea lui c este 2, se va rezolva numai punctul 2 din cerinţă. În acest caz, fişierul de ieşire optime.out va conţine pe prima linie un număr natural reprezentând numărul de ordine al primei coloane conform cerinţei, iar pe linia a doua numărul de numere prime, conform cerinţei.

Restricţii

  • 1 ≤ xk ≤ 200
  • Pentru rezolvarea primei cerinţe se acordă 30% din punctaj, iar pentru cerinţa a doua se acordă 70% din punctaj.

Exemplu

optime.inoptime.outExplicaţie
1
4
286
Pentru k=4, în tabel se află următoarele numere neprime: 27, 39, 49, 51, 57, 63,
suma lor fiind 286.
2
4 3
2
19
Coloana 1 conţine 7 numere prime, coloana 2 conţine 6 numere prime,
coloana 3 conţine 6 numere prime, iar coloana 4 conţine 7 numere prime.
Putem alege fie coloanele 1,2,3, fie coloanele 2,3,4, ambele variante
conţinând câte 19 numere prime. Se alege a doua variantă, pentru că are
valoarea mai mare a coloanei de început a secvenţei.
Trebuie sa te autentifici pentru a trimite solutii. Click aici