Fișierul intrare/ieșire	ciocolata.in, ciocolata.out	Sursă	OJI 2023 Clasa a 6-a
Autor	Daniel Popa | Vlad-Mihai Bogdan	Adăugată de	Mihai Tutu • mihai.tutu
Timp de execuție pe test	0.05 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Ciocolata (clasa a 6-a)

Irina și Mihaela sunt surori. Într-o zi, mama lor le aduce N tablete de ciocolată, numerotate de la 1 la N, pe care le așează, în această ordine, pe o poliță a unui raft. Pentru fiecare tabletă se cunoaște gramajul (numărul de grame pe care le cântărește). Cantitatea totală de ciocolată consumată de o fată este egală cu suma gramajelor tuturor tabletelor consumate de ea. Pentru a consuma ciocolată, fetele trebuie să respecte următoarele reguli:

• cantitatea totală de ciocolată consumată de Irina trebuie să fie mai mare sau egală cu cantitatea totală de ciocolată consumată de sora sa;
• diferența dintre cantitatea totală de ciocolată consumată de Irina și cantitatea totală de ciocolată consumată de Mihaela trebuie să fie cât mai mică;
• fiecare fată trebuie să consume cel puțin o tabletă de ciocolată;
• fiecare fată consumă tablete de ciocolată de pe raft: Irina începe de la cea numerotată cu 1 și continuă, în ordine, de la stânga la dreapta, iar Mihaela începe cu cea numerotată cu N și continuă, în ordine, de la dreapta la stânga;
• fiecare fată poate întrerupe oricând consumul tabletelor de ciocolată, iar cele rămase fie sunt abandonate pe raft, fie sunt consumate de fata cealaltă, dacă ajunge la ele;
• fiecare tabletă de ciocolată fie este consumată complet de una dintre fete, fie rămăne pe raft, dar fetele NU pot sări peste nicio tabletă de ciocolată.

Cerințe

Determinați și afișați:

1. cel mai des întâlnit gramaj în șirul de tablete așezate inițial pe poliță, iar dacă sunt mai multe gramaje care apar de un număr maxim de ori, se alege cel mai mic dintre acestea;
2. diferența minimă dintre cantitatea totală de ciocolată consumată de Irina și cantitatea totală de ciocolată consumată de Mihaela.

Date de intrare

Pe prima linie din fișierul ciocolata.in se găsește numărul C, reprezentând cerința ce trebuie rezolvată (1 sau 2), urmat de numărul N, cu semnificația din enunț, iar pe a doua linie N numere naturale, reprezentând gramajele celor N tablete de ciocolată, în ordinea numerotării lor. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire ciocolata.out se va afla un singur număr reprezentând gramajul determinat la cerința 1 (dacă C = 1), respectiv, diferența minimă determinată la cerința 2 (dacă C = 2).

Restricții

• C ∈ {1, 2}
• 1 ≤ N ≤ 100000
• gramajul fiecărei tablete este un număr natural nenul mai mic sau egal cu 10000
• se garantează că există întotdeauna soluție
• pentru C = 1 se acordă 30 puncte
• pentru C = 2 și N = 2 se acordă 5 puncte
• pentru C = 2 și 1 ≤ N ≤ 100 se acordă 10 puncte
• pentru C = 2 și 1 ≤ N ≤ 1000 se acordă 25 puncte
• pentru C = 2 și fără restricții suplimentare se acordă 30 puncte

Exemplu

Explicație

...