Lista de probleme 213

Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu 1 este strict mai mare decât numărul valorilor de 0. De exemplu, în șirul 1,0,0,0,1,1,0,1,1,1,0,0 o secvență dominantă este 0,1,1 și o alta, de lungime mai mare, este 0,1,1,0,1,1,1. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este 1,0,0,0,1,1,0,1,1,1,0 (adică întreg șirul, fără ultimul zero).

Dat fiind un șir de valori binare, să se determine lungimea unei secvențe dominante maximale precum și numărul acestor secvențe.

Ana şi Bogdan au inventat din nou un joc, pe care l-au denumit ks. Pe tabla de joc sunt plasate pe poziţii consecutive n jetoane, pe fiecare jeton fiind scris un număr natural nenul.

Ana este prima la mutare şi are voie să extragă de pe tablă exact k jetoane situate pe poziţii consecutive.

Bogdan mută al doilea şi are şi el voie să extragă exact k jetoane, dintre cele rămase pe tablă, situate de asemenea pe poziţii consecutive.

Punctajul asociat unei mutări este egal cu suma numerelor scrise pe jetoanele extrase la mutarea respectivă.

Scopul Anei este să efectueze mutarea sa astfel încât punctajul obţinut de Bogdan să fie cât mai mic. Considerăm că atât Ana, cât şi Bogdan joacă optim.

Cunoscând numărul de jetoane de pe tabla de joc, valorile înscrise pe acestea, precum şi valoarea k, scrieţi un program care să determine care este cel mai bun punctaj pe care Bogdan îl poate obţine, ştiind că ambii jucători joacă optim.

Un indicator numeric este un dispozitiv de afişaj electronic destinat afişării unei cifre zecimale.
Acesta conține 7 segmente notate cu a, b, c, d, e, f, g, ca în figura de mai jos.

Afişarea unei cifre se face prin aprinderea unei combinații de segmente conform tabelului:

Cunoscând un număr natural N afișat cu ajutorul mai multor indicatoare numerice, să se scrie un program care determină:

1. Numărul de segmente aprinse pentru afișarea numărului N.
2. Numărul de numere distincte mai mari decât N,ce se pot forma prin aprinderea a cel puțin unui segment în plus, față de cele utilizate pentru afișarea numărului N, fără a folosi alte indicatoare numerice, și fără a stinge niciun segment dintre cele deja aprinse.

În oraşul Z sunt un număr de n obiective turistice, numerotate de la 1 la n. Pentru a ajuta turiştii să viziteze oraşul, primăria a cumpărat un autobuz special ce are k locuri şi care va parcurge cele n puncte de atracţie turistică începând cu obiectivul numerotat cu 1, apoi obiectivul numerotat cu 2, …, până la obiectivul numerotat cu n şi apoi revine la obiectivul 1, traseul având formă circulară. În fiecare staţie aşteaptă un anumit număr de călători; pentru fiecare călător se ştie numărul de staţii pe care doreşte să le parcurgă. Călătorii au acces în autobuz numai dacă sunt locuri libere, în ordinea în care așteaptă în stație, iar cei care nu pot urca părăsesc staţia; la următoarea oprire în staţia respectivă vor aştepta alţi călători. Pentru fiecare staţie parcursă costul unui bilet este 1 leu. Autobuzul va face pentru ultima urcare a călătorilor şi un ultim tur în care doar coboară călători şi nu urcă nimeni. Se cere numărul de curse complete realizate şi suma încasată pentru cursele realizate.

Determinarea valorilor ce reprezintă suma încasată şi numărul de curse complete realizate.

N puncte numerotate de la 1 la N sunt aşezate pe cerc, în sensul acelor de ceasornic, în ordine strict crescătoare.

Există M segmente de dreaptă diferite care unesc M perechi de puncte dintre cele N date. Cele două puncte care formează orice pereche sunt distincte.

Distanţele dintre două puncte succesive sunt alese astfel încât să nu existe 3 sau mai multe segmente care trec printr-un acelaşi punct interior cercului.

Cunoscându-se numărul de puncte, numărul de perechi şi perechile de puncte care vor fi unite, se cere să se determine numărul P de puncte de intersecţie formate de acestea în interiorul cercului (punctele de intersecţie aflate chiar pe cerc nefiind luate în considerare).

