Lista de probleme 3

Pe o linie orizontală se găsesc n greieri. Ei încep să stea „capră” într-o ordine prestabilită începând cu ultimul, pe rând, până la primul. Toţi greierii care îl preced pe cel care stă „capră” sar peste acesta, în ordine.

De exemplu pentru n=4, mai întâi stă „capră” greierul 4 și peste el sar, în ordine, 3, 2 și 1. Apoi stă „capră” greierul 3 și sar peste el, în ordine, 2, 1 și 4. Apoi stă „capră” greierul 2 și peste el sar, în ordine, 1, 3 și 4. Apoi stă „capră” greierul 1 și sar peste el, în ordine, 4 , 3 și 2, și se revine la ordinea inițială.

Scrieți un program care citește numerele naturale n și m și determină:

a) De câte sărituri este nevoie pentru a se ajunge la ordinea inițială?
b) Cum vor fi așezați greierii după m sărituri?

Gigel, mare amator de probleme de matematică şi informatică, a observat că unele numere prime au o proprietate interesantă: orice cifră ar elimina dintr-un astfel de număr, numărul obţinut este tot număr prim. A numit astfel de numere numere extraprime. De exemplu, numărul 317 este un număr extraprim: el este număr prim şi, în plus, dacă eliminăm cifra 3, obţinem 17, care este prim; dacă eliminăm 1, obţinem 37, care este prim; dacă eliminăm 7, obţinem 31, care este şi el număr prim.

Spunem că x este între a şi b dacă x≥a şi x≤b. Fiind date două valori naturale a şi b, să se determine câte numere extraprime există între a şi b, precum şi cel mai mic şi cel mai mare număr extraprim dintre a şi b.

La ONIGIM2013 participă N elevi de clasa a V-a având ca id-uri, în ordine, numerele naturale de la 1 la N. Anul acesta organizatorii au afişat la clasa a V-a toate punctajele distincte obţinute de elevi, în ordine strict crescătoare p1, p2,…, pK, şi un şir de N valori a1, a2,…, aN, unde ai reprezintă numărul de elevi care au punctaje strict mai mici decât punctajul elevului având id-ul i (1≤i≤N).

Cunoscând numărul de elevi (N), numărul de punctaje distincte (K) obţinute de elevii de clasa a V-a, punctajele p1, p2,…, pK, în ordine strict crescătoare, şi valorile a1, a2,…, aN cu semnificaţia din enunţ, să se scrie un program care determină:

a) Punctajul obţinut de fiecare elev în ordinea crescătoare a id-urilor.
b) Numărul de distincţii acordate de organizatori. Numărul de distincţii este egal cu numărul de elevi care au obţinut cele mai mari trei punctaje distincte.
c) Numărul maxim de elevi care au obţinut acelaşi punctaj.