Lista de probleme 51

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#1247 Torturi

Adela lucrează la un laborator de cofetărie. Ea trebuie să pregătească două torturi de nuntă şi în acest scop va folosi n blaturi de tort. Blaturile de tort au formă cilindrică, având toate aceeaşi înălţime, eventual diametre diferite. Blaturile ies pe rând din cuptor. Când un blat iese din cuptor, Adela îl va aşeza deasupra uneia dintre cele două stive de blaturi aflate pe cele două tăvi pe care se pregătesc torturile.

Blaturile diferă între ele prin rezistenţa la presiune. Rezistenţa unui blat creşte odată cu creşterea diametrului. Astfel, un blat va suporta deasupra sa oricâte alte blaturi cu diametre mai mici sau egale cu diametrul său. Pe de altă parte, dacă se aşează un blat de diametru d, deasupra altuia de diametru mai mic, atunci atât blatul aflat imediat dedesubt, cât şi toate blaturile din tort cu diametrul mai mic decât d vor colapsa. Blatul de diametru d se va stabiliza pe un blat cu diametru mai mare sau egal cu al său sau după caz, pe fundul tăvii.

Adela trebuie să folosească toate cele n blaturi pentru pregătirea celor două torturi, şi să le aşeze pe cele două tăvi, în ordinea în care blaturile ies din cuptor. Dorinţa Adelei este ca numărul total de blaturi care nu vor colapsa în cele două torturi să fie maximă.

Cunoscând diametrele blaturilor şi ordinea în care acestea ies din cuptor, să se determine numărul maxim de blaturi care nu vor colapsa.

#1736 Cuie

Pe o scândură se găsesc înfipte și aliniate N cuie de diverse înălțimi, măsurate în centimetri.

La fiecare ”bătaie” de ciocan într-un cui, acesta pătrunde în scândură cu 1 cm. Tâmplarul dorește să obțină cea mai lungă secvență de cuie de aceeași înălțime, după aplicarea a cel mult M ”bătăi” de ciocan.

Să se determine lungimea maximă – L a unei secvențe de cuie de aceeași înălțime în condițiile date și numărul minim de ”bătăi” – K necesare obținerii acesteia.

Deoarece vin sărbătorile, elevii de la Liceul de informatică s-au gândit să decoreze laboratorul P1 cu ghirlande legate între ele. Ei au cumpărat N ghirlande numerotate de la 1 la N și vor să le lege împreună apoi să orneze laboratorul. Fiecare ghirlandă are doua culori distribuite astfel încât capetele să aibă culori diferite. Culorile sunt codificate prin numere naturale. Decoraţiunile cumpărate au N-1 culori care apar exact de două ori şi 2 culori care apar doar o singură dată. Pentru a face munca mai distractivă ei s-au gândit că, la legarea a două ghirlande, să unească două capete de aceeaşi culoare.

1) Pentru cerinţa 1 copiii vor să afle suma codurilor culorilor aflate la cele două capete ale lanţului format prin legarea ghirlandelor cumpărate, respectând regulile de îmbinare de mai sus.
2) Pentru cerinţa 2 ajutaţi-i să lege ghirlandele pentru a decora laboratorul P1 respectând regulile menţionate. Trebuie sa afisati numerele de ordine ale ghirlandelor în ordinea în care vor fi legate. La cele doua capete se vor afla
cele doua ghirlande care conțin o culoare ce apare o singura data. Dintre acestea prima va fi cea care are codul culorii mai mic

#1427 Manager

Andrei este manager la o firmă foarte importantă, la care se lucrează în ture. Aceste ture durează un număr constant de minute (1017 minute), fiecare tură începând la minutul 1. După o tură, Andrei, fiind foarte obosit, doarme până la începutul următoarei ture.

El este foarte ocupat cu o mulțime de ședințe (S ședințe mai exact). Acestea sunt trecute în agenda lui astfel: Minutul de început Durata Minutele necesare pentru pregătire – în minutele de pregătire nu trebuie să îl deranjeze nimeni).

Agenda este foarte dezordonată, iar şedinţele nu sunt notate în ordine cronologică, şi, în plus, acestea se pot suprapune. Ca un bun manager, Andrei doreşte să participe la cât mai multe şedinţe într-o tură cu condiţia să nu se desfăşoare în acelaşi timp. Deoarece nu poate renunța la nicio ședință, el va amâna pentru turele viitoare unele dintre ședințele care se suprapun, păstrând în agendă aceleași informații despre fiecare (început, durată, timp necesar pentru pregătire).

a) Afișați numărul minim de ture în care Andrei poate participa la toate şedinţele.
b) Știind că în prima tură, Andrei poate să ajungă la toate şedinţele (nu se desfăşoară două sau mai multe şedinţe la un moment dat), determinați minutul în care se poate programa începutul pregătirii unei noi şedinţe de durată D şi timp de pregătire P, astfel încât să nu se suprapună cu o alta (dacă există mai multe soluţii se va afişa cea cu momentul de început minim).

#1787 Mapal

Marele inginer NN, a fost numit inspector general al barajelor. În prima zi de lucru el primește un sector dintr-un baraj de lângă un lac de acumulare care conține stricăciuni și are misiunea de a realiza un plan de reparații. În plus, costurile reparațiilor trebuie să fie minime. Sectorul din baraj poate fi reprezentat ca o matrice binară de NxN. El a observat că liniile l1, l2 …, lk și coloanele c1,c2, …, cl sunt singurele care au stricăciuni. Pentru a le repara el trebuie să înlocuiască unele elemente din matrice astfel încât liniile și coloanele stricate să devină palindrom.

Ajutați-l pe NN să găsească numărul minim de înlocuiri și să dovedească că e maestru în baraje de toate felurile.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1488 Strazi

Gigel primeşte o nouă provocare de la prietenul său Programatorul! Cunoscând înălţimile clădirilor aflate pe o anumită stradă, Gigel trebuie să răspundă rapid la întrebarea: “Care este gradul de vizibilitate al străzii?”

Gradul de vizibilitate al unei străzi este dat de raportul dintre numărul clădirilor vizibile din capătul stâng al străzii şi numărul total al clădirilor de pe stradă, raport calculat cu trei zecimale.

Pentru o intersecţie de N străzi ajutaţi-l pe Gigel să determine gradul de vizibilitate al fiecărei străzi şi să precizeze care este strada cu grad maxim de vizibilitate.

Olimpiada locală de Informatică, Prahova, 2016

#1592 Plata

Eroul nostru, Costy merge la magazin pentru a-şi cumpăra biscuiţi. Vânzătorul îi spune că biscuţii costă S nasturi, şi că doreste ca plata lor să fie făcută cu n tipuri diferite de nasturi. De asemenea, vânzătorul precizează că ar dori ca numărul de nasturi din fiecare tip i să depăşească valoarea x[i], dar, să nu depăşească valoarea y[i]. Presupunând că baiatul are o infinitate de nasturi din fiecare tip şi că doreşte să rămână cu cât mai mulţi nasturi de tipurile n, n-1, n-2,.. în buzunar, ajutaţi-l să efectueze plata şi să pună cât mai repede mâna pe biscuiţi.

#2044 Cursuri

Într-o tabără de vară se programează susținerea unor cursuri în K săli de clasă. Sunt N profesori care și-au exprimat dorința de a participa, fiecare dintre ei specificând intervalul de timp [ai, bi] în care își poate susține cursul. Programarea pe săli a profesorilor trebuie să țină cont de faptul că într-o clasă, la un moment dat, nu poate preda decât un singur profesor.

Cunoscându-se faptul că organizatorii doresc susținerea a cât mai multor cursuri, să se determine:

1) Numărul maxim de cursuri care pot fi programate în cele K săli de clasă, ținând cont de restricția indicată.
2) În dorința de a programa toate cursurile, în cele K săli, organizatorii decid să modifice durata cursurilor, păstrând însă neschimbată ora de început a lor. Astfel, ei hotărăsc ca toate cursurile să dureze un interval egal de timp, care însă nu va depăși durata celui mai lung curs propus inițial de unul dintre cei N profesori. Determinați care poate fi durata maximă pe care o pot avea cursurile în aceste condiții.

Misiunea robotului Curiosity este de-a trimite imagini și informații către satelitul plasat pe orbita planetei Marte. Zona de explorare a robotului este de-a lungul unei axe de coordonate Ox. Robotul este înzestrat cu o baterie solară de capacitate energetică maximă C și consumă pentru fiecare unitate de drum parcurs o unitate de energie. Coordonata punctului de plecare al incursiunii robotului (raportată la origine x=0) este Xs, iar punctul unde este finalizat studiul are coordonata Xf.
Totodată, cercetătorii au stabilit N puncte ce fac posibilă încărcarea bateriilor robotului, numerotate de la 1 la N. În funcție de intensitatea luminii solare primite, reflectată în durata de încărcare a bateriei, punctele de încărcare sunt de trei tipuri: tipul 1–intensitate minimă/timp de încărcare mare, tipul 2–intensitate medie/timp de încărcare mediu, tipul 3–intensitate maximă/timp de încărcare scurt. Altfel, fiecare punct de încărcare i este descris prin perechea t[i] x[i], adică tipul de încărcare, respectiv poziția acestuia pe axă. În orice punct de încărcare robotul poate decide dacă încarcă sau nu bateria, cu unități de energie, nu mai mult decât capacitatea maximă. Robotul se poate deplasa dintr-un punct atât în stânga cât și în dreapta pe axă.
Pentru a scurta durata parcurgerii distanței către punctul final se dorește determinarea unei strategi optime a opririlor pentru încărcarea bateriilor, astfel încât cantitatea totală de energie încărcată în puncte de tipul 1 să fie minimă. În cazul în care sunt mai multe strategii de oprire pentru care cantitatea totală de energie încărcată în puncte de tipul 1 este minimă, atunci se va alege strategia pentru care cantitatea totală de energie încărcată în puncte de tipul 2 să fie minimă.

Dacă se cunosc Xs, Xf, C, precum și descrierea celor N puncte de încărcare să se determine o strategie de deplasare între coordonatele Xs și Xf, optimă din punct de vedere al timpului necesar încărcării bateriilor.

#3032 sufle

Sufle este un personaj cu urechi ascuțite, îndrăgostit de algoritmică. El are o antipatie profundă față de Aisimok, cel care îl tot provoacă să rezolve probleme folosind tot felul de formule. Sufle a botezat aceste probleme Emsiteanap. Astăzi Aisimok i-a aruncat tânărului Sufle o nouă provocare:

Pentru oricare două numere naturale se definește următoarea operație:

  • se consideră reprezentările în baza 2 pentru cele două numere;
  • se alege o poziție în reprezentarea binară a primului număr;
  • se schimbă cifra situată pe acea poziție în primul număr cu cifra aflată pe exact aceeași
    poziție în al doilea număr. (Observați cum Aisimok, obsedat de matematică, nu a folosit termenul bit, tocmai pentru a-l irita pe Sufle.)

Pentru un șir oarecare de numere naturale, se poate aplica de oricâte ori și asupra oricăror două numere operația descrisă mai sus. Scopul final este ca suma pătratelor numerelor din șir să ajungă la valoarea minim posibilă. Denumim costul șirului acestă valoare minimă.

Pentru a deveni și mai antipatic, Aisimok îi cere lui Sufle să calculeze aceast cost pentru mai multe subsecvențe ale unui șir dat. Costul unei subsecvențe este egal cu costul șirului definitit de subsecvența dată.

Cerința: Pentru un șir cunoscut și pentru mai multe subsecvențe date să se calculeze suma minimă a pătratelor numerelor din subsecvență după aplicare a operației descrise, de oricâte ori se consideră necesar și asupra oricăror numere din subsecvență.