Lista de probleme 3

Un număr natural nenul m se numește norocos dacă pătratul lui se poate scrie ca sumă de m numere naturale consecutive. Un număr natural m se numește k-norocos, dacă este egal cu produsul a exact k numere prime distincte. Observați că între cele două proprietăți definite nu există nicio legătură.

Dându-se k și N numere naturale, scrieți un program care să determine:

a) Cel mai mic și cel mai mare număr norocos dintre cele N numere citite
b) Câte numere k-norocoase sunt în șirul de N numere citite

Fie un şir a[1], a[2], …, a[n] de numere naturale, unde n este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.

Cerințe:

1. Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
2. Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial.

Pentru un număr natural N se consideră șirul a=(1,2,3...,N), deci a[i]=i pentru orice i, 1≤i≤N.

Asupra acestui șir se pot aplica operații de două tipuri:

a) la operația de tipul 1 se specifică două valori i și j, cu 1≤i≤j≤N. Efectul acestei operații asupra șirului este de oglindire a secvenței din șir care începe cu elementul de pe poziția i și se termină cu cel de pe poziția j. De exemplu, dacă în șirul a=(1,2,3,4,5,6,7) se aplică operația 3 6, atunci șirul devine a=(1,2,6,5,4,3,7). Iar în șirul a=(1,4,3,2,5,6,7), dacă se aplică operația 4 6, atunci a=(1,4,3,6,5,2,7).
b) Operația de tipul 2 conține un indice i, 1≤i≤N, și cere să afișăm valoarea elementului care se află în acel moment pe poziția i în șir.

Se consideră M astfel de operații într-o ordine dată.

Scrieți un program care să determine și să afișeze rezultatul pentru fiecare operație de tipul 2.