Fişierul intrare/ieşire:peste.in, peste.outSursăONI 2017 clasa a 6-a
AutorCristina IordaicheAdăugată defrancuCristian Francu francu
Timp execuţie pe test1.2 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Pește (clasa a 6-a)

Ursul: Bună, cumătră! Da cât peşte ai? Dă-mi şi mie, că tare mi-i poftă!
Vulpea: Ia mai pune-ţi pofta-n cui. Dacă vrei peşte, du-te şi-ţi înmoaie coada-n baltă şi vei avea ce să mănânci.
Ursul: Învaţă-mă, te rog, cumătră, că eu nu ştiu cum se prinde peştele.
Vulpea: Alei, cumetre! da' nu ştii că nevoia te-nvaţă ce nici nu gândeşti? Du-te deseară la baltă şi bagă-ţi coada-n apă. Stai pe loc, fără să te mişti, până spre ziuă. Între timp, ia foaia aceasta pe care am scris N numere naturale şi până dimineaţă trebuie să procedezi în felul următor:

  • elimini exact două cifre alăturate din fiecare număr scris pe foaie, astfel încât, celelalte cifre rămase după eliminare să formeze, de la stânga la dreapta, cel mai mare număr posibil (de exemplu, din numărul 77196, elimini cifrele 7 şi 1 pentru a obţine cel mai mare număr posibil 796).
  • toate cele N numere obţinute la pasul anterior, le lipeşti unul după altul, în ce ordine vrei tu. Uitându-te de la stânga la dreapta la cifrele numerelor lipite, observi că s-a format un nou număr X. Ai grijă cum procedezi, căci până dimineaţă, atâta peşte se va prinde de coada ta cât vei obţine tu valoarea lui X.

Ajutaţi-l pe urs să prindă cât mai mult peşte posibil.

Cerinţe

Scrieţi un program care citeşte N numere naturale şi determină:

  1. Cel mai mare număr de eliminări efectuate cu aceleaşi două cifre alăturate.
  2. Cel mai mare număr natural X determinat astfel încât ursul să prindă cât mai mult peşte.

Date de intrare

Fişierul de intrare peste.in conţine pe prima linie numărul natural P care poate avea valoarea 1 sau 2 şi reprezintă numărul cerinţei. Cea de-a doua linie conţine un număr natural N cu semnificaţia din enunţ, iar pe următoarele N linii, cele N numere scrise pe foaia ce i-a dat-o vulpea ursului, câte un număr natural pe fiecare linie a fişierului.

Date de ieşire

Fişierul de ieşire peste.out conţine pe prima linie un singur număr natural determinat conform cerinţei problemei.

Restricţii

  • 1 ≤ N ≤ 100, fiecare dintre cele N numere au cel puţin 3 şi cel mult 18 cifre;
  • pentru rezolvarea corectă a cerinţei 1 se acordă 40 de puncte, iar pentru rezolvarea corectă a cerinţei 2 se acordă 60 de puncte;
  • pentru cazul P=2, vor exista şi teste în valoare de 25 de puncte în care cele N numere naturale au valori mai mici decât 109 şi alte teste în valoare de 10 puncte în care cele N numere din fişierul de intrare sunt mai mici decât 109 şi au acelaşi număr de cifre.

Exemple

peste.inpeste.outExplicaţii
1
4
1791
802
777
77196
2
Se va rezolva cerinţa 1, iar în fişier sunt patru numere cu care vom proceda astfel:
din 1791 eliminăm cifrele 1 şi 7 iar numărul rezultat este 91
din 802 eliminăm cifrele 0 şi 2 iar numărul rezultat este 8
din 777 eliminăm cifrele 7 şi 7 iar numărul rezultat este 7
din 77196 eliminăm 7 şi 1 iar numărul rezultat este 796
S-au efectuat două eliminări cu aceleaşi două cifre alăturate: 1 şi 7.
2
4
1791
802
777
77196
9187967
Cu aceleaşi patru numere din exemplul precedent, vom rezolva cerinţa 2.
În urma eliminărilor efectuate s-au obţinut numerele:
91 8 7 796
Cel mai mare număr posibil, obţinut prin lipirea acestor numere este 9187967.
Trebuie sa te autentifici pentru a trimite solutii. Click aici