Ana are un joc nou. Pe o tablă pătrată este trasat un grid format din celule pătratice de dimensiune 1. În oricare dintre colţurile oricărei celule, Ana poate înfige câte un beţişor perpendicular pe tablă. După ce a plasat n beţişoare, Ana ia dintr-o cutie (cu un număr suficient de mare de corzi elastice circulare) câte o coardă cu care înconjoară trei sau mai multe beţişoare. Fiecare coardă este bine întinsă şi formează pe tablă un contur poligonal.
În figura alăturată este folosită o coardă ce formează un contur poligonal cu 4 laturi cu care sunt înconjurate 5 dintre cele 8 beţişoare de pe tablă.

Jocul se încheie când au fost plasate atâtea coarde încât toate beţişoarele de pe tablă să se afle pe marginea sau în interiorul a cel puţin unul dintre contururile poligonale formate. Scopul jocului este ca amplasarea corzilor să fie făcută convenabil astfel încât totalul ariilor contururilor poligonale formate să fie minim.

Cunoscând coordonatele celor n beţişoare (x[1], y[1]), (x[2], y[2]), …, (x[n], y[n]) măsurate faţă de unul dintre colţurile gridului, Ana doreşte să găsească suma minimă a ariilor poligonale obţinute prin amplasarea convenabilă a coardelor, astfel încât fiecare beţişor să se găsească în interiorul sau pe conturul a cel puţin un astfel de poligon.

La marginea unei păduri sunt N stupi aşezaţi în linie. Ei au asociate numere de ordine de la 1 la N, în ordinea în care apar. Fiind sezonul florii de salcâm, albinele colectează foarte repede mierea. La finalul fiecărei zile, din satul aflat în apropiere vine un apicultor la volanul unui camion pentru a o recolta. Capacităţile camioanelor pot fi diferite. Procesul de strângere a mierii decurge astfel: camionul pleacă din dreptul stupului 1 şi încarcă întreaga cantitate de miere din acesta, apoi trece la stupul 2 şi procedează la fel şi aşa mai departe. Dacă odată ajuns la un stup camionul nu poate colecta întreaga cantitate de miere din acel stup, acesta întrerupe acţiunea de colectare şi se întoarce în sat. În ziua următoare, albinele din stupii de unde s-a recoltat refac cantitatea de miere din ziua anterioara. În plus, în fiecare stup cantitatea de miere creşte cu un kilogram faţă de ziua anterioară.

Dându-se N, numărul de stupi, cantitatea de miere existentă în fiecare la finalul primei zile, numărul M de zile în care se face colectarea mierii şi capacitatea camionului care trece în fiecare zi, se cere numărul de stupi din care se recoltează miere în fiecare dintre cele M zile.

Arpsod are în curtea sa N copaci foarte bătrâni, așezați în linie și numerotați de la 1 la N. Fiecare copac are o înălțime cunoscută, Hi. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni. Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea 1, 2, 3, ... ,N iar cel de-al doilea în ordinea N, N-1, N-2, ... 1. Fiind un tărâm democratic, fiecare muncitor dorește să fie plătit pentru fiecare metru pe care îl taie. Muncitorul 1 are un tarif de T1 pe metru iar muncitorul 2 un tarif de T2 pe metru. Dacă un muncitor a început să taie un copac, acesta îl va tăia integral. Din motive de protecție a muncii, muncitorilor nu le este permis să lucreze simultan. De aici apare următoarea pretenție: dacă după tăierea unui copac, muncitorul nu este înlocuit de colegul său, acesta va cere un cost suplimentar C pentru a rămâne să taie în continuare.
De exemplu, dacă avem 3 copaci: 1, 2, 3 și muncitorul 1 taie singur toți copacii, acesta va cere un cost suplimentar de 2 ori (pentru copacul 2 și copacul 3).

Arpsod vă cere să determinați costul minim pe care îl poate plăti astfel încât toți cei N copaci să fie tăiați.

Un număr natural nenul se numeste “p-prim” dacă el se descompune în p moduri ca produs de doi factori primi între ei. De exemplu, numărul 60 este 4-prim deoarece 60 se decompune în 4 moduri ca produs de doi factori primi între ei 60=1*60=4*15=5*12=20*3, iar numărul 7 este 1-prim. Pentru un interval închis [a,b] să se determine câte numere p-prime aparţin intervalului. De exemplu intervalul [7, 20] conţine numerele 2-prime: 10,12, 14,18,20.

Pădurea magică din Povestea lui Negrimon este situată pe un teren dreptunghiular care poate fi privit ca o matrice cu N linii, numerotate de la 1 la N şi M coloane, numerotate de la 1 la M. Putem spune că terenul este împărţit în N * M
parcele pătrate de latură 1. În pădure trăieşte şarpele Snake care, iniţial, este lung cât K parcele şi lat cât una singură. La începutul poveştii şarpele se află pe prima linie, pe parcelele de la 1 la K, capul fiind pe poziţia K şi orientat spre est.

Snake se deplasează cu o parcelă pe secundă. Astfel, după prima secundă, şarpele se va afla tot pe linia 1, deplasat cu o poziţie spre dreapta, mai exact capul va fi în parcela K + 1. Deplasarea se face simultan cu întreg corpul.

În pădure au loc E evenimente ce pot fi de tipurile următoare:

1. Apariţia unui măr la secunda st pe linia x şi coloana y, care va dispărea la secunda en, dacă nu este mâncat până atunci de şarpe. Snake înghite mărul când capul său ajunge în parcela care îl conţine. Mărul dispare, desigur, iar corpul şarpelui creşte instantaneu cu o unitate care îi va fi adăugată la coadă şi va ocupa aceeaşi parcelă pe care s-a aflat coada (ultima porţiune din corp) la secunda anterioară înghiţirii mărului.

1. Apariţia unui schimbător la secunda st pe linia x şi coloana y, care va dispărea la secunda en şi care are valoarea v. Când capul şarpelui ajunge în parcela schimbătorului, direcţia ulterioară de deplasare va fi dată de valoarea v ∈ {1, 2, 3, 4} cu semnificaţia: 1 Nord (sus); 2 Est (dreapta); 3 Sud (jos); 4 Vest (stânga).

Schimbătorul funcţionează astfel: de exemplu, dacă Snake se deplasează spre Est şi la o anumită secundă capul acestuia ajunge într-o parcelă unde se află un schimbător cu valoarea 1, la următoarea secundă capul se va afla în parcela situată deasupra schimbătorului şi în parcela schimbătorului se află prima porţiune din corpul şarpelui.

Schimbătorul dispare exact în secunda en iar până atunci rămâne în matrice indiferent de câte ori Snake trece prin parcela acestuia. Schimbătorul va acţiona doar când capul lui Snake ajunge în parcela lui şi nu va exista nicio situaţie în care să se schimbe direcţia în sens opus celei din care vine. De exemplu, dacă direcţia lui Snake este spre Est, nu va întâlni un schimbător cu valoarea 4, care l-ar întoarce spre Vest.

În fiecare secundă s, evenimentele se petrec în acestă ordine: dispar obiectele programate să dispară în secunda s, apar obiectele ce trebuie să apară în secunda s, Snake se deplasează cu o parcelă. Dacă printr-o combinaţie nefericită de mişcări, Snake se loveşte de propriul corp, el se blochează şi aşteptă serviciul de asistenţă a pădurii.

Deoarece Snake se află într-o pădure magică, deplasarea lui respectă reguli speciale: când capul este pe ultima coloană din matrice şi se mişcă spre Est, el reapare pe aceeaşi linie, dar pe prima coloană, trăgând corpul simultan. Analog şi pentru prima coloană, când se deplasează spre Vest, capul reapare pe aceeaşi linie dar pe ultima coloană. Dacă şarpele se află pe prima linie şi se deplasează spre Nord, mişcarea va continua pe ultima linie şi aceeaşi coloană din matrice. Analog pentru ultima linie, când Snake se deplasează spre Sud, capul reapare pe prima linie şi aceeaşi
coloană. Aceste mişcări au loc doar dacă Snake nu se blochează în propriul corp.

Povestea se termină în secunda în care apare oricare dintre situaţiile: Snake se loveşte de propriul corp, caz în care el rămâne BLOCAT; toate cele E evenimente s-au produs şi nu mai există niciun obiect în matrice pentru că toate au
dispărut, caz în care rămâne un şarpe LIBER.

Cerința: În funcţie de finalul poveştii, afişaţi starea lui Snake şi harta pădurii în secunda respectivă. Pe hartă trebuie să fie marcate parcelele ocupate de corpul lui Snake, inclusiv capul.