Articole

sussy bakka

xx

place shaorma da fara ceapa

Sunt pe BOABA└■

buna amicii mei

?

Cerința
Un filipinez cultivat are X cărți pe care dorește să le vândă. Pentru aceasta, el merge pe strada Plopilor fără soț unde se află n case. Acesta știe că în fiecare dintre cele n case se vor vinde un număr de cărți.

Filipinezul cultivat începe să vândă de la o casă a și trece pe la toate casele succesive până când nu mai are cărți de vândut.

Determinați intervalul minim lexicografic [a, b] între care filipinezul să-și vândă cărțile, astfel încât să vândă un număr maxim de carți, mai mic sau egal cu X

Date de intrare
Fișierul de intrare carti2.in conține pe prima linie numerele n și X, iar pe a doua linie n numere naturale separate prin spații reprezntând numărul de cărți pe care le va vinde la fiecare casă.

Date de ieșire
Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.

Restricții și precizări
1 ≤ n ≤ 100.000
1 ≤ X ≤ 1.000.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu
carti2.in

5 9
1 2 3 4 5
carti2.out

2 4
Explicație
Intervalul [2, 4], deoarece 2 + 3 + 4 = 9

Mama lui Catalin este o femeie minunata.

#include <iostream>
using namespace std;

int main ()
{ int a,s; cin>>a; s=a*a*2+9; cout<<s; return 0;
}

PIRNOG THEODOR IOAN
Colegiul Național “B. P. Hasdeu”, 10A

Determinarea primalității unui număr reprezintă o sarcină de lucru pe care o putem întâlni atât la probleme simple, cât și la probleme cu un grad ridicat de dificultate, cum ar fi cele de olimpiadă. Este foarte important să observăm resursele disponibile atunci când rezolvăm o astfel de problemă. În cazul în care avem destulă memorie la dispoziție, putem utiliza ciurul lui Eratostene, fie el sub forma unui vector bool, fie utilizând <bitset>. Există însă cazuri în care memoria nu ne permite să folosim astfel de structuri, prin urmare, vom fi nevoiți să ne gândim la o altă metodă pentru determinarea primalității unui număr. Probabil că, mulți vor tinde să utilizeze următorul algoritm: (Vezi poza I)

Este un algoritm simplu, ușor de înțeles, dar care nu este foarte eficient. Avem nevoie de ceva mai bun.

• dacă p ∈ {0, 2, 4}, atunci x = 6k, 6k + 2 sau 6k + 4 <=> x = 2 * 3k, x = 2 * (3k + 1) sau x = 2 * (3k + 2) => x este divizibil cu 2 => x nu este prim. (1)

• dacă p ∈ {3}, atunci x = 6k + 3 <=> x = 3 * (2k + 1) => x este divizibil cu 3 => x nu este prim. (2)

Rămânem, deci, cu p = ± 1 => x = 6k ± 1, despre care dorim să aflăm dacă este prim. Haideți să aruncăm o privire asupra perechilor de forma (6k – 1, 6k + 1), k ≥ 1: (5, 7), (11, 13), (17, 19), (23, 25), … Pentru aceste numere, vom încerca să găsim divizori pentru a verifica dacă sunt numere prime sau nu. Divizorii acestor numere vor fi tot de forma 6k ± 1, întrucât, dacă x ar fi divizibil cu un număr scris sub forma (1), atunci ar fi multiplu de 2, deci nu poate fi prim (analog pentru multiplii de 3, conform a ceea ce am zis la (2)). Observăm că, modulul diferenței dintre cei 2 termeni ai unei perechi (6k – 1, 6k + 1), k ≥ 1, este mereu 2, iar modulul diferenței dintre oricare 2 termeni aflați pe prima poziție în perechi consecutive va fi mereu 6, datorită 6k. De observat este că, numerele prime 2 și 3 nu pot fi scrise sub forma 6k – 1 sau 6k + 1, k ≥ 1, deci va trebui să ne ocupăm separat de ele. Acestea fiind spuse, să aruncăm o privire asupra noului test de primalitate: (Vezi poza II)

O problemă care necesită un astfel de algoritm este #hard_prime , în care soluția se încadrează în timp și memorie folosind acest algoritm. Spor la lucru!