Programarea Calculatoarelor, seria CC

Ultima modificare: duminică, 24 octombrie 2010

Tema 1

Data publicării: duminică, 24 octombrie 2010

Deadline: duminică, 7 noiembrie 2010, ora 23:55

Precizări:



Problema 1. [30 puncte] Aritmetică pe date

Ema este o fată superstițioasă și, în același timp, pasionată de astronomie. De curând, ea a aflat despre profeția Maya privind anul 2012. Aceasta susține că sfârșitul lumii va avea loc pe 21 decembrie 2012. Calendarul Maya se încheie brusc la această dată, cu toate că, în trecut, mayașii, care erau foarte avansați în astronomie, calculaseră date cosmice până la milioane de ani.

Așadar, Ema s-a decis să o ia pe urmele mayașilor și să verifice dacă profeția este corectă. Pentru început ea exersează operațiile aritmetice de bază specifice calendarului. Cu toate că este pasionată de ceea ce face, ea nu va reuși să-și termine treaba la timp pentru că a început facultatea și temele abundă. Ajutați-o pe Ema să-și însușească operațiile de bază astfel încât să poată demonstra veridicitatea profeției Maya.

Date de intrare:

Se citesc de la tastatură o dată calendaristică în format ZI LUNĂ AN și un număr întreg x (-30 000 ≤ x ≤ 30 000).

Cerință:

Să se calculeze și afișeze data rezultată prin adunarea la data calendaristică citită a x zile.

Aveți grijă la anii bisecți! Găsiți aici algoritmul pentru a afla dacă un an este bisect.

Date de ieșire:

Rezultatul va fi afișat în format ZI LUNĂ AN. Dacă data citită este invalidă, se va afișa mesajul Data invalida!.

Exemplu:

Intrare Ieşire Explicație
1 1 2010
5
6 1 2010 1 ianuarie 2010 + 5 zile = 6 ianuarie 2010
1 1 2010
-5
27 12 2009 1 ianuarie 2010 - 5 zile = 27 decembrie 2010
31 2 2010
5
Data invalida! Nu există data 31 februarie 2010

Problema 2. [30 puncte] Logica

Marcvs este un băutor înrăit de cafea şi s-a hotărât să îşi deschidă propria sa plantaţie. El a plecat într-o călătorie în jurul lumii în căutarea locului perfect, dar pentru că lucrurile nu merg mereu conform planurilor, a naufragiat pe o insulă.

După câteva zile, şi-a dat seama că pe această insulă locuiesc trei triburi de băştinaşi: Sfinţi, Demoni şi Oameni. La un studiu mai atent, a aflat despre ei următoarele lucruri:

În urma unei întâlniri dintre șefii celor trei triburi, s-a decis că Marcvs își va recâștiga libertatea dacă, în urma a trei întrebări, poate să ghicească corect identitățile acestora. Când Marcvs a fost chemat să se prezinte în fața lor, conversația a decurs astfel:

(*) considerăm că Șeful 1 stă în stânga Șefului 2 (deci cum privim spre ei)
(**) relațiile de ordine nu sunt considerate ciclice, cu alte cuvinte, Șeful 1 NU stă în dreapta Șefului 3

  1. Marcvs către șeful 1: Imediat în dreapta Demonului stă Omul?
  2. Șeful 1: X
  3. Marcvs către șeful (3-X): Dacă ai fi Demon și te-aș întreba, ai recunoaște că ești Demon?
  4. Șeful (3-X): Y
  5. Marcvs către șeful (3-X): Este posibil ca cel din stânga ta să fi dat același răspuns cu tine la întrebarea precedentă?
  6. Șeful (3-X): Z

Se știe că șefii de trib răspund cu:

Atentie! Întrebările 2 și 3 au fost adresate șefului determinat de răspunsul la întrebarea 1 (2 pentru True, 3 pentru False)!

Date de intrare:

Se citesc de la tastatură X, Y și Z, trei numere naturale din mulțimea {0,1} reprezentând răspunsurile celor trei șefi de trib.

Cerință:

Ajutați-l pe Marcvs să plece de pe insulă și să își continuie căutarea locului perfect pentru plantația de cafea, afișând în ordine identitățile celor trei șefi de trib.

Pentru a primi punctajul complet, veți explica în cuvinte și raționamentul pe care l-ați folosit (în fișierul README).

Date de ieșire:

Programul va afișa unul dintre raspunsurile:
  1. Sfant Om Demon
  2. Sfant Demon Om
  3. Om Sfant Demon
  4. Om Demon Sfant
  5. Demon Sfant Om
  6. Demon Om Sfant

Exemplu:

Intrare Ieşire
1 0 0 Demon Sfant Om

Problema 3. [40 puncte] Echipe

La un concurs de programare sunt înscriși n studenți. Fiecare dintre cei n studenți și-a creat câte o echipă. Fiecare echipă are inițial un singur membru: studentul care a creat-o. Studenții au hotarât că numărul membrilor unei echipe poate să crească prin unificarea cu o altă echipă după următoarea regulă: două echipe se pot unifica dacă au același număr de membri. Prin unificare, una dintre echipe va continua să existe, iar cealaltă se va desființa. Echipa care continuă să existe preia toți membri echipei care se desființează. Deoarece studenții pot rezolva mai ușor problemele atunci când echipa are mai mulți membri, ei au hotărât sa unifice echipele după regula de mai sus, cât timp unificarea este posibilă.

Cerință:

Scrieţi un program care să citească numărul natural n şi care să determine:
a) cel mai mic număr natural k de echipe care continuă să existe după ce s-au produs toate unificările;
b) pentru fiecare dintre echipe, numărul de membri.

Date de intrare:

De la tastatură se va citi un număr natural n (n ≤ 30000) care reprezintă numărul de studenți înscriși la concursul de programare.

Date de ieșire:

Pe prima linie a ieșirii standard se va afișa un număr natural k, reprezentând cel mai mic număr de echipe care continuă să existe după ce s-au produs toate unificările.
Pe a doua linie, se vor afișa k numere naturale nenule, separate prin câte un spaţiu, reprezentând numărul de membri ai fiecărei echipe, în ordinea crescătoare a numărului de membri.

Observaţii:

  • În cazul în care numărul studenţilor este impar se consideră că studentul rămas singur formează o echipă.
  • Pentru fiecare test de intrare se poate determina cel puţin o echipă.

Exemplu:

Intrare Ieşire Explicație
7 3
1 2 4
6 studenți formează 3 echipe având fiecare câte 2 membri, iar studentul rămas formează la rândul lui o echipă (cu un singur membru).
Apoi 2 dintre echipele cu câte 2 membri se unesc şi formează o singură echipă cu 4 membri. Deci sunt 3 echipe: 1 cu un membru, 1 cu 2 membri şi 1 cu 4 membri.
24 2
8 16
Iniţial se formează 12 echipe cu câte 2 membri, apoi 6 cu câte 4 membri.
Din cele 6 echipe se vor forma apoi 3 cu câte 8 membri. Două dintre echipele cu 8 membri se unesc formând una cu 16 membri.
În final rămân 2 echipe, una cu 8, iar celălaltă cu 16 membri.