Fişierul intrare/ieşire:sir3.in, sir3.outSursăLot Bistrita 2009, Baraj 1
AutorMircea DimaAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.8 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sir3

Termopanes s-a plictisit de numerele mari dar nu şi-a pierdut entuziasmul pentru numere în general aşa că i-a cerut surorii sale o nouă provocare. El a primit un şir a de n numere naturale distincte două câte două şi un număr S.
Sora lui îi cere o subsecvenţă de lungime maximă care are următoarele proprietăţi (presupunem că subsecvenţa este ai, ai+1, ..., aj ):

  • ai + aj = S
  • dacă elementul k aparţine subsecvenţei atunci şi S - k aparţine subsecvenţei

Deoarece şir-ul poate fi foarte mare, Termopanes vă cere ajutorul.

Cerinta

Determinaţi o subsecvenţă de lungime maximă care să respecte proprietăţile din enunţ.

Date de intrare

Fişierul de intrare sir3.in va conţine pe prima linie numerele naturale n şi S, cu semnificaţiile din enunţ. Pe a 2-a linie se vor afla cele n numere naturale ale şirului separate prin spaţii.

Date de ieşire

Fişierul de ieşire sir3.out va conţine o singură linie cu 3 numere naturale separate prin spaţii: maxlen, pozfirst, pozlast reprezentând lungimea maximă a subsecvenţei, poziţia de început şi poziţia de sfârşit a subsecvenţei. În cazul în care există mai multe subsecvenţe de lungime maximă se va lua cea cu pozfirst minimă.

Restricţii

  • 1 ≤ n ≤ 200 000
  • 1 ≤ S ≤ 2.000.000.000
  • 0 ≤ ai ≤ 1.000.000.000
  • S este impar
  • Se garantează că există întotdeauna soluţie.

Exemplu

sir3.insir3.out
10 11
2 3 1 4 7 10 0 11 8 5
8 2 9

Explicaţie

2 3 1 4 7 10 0 11 8 5
3 + 8 = 11
1 + 10 = 11
4 + 7 = 11
0 + 11 = 11

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content