Lista de probleme 3

Un grup de N cercetași, numerotați de la 1 la N, se află în tabără la munte. Pentru ei, organizatorii au pregătit N scaune, de asemenea numerotate de la 1 la N, așezate în cerc, astfel încât fiecare cercetaș să aibă locul său (locul cercetașului i este pe scaunul i, 1≤i≤N).

Pentru desfășurarea următoarei activități, organizatorii au decis ca M dintre cercetași să prezinte diferite exerciții. Numărul M este egal cu cea mai mare putere a lui 2 cu proprietatea că numărul N de cercetași aflați în tabără se poate scrie ca sumă de M numere consecutive în mulțimea numerelor impare. Cei M cercetași care vor prezenta sunt cei numerotați cu numerele impare consecutive a căror sumă este N. De exemplu, dacă N=8, atunci M este 2, iar exercițiile vor fi prezentate de cercetașii numerotați cu 3, respectiv cu 5.

Din joacă, micii cercetași s-au așezat pe scaune la întâmplare. Organizatorii au nevoie pentru a desfășura activitatea ca cel puțin cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor. Pentru aceasta, o parte dintre cercetași trebuie să-și schimbe locul și organizatorii invită micii cercetași să participe la jocul numit ”Mutare”. Acest joc se desfășoară astfel: unul dintre cercetașii care nu se află pe locul lor se ridică și merge în interiorul cercului. Cercetașul numerotat cu numărul scaunului rămas liber își va ocupa locul, iar locul ocupat de el anterior rămâne astfel liber. Jocul continuă până când scaunul cercetașului aflat în interiorul cercului se eliberează și el se așază pe locul său.

Fiind dat numărul N, precum și ordinea în care s-au așezat cercetașii pe scaunele numerotate de la 1 la N, scrieți un program care să determine:

• numărul M de cercetaşi care vor prezenta exerciţii în cadrul activităţii;
• numerele de identificare ale celor M cercetaşi care vor prezenta exerciţiile, în ordine strict crescătoare;
• numărul minim de cercetași care își vor schimba locul, astfel încât toţi cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor.

Pasionată de astronomie, Teodora dorește să țină evidența numărului de stele din galaxii. Pentru a face lucrurile mai interesante, ea codifică aceste numere într-un sistem propriu, transformându-le într-o înșiruire de litere și cifre după algoritmul următor:

• notează fiecare putere a lui 2, strict mai mică decât 226, cu o literă a alfabetului, astfel:

20	21	22	23	24	25	26	27	28	29	210	211	212
a	b	c	d	e	f	g	h	i	j	k	l	m
213	214	215	216	217	218	219	220	221	222	223	224	225
n	o	p	q	r	s	t	u	v	w	x	y	z

• reprezintă fiecare număr ca un șir de cifre și litere obținut din scrierea acelui număr ca sumă de puteri ale lui 2; dacă o putere este folosită de mai multe ori în descompunerea numărului atunci ea va fi precedată în șir de numărul de utilizări.

Un număr poate fi reprezentat astfel în mai multe moduri. De exemplu, pentru numărul 100 printre variantele de reprezentare avem:

• 100 = cfg = 22+25+26 = 4+32+64 = 100
• 100 = 2ab2cde2f = 2*20+21+2*22+23+24+2*25 = 2*1+2+2*4+8+16+2*32 = 100
• 100 = 16bcg = 16*21+22+26 = 16*2+4+64 = 100

Scrieți un program care rezolvă următoarele cerinţe:

1. cunoscând s numărul de stele dintr-o galaxie, determină o reprezentare codificată a acestui număr formată doar din litere mici distincte ordonate alfabetic;
2. cunoscând g, reprezentând numărul de galaxii și g numere în scriere codificată, reprezentând numărul de stele din fiecare galaxie, determină scrierea zecimală a numărului total de stele din cele g galaxii.

Noile reguli din sistemul sanitar cer ca medicii să nu prescrie pe reţete un anumit medicament, ci să menţioneze substanţa activă. Reţeta este formată din n prescripţii, câte una pentru fiecare substanţă activă prescrisă.

Farmacista de la care cumpăr medicamentele mi-a făcut o listă în care pentru fiecare substanţă activă de pe reţetă sunt trecute medicamentele care conţin substanţa activă respectivă, precum şi preţul pastilelor prescrise din medicamentul respectiv, sub forma următoare:

• substanţa activă : medicament1 preţ1, medicament2 preţ2, ..., medicamentk preţk

Din păcate, între anumite medicamente există incompatibilităţi şi ca urmare ele nu pot fi administrate simultan, deoarece ar produce reacţii adverse. De aceea, farmacista mea mi-a dat şi o listă de incompatibilităţi, în listă fiind specificate perechi de medicamente incompatibile, sub forma:

• medicament1/medicament2

Când cumpăr reţeta, eu trebuie să iau câte un medicament pentru fiecare substanţă activă prescrisă de medic şi să am grijă să nu cumpăr medicamente care sunt incompatibile. Desigur, voi cumpăra pastilele prescrise pentru tratamentul complet.

Cunoscând lista pe care mi-a dat-o farmacista, precum şi incompatibilităţile dintre medicamente, scrieţi un program care să determine:

1. câte medicamente am la dispoziţie pentru fiecare substanţă activă;
2. suma minimă pe care trebuie să o cheltui pentru a cumpăra reţeta.