Page 118 - MATINF Nr.2

˘
118 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Date de intrare

Din fis , ierul secventa.in se citesc: num˘arul natural N de pe prima linie s , i cele N numere
din s , irul p, pe a doua linie, separate prin cˆate un spat , iu.
Date de ies , ire

ˆ
In fis , ierul secventa.out se vor scrie num˘arele A s , i B separate printr-un spat , iu.
Restrict , ii s , i preciz˘ari

• 1 < N ≤ 100000, num˘ar natural
• Termenii s , irului sunt numere naturale cu maxim 9 cifre

• Secvent , a este un o port , iune din p cu indici consecutivi

Exemplu

secventa.in secventa.out Explicat , ie
10 3 2 Secvent , ele de numere prime sunt:
2 5 11 8 7 4 3 19 17 4 2 5 11, 7, 3 19 17.
Secvent , ele 2 5 11, 3 19 17 sunt
de lungime maxim˘a.

Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘a disponibil˘a 2 MB.

Violeta B˘alan, Slatina

I 19 (bireactive). Cˆand a ajuns acas˘a, Gigel a g˘asit pe o foaie n numere (C 1 , C 2 , . . . , C n ), fiecare
reprezentˆand o substant , ˘a chimic˘a. El s , tie de la chimie c˘a dou˘a substant , e chimice A s , i B al˘aturate
react , ioneaz˘a dac˘a ˆındeplinesc urm˘atoarea condit , ie 0 ≤ |A − B| ≤ 10 (|a| = modul de a) s , i
rezult˘a o singur˘a substant , ˘a, egal˘a cu:

1. A + B, dac˘a 0 ≤ |A − B| ≤ 5;
2. 2(A + B), dac˘a 5 < |A − B| ≤ 10.

El a observat c˘a unele substant , e pot react , iona s , i cu substant , a din stˆanga s , i cu substant , a
din dreapta s , i le-a numit ,,bi-reactive”.
Cerint , ˘a

1. Cˆate substant , e bi-reactive sunt?
2. Care este substant , a care apare de cele mai multe ori? (dac˘a dou˘a substant , e apar de un
num˘ar maxim de ori, se va afis , a prima g˘asit˘a).
3. Care ar fi num˘arul maxim de substant , e bi-reactive dac˘a s-ar elimina o substant , ˘a oarecare
de pe foaie?
4. Determinat , i substant , ele rezultate dup˘a ce toate substant , ele au react , ionat, astfel ˆıncˆat:

• substant , a react , ioneaz˘a doar cu cea din dreapta ei;
• dup˘a fiecare react , ie se caut˘a de la stˆanga la dreapta prima substant , ˘a care poate
react , iona;
• procesul se repet˘a pˆan˘a cˆand nu mai exist˘a dou˘a substant , e vecine care pot react , iona.