Lista de probleme 3

Vlad a inventat un nou joc. Jocul conţine N standuri aşezate în linie dreaptă. Fiecare stand are o etichetă pe care este scris un număr natural. Eticheta este considerată corectă dacă numărul îndeplineşte următoarele două condiţii:

• conține atât cifre pare, cât și cifre impare;
• începe cu cifrele impare așezate în ordine crescătoare, urmate de cifrele pare în ordine descrescătoare.

Pentru jocul său, Vlad a construit robotul reparator care ştie să verifice numere şi să le repare, dacă este necesar. Robotul reparator se deplasează în linie dreaptă și se opreşte pe rând la fiecare dintre cele N standuri. La fiecare stand, robotul verifică eticheta şi dacă nu este corectă, o „repară”. Pentru a repara eticheta, robotul aranjează cifrele impare în ordine crescătoare, apoi, în continuare, aranjează cifrele pare în ordine descrescătoare; dacă eticheta nu conţine nicio cifră impară, cea mai mare cifră pară o înlocuieşte cu 9 ; dacă eticheta nu conţine nicio cifră pară, cea mai mică cifră impară o înlocuieşte cu 0 . Deplasarea de la un stand la altul durează t secunde, verificarea etichetei unui stand durează v secunde, iar repararea acesteia durează r secunde. Cursa robotului se încheie după ce robotul a verificat toate cele N standuri şi a reparat etichetele incorecte.

Scrieţi un program care citeşte numărul N de standuri, timpul (ora h , minutul m , secunda s) când robotul ajunge la primul stand, timpii t , v și r cu semnificaţia din enunţ şi etichetele standurilor și care rezolvă următoarele cerințe:

1. calculează şi afişează timpul (ora, minutul şi secunda) când robotul a încheiat verificarea tuturor celor N standuri şi repararea etichetelor incorecte;
2. repară (unde este necesar) etichetele standurilor şi afişează etichetele celor N standuri la final.

Eu sunt fascinată de numerele prime. Consider că numerele prime sunt “scheletul” tuturor numerelor sau “atomii” acestora, pentru că orice număr natural mai mare decât 1 poate fi scris ca un produs de numere prime. Recent am aflat şi alte proprietăţi interesante legate de numerele prime, de exemplu:

1. În şirul Fibonacci există o infinitate de numere prime. Vă mai amintiţi şirul Fibonacci? 0, 1, 1, 2, 3, 5, 8, 13, ... Este şirul în care fiecare termen, exceptând primii doi, se obţine ca suma celor doi termeni care îl precedă.
2. Există numere naturale denumite „economice”. Un număr natural este economic dacă numărul de cifre necesare pentru scrierea sa este mai mare decât numărul de cifre necesare pentru scrierea descompunerii sale în factori primi (adică decât numărul de cifre necesare pentru scrierea factorilor primi şi a puterilor acestora). De exemplu 128 este economic pentru că 128 se scrie cu 3 cifre, iar descompunerea sa în factori primi se scrie cu două cifre (2^7); 4374 este economic pentru că se scrie cu 4 cifre, în timp ce descompunerea sa în factori primi se scrie cu 3 cifre (2*3^7). Observaţi că atunci când un factor prim apare la puterea 1, aceasta nu este necesar să fie scrisă.
3. Multe numere naturale pot fi scrise ca sumă de două numere prime. Dar nu toate. De exemplu, 121 nu poate fi scris
   ca sumă de două numere prime.

Scrieţi un program care citeşte numărul natural n şi o secvenţă de n numere naturale, apoi rezolvă următoarele cerinţe:

1. determină şi afişează câte dintre numerele din secvenţa dată sunt numere prime din şirul Fibonacci;
2. determină şi afişează câte dintre numerele din secvenţa dată sunt numere economice;
3. determină şi afişează câte dintre numerele din secvenţa dată nu pot fi scrise ca sumă de două numere prime.

Un copil dorește să vopsească ouăle de Paște, având la dispoziție vopsele de culoare roșie, galbenă, verde și albastră. Fiecare culoare va fi reprezentată printr-un singur caracter astfel: 'r' pentru culoarea roșie, 'g' pentru galben, 'v' pentru verde, 'a' pentru albastru. Pentru a vopsi ouăle, le așază în rând, unul după altul. Astfel, o colorare va fi o succesiune de N caractere din mulţimea {'r' , 'g' , 'v','a'}, reprezentând, în ordinea aşezării, culorile celor N ouă.

Numim “roua” o secvență de R caractere cu proprietatea că dintre acestea exact R-1 caractere reprezintă culoarea roșie, iar un caracter reprezintă una dintre celelalte 3 culori. De exemplu secvenţele roua de lungime 3 sunt "grr", "rgr", "rrg", "vrr", "rvr", "rrv", "arr", "rar", "rra" .

Copilul consideră că o colorare este R-frumoasă, dacă oricare R caractere consecutive din colorare formează o secvență roua. De exemplu, pentru N=11 ouă, şirul "arrrvrrrarr" reprezintă o colorare 4-frumoasă.

Cunoscând N, numărul de ouă vopsite, și numărul natural R, scrieți un program care determină și afișează:

1. numărul de secvențe “roua” de lungime R existente în colorarea celor N ouă;
2. numărul total al colorărilor R-frumoase pentru cele N ouă.