Lista de probleme 977

Comisia Naţională a Audiovizualului (CNA) este autoritatea care coordonează activitatea posturilor media din România. Șeful CNA-ului dorește o statistică referitoare la publicitatea transmisă de posturile de televiziune. În acest scop, el primește pentru fiecare zi informații în următorul format: d hh:mm:ss, unde d este durata exprimată în secunde a publicității, iar hh:mm:ss este momentul de start al publicității (hh este ora, mm este minutul, iar ss este secunda). Observaţi că d este separat de hh printr-un singur spaţiu, iar următoarele valori sunt separate prin caracterul ':'.

De exemplu o linie de forma:

150 05:02:45

se interpretează astfel: există un post TV care a transmis publicitate cu durata de 150 secunde, ora de început fiind 5, 2 minute și 45 de secunde.

”Secunda de aur” este o secundă în care se difuzează cât mai multă publicitate, adică pe un număr maxim de posturi în acea secundă se transmite publicitate. Dacă sunt mai multe astfel de secunde, “secunda de aur” este considerată prima secundă cu această proprietate în derularea zilei.

Șeful CNA primește în fiecare dimineață lista cu activitatea din ziua anterioară ca o succesiune de linii, fiecare linie având forma descrisă mai sus.

Scrieţi un program care, cunoscând lista din ziua anterioară, să rezolve următoarele cerinţe:

1. să determine durata totală în care niciun post de televiziune nu a difuzat publicitate;
2. să determine care este “secunda de aur”.

Pentru obținerea Pietrei Filosofale, un alchimist a preparat un elixir folosind un creuzet de capacitate C, în care a turnat picături de metal topit, într-o ordine bine stabilită, în N etape. Numărul de picături turnate într-o etapă este cuprins între 0 și C-1, iar procesul începe când în creuzet s-a turnat prima picătură (în prima etapă numărul de picături turnate este nenul). Picăturile se adună în creuzet una câte una şi, de fiecare dată când acesta se umple complet, alchimistul rosteşte o formulă magică, provocând transformarea întregului conţinut într-o singură picătură, apoi continuă procesul. O rețetă de obținere a elixirului se exprimă printr-un șir de N numere, reprezentând numărul de picături turnate în cele N etape.

De exemplu, aplicând rețeta 5 6 1 0, cu un creuzet de capacitate C=7, în cele N=4 etape procesul este:

• etapa 1: se toarnă 5 picături;
• etapa a 2-a: se toarnă 6 picături, astfel: după primele 2 picături se umple creuzetul (5+2=7) și deci se rosteşte formula magică, în creuzet rămânând o picătură; se continuă cu celelalte 4 picături; la finalul etapei în creuzet sunt 5 picături (1+4=5);
• etapa a 3-a: se toarnă o picătură; la finalul etapei în creuzet sunt 6 picături (5+1=6);
• etapa a 4-a: se toarnă 0 picături; după ultima etapă creuzetul conține 6 picături (6+0=6).

O rețetă care corespunde Pietrei Filosofale trebuie să conducă, la finalul aplicării ei, la obținerea unei singure picături, chintesența metalelor amestecate. Bineînțeles, sunt mai multe astfel de rețete.

Fiind un tip responsabil, alchimistul a lăsat posterității un set de tratate, care cuprind toate aceste rețete. El a scris pe fiecare pagină câte o rețetă, astfel încât niciuna să nu se repete în cadrul întregii lucrări. Pe vremea aceea erau meșteri pricepuți, care fabricau tratate de dimensiuni corespunzătoare, încât fiecare pagină să poată cuprinde o rețetă ca a noastră, oricât de lungă ar fi ea. Fiecare tratat are P pagini și doar după ce completează toate cele P pagini ale unui tratat, alchimistul începe un nou tratat.

Se cere numărul de rețete publicate în ultimul tratat.

Gigel si Ionel se joacă de-a spionii! De aceea ei imaginează o modalitate de a codifica un mesaj astfel încât nimeni să nu îl poată descifra. Toate mesajele lor au lungimea o putere a lui 2. Ei numerotează literele mesajului începând cu 1. Apoi separă literele în două categorii: cele cu număr de ordine impar în stânga, cele cu număr de ordine par în dreapta, păstrând ordinea lor. Procedeul continuă pentru fiecare grupă nou rezultată începând cu cea din stânga, până când fiecare grupă obţinută conţine un singur caracter. După terminarea operaţiilor alipesc grupele de câte o literă rezultate, începând de la stânga spre dreapta şi obţin mesajul codificat.

De exemplu pentru mesajul MESAJNECODIFICAT procedează astfel:
1. numerotează

MESAJNECODIFICAT
123456789...

2. separă

MSJEOIIA                   EANCDFCT            apoi repetă paşii 1 şi 2 pentru 
12345678                   12345678            fiecare grupă rezultată

MJOI        SEIA           ENDC       ACFT
1234        1234           1234       1234

MO   JI     SI   EA        ED  NC     AF  CT
12   12     12   12        12  12     12  12

M O  J I    S I  E A       E D  N C   A F  C T
1 2  1 2    1 2  1 2       1 2  1 2   1 2  1 2    

până se obţine un singur caracter în fiecare grupă şi alipind literele de la stânga spre dreapta rezultă mesajul codificat: MOJISIEAEDNCAFCT

Scrieţi un program care să rezolve următoarele două cerinţe:

1. dat fiind un mesaj, să determine codificarea acestuia;
2. dat fiind un mesaj codificat, să determine decodificarea acestuia.

Fie A = (a[1],a[2],…,a[N]) o permutare a mulțimii {1,2,…,N}.

Permutarea A o numim K-swap dacă prin aplicarea algoritmului de sortare bubble-sort sunt necesare exact K swapuri (interschimbări) pentru ca aceasta să devină permutarea identică.
Reamintim algoritmul bubble-sort:

do {   
    ok = 1;    
    for ( i = 1; i < N; i ++ )      
        if ( a[i] > a[i+1] ){        
             swap(a[i], a[i+1]);   
             ok = 0;   
        }
}while( ok == 0 );          

Pentru N și K dat să se determine numărul de permutări K-swap ale mulțimii {1,2,…,N}.

Victor are la dispoziție multe cuburi din lemn, toate de aceeași dimensiune, fiecare fiind colorat cu una din culorile 0, 1, 2, …, 9. El a inventat un joc sub forma unui algoritm:

• Pasul 0 – Se inițializează variabila X cu zero.
• Pasul 1 – Se aleg la întâmplare un număr de cuburi și se formează cu ele un șir. Cuburile din șir sunt lipite unul de altul.
• Pasul 2 – Dacă toate cuburile din șir au aceeași culoare, atunci se afișează valoarea variabilei X și jocul se oprește. În caz contrar se trece la pasul 3.
• Pasul 3 – Se alege o culoare C și apoi toate cuburile de culoarea C se elimină din șir. Locurile cuburilor eliminate rămân temporar libere.
• Pasul 4 – Orice cub din șir va fi deplasat spre stânga lui, cât timp pozițiile vecine sunt libere. Se mărește X cu 1 la fiecare deplasare cu o poziție. Operațiile de deplasare se încheie când nu se mai pot efectua mutări spre stânga. Apoi se revine la pasul 2.

Se consideră un șir cu cel puțin două elemente reprezentând culorile cuburilor din șir. Se cere să se calculeze valoarea maximă pe care o poate avea X.

Manole este extrem de răcit. Din această cauză a mers la medicul de familie care l-a sfătuit urmeze un tratament cu N pastile, din care trebuie să ia în fiecare zi câte o jumătate. A cumpărat de la farmacie o cutie în care se aflau exact N pastile, fiecare dintre ele având pe suprafață o dungă care marchează jumătatea ei.

Manole începe să își ia tratamentul și constată că poate proceda doar astfel:

• scoate din cutie o pastilă întreagă din care folosește, în ziua respectivă, doar jumătate din ea, iar jumătatea rămasă o pune înapoi în cutie;
• scoate din cutie o jumătate de pastilă, rămasă din una din zilele anterioare, pe care o folosește în ziua respectivă.

Scrieți un program care determină numărul de posibilități în care poate lua toate cele N pastile, procedând după procedeul descris mai sus.

Specificul insulelor din arhipelagul Maldive (Oceanul Indian) este faptul că toate cele N insule ale sale au forma unui triunghi. Localizarea acestor insule folosește coordonatele carteziene ale celor trei vârfuri.

Administrația acestor insule dorește să instaleze un dispozitiv de emisie-recepţie pe apă sau pe o insulă, într-un punct având coordonate numere naturale (xD, yD), ce transmite semnale numai pe direcții orizontale și verticale concomitent, cu următoarele proprietăţi:

• notând cu NRO numărul de insule la care ajunge semnalul pe orizontală și cu NRV numărul de insule la care ajunge semnalul pe verticală, suma NRO + NRV trebuie să fie maximă;
• dacă există mai multe puncte cu proprietatea anterioară, atunci se va alege punctul cel mai mic în ordine lexicografică.

Să se scrie un program care cunoscând numărul de insule N şi coordonatele carteziene ale vârfurilor acestora, determină coordonatele xD și yD cu proprietățile din enunţ.

Dându-se n fracții ireducitibile sortate crescător și un număr k să se determine numărul de subșiruri de exact k elemente în care diferența dintre două fracții consecutive este egală cu 1. De asemenea, prima fracție din subșir trebuie să nu fie supraunitara.

Să se rezolve n inecuații.

Zoli și D’Umbră s-au pierdut într-un labirint cu n x n camere dispuse pe cate n linii și n coloane. D’Umbră se află în camera (1, 1), iar Zoli se află în camera (n, n). Aceștia vor trebui să parcurgă labirintul pentru a se întâlni.