Lista de probleme 53

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

Se dau n șiruri de numere întregi ordonate crescător, de dimensiuni d[1], d[2], …, d[n]. Dacă se interclasează șirurile de dimensiuni d[i] și d[j] atunci se efectuează d[i]+d[j] operații și se obține un șir de dimensiuni d[i]+d[j]. Trebuie interclasate toate cele n șiruri. Pentru aceasta sunt necesari exact n - 1 pași. La fiecare pas se iau două șiruri, se interclasează și cele două șiruri se înlocuiesc cu noul șir. Scopul este să se obțină un singur șir ordonat efectuând un număr minim de operații. De exemplu, dacă n=4 și șirurile au dimensiunile 1, 5, 2 și 5, atunci se poate interclasa mai întâi 1 și 5, se fac 6 operații și rămân 3 șiruri de lungimi 6, 2, 5. Se interclasează apoi 2 cu 5 cu un cost 7 și rămân două șiruri: 6 și 7. Se interclasează aceasta două cu un cost de 13 și a rămas un singur șir. În total s-au efectuat 6 + 7 + 13 = 26 operații, dar acesta nu este numărul minim posibil. Să se determine numărul minim de operații necesare pentru a interclasa cele n șiruri.

#2150 credite

Se dă o listă de probleme, numărul de credite al fiecărei probleme precum și timpul limită de rezolvare al fiecărei probleme. Scrieți un algoritm care determină numărul maxim de credite pe care le poate obține Maria prin rezolvarea problemelor din listă.

Concursul Interjudețean de Informatică "Spiru Haret" Targu Jiu, Ed. II

Într-un laborator de analize chimice se utilizează N reactivi. Se ştie că, pentru a evita accidentele sau deprecierea reactivilor, aceştia trebuie să fie stocaţi în condiţii de mediu speciale. Mai exact, pentru fiecare reactiv x, se precizează intervalul de temperatură [minx, maxx] în care trebuie să se încadreze temperatura de stocare a acestuia.
Reactivii vor fi plasaţi în frigidere. Orice frigider are un dispozitiv cu ajutorul căruia putem stabili temperatura (constantă) care va fi in interiorul acelui frigider (exprimată într-un număr întreg de grade Celsius).

#1207 Cifre9

Maia tocmai a învăţat la şcoală să facă adunări cu numere naturale având mai multe cifre. Pentru că îi place foarte mult matematica s-a apucat să scrie pe o foaie multe numere naturale, cu una sau mai multe cifre, şi a început să le adune.

După o vreme s-a cam plictisit şi s-a gândit să afle cea mai mare sumă ce s-ar putea obţine dacă s-ar schimba între ele cifrele numerelor de pe foaie. Are însă o singură dorinţă: după ce schimbă cifrele între ele să rămână acelaşi număr de numere cu o cifră, acelaşi număr de numere cu două cifre şi aşa mai departe.

Cerinţe

Scrieţi un program care să determine

a) suma maximă ce se poate obţine schimbând între ele cifrele numerelor iniţiale;
b) un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

#1187 Roboti1

O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de dimensiuni N×M. Terenul este împărțit în parcele de dimensiune 1x1. Pe unele dintre cele N×M parcele sunt plantați copaci. Firma dorește construirea unui grandios complex comercial și este necesară defrișarea întregului teren. În acest scop sunt utilizați roboți, fiecare robot având baza un pătrat de latură L. Suprafața defrișată de fiecare robot la un moment dat este chiar aria de acoperire a robotului, L×L. Fiecare robot pătrunde prin colțul stânga sus de coordonate (1, 1), se poate deplasa doar în dreapta și în jos și poate părăsi suprafața numai prin colțul dreapta jos, de coordonate (N, M).

Cunoscând dimensiunile N, M ale terenului și coordonatele parcelelor în care sunt plantați copaci se cere:

1. Numărul minim de roboți necesari defrișării întregului teren.
2. Să se răspundă la Q interogări de forma k, unde k este un număr natural. Pentru fiecare interogare de această formă va trebui determinată latura minimă a unui robot astfel încât să fie necesari pentru defrișare cel mult k roboți.

#962 Cerc4

Se desenează n cercuri distincte în planul P, numerotate cu numerele de la 1 la n. Pentru fiecare cerc k (k∈{1,2,...,n}) se cunosc: raza cercului, rk, şi coordonatele (xk,yk) ale centrului cercului, coordonate referitoare la reperul cartezian xOy cu originea în punctul O a planului P. Din punctul O, se desenează m drepte distincte, astfel încât pentru fiecare dreaptă, dintre cele m desenate, să existe cel puţin un cerc, dintre cele n, al cărui centru să fie situat pe aceasta şi pentru fiecare cerc desenat, să existe o singură dreaptă, dintre cele m desenate, care să treacă prin centrul lui.

Să se scrie un program care să se determine:
a) numărul m de drepte distincte;
b) cel mai mare număr q de cercuri, dintre cele n, exterioare două câte două, ale căror centre sunt situate pe o aceeaşi dreaptă care trece prin punctul O, dintre cele m desenate;
c) numărul p al dreptelor distincte, dintre cele m desenate, pe care sunt situate centrele a câte q cercuri, dintre cele n, exterioare două câte două.

#1063 Arme

Vasile joacă (din nou!) jocul său preferat cu împuşcături. Personajul său are la brâu N arme, aşezate în N huse speciale, numerotate de la 1 la N. Arma din husa i are puterea pbi (1≤i≤N).

În camera armelor a găsit M arme, aşezate pe perete, în M locaţii, numerotate de la 1 la M. Pentru fiecare armă j (1≤j≤M) este cunoscută puterea sa pcj.

Vasile poate înlocui arme pe care le are la brâu cu arme aflate pe perete în camera armelor. La o înlocuire el ia arma de pe perete din locaţia j (1≤j≤M) şi o pune la brâu în husa i (1≤i≤N), iar arma din husa i o pune pe perete în locaţia j.

Scrieţi un program care să determine suma maximă a puterilor armelor pe care le va avea la brâu Vasile după efectuarea înlocuirilor.

Având la dispoziție n cifre, să se construiască k numere, astfel încât suma lor să fie minimă.

Prin fibosir(N) înţelegem un şir construit prin adăugarea la sfârşit (concatenare) a primilor N termeni nenuli ai şirul Fibonacci definit astfel:

  • F1=1
  • F2=1
  • FN = FN-1 + FN-2

Pentru N valoare naturală dată, să se elimine din fibosir-ul construit M secvenţe disjuncte de lungime K fiecare, astfel încât numărul format din cifrele rămase în fiboşir să fie maxim.

Domino este un joc care utilizează N piese speciale, de formă dreptunghiulară. Pe prima şi pe a doua jumătate a fiecărei piese este inscripţionată câte o cifră de la 1 la 9.

În timpul jocului cele N piese se așează pe tabla joc astfel încât toate cifrele să fie aliniate pe orizontală, iar jucătorul poate acţiona asupra unei piese în două moduri:

  • ELIMINARE – piesa este înlăturată de pe tabla de joc;
  • ROTIRE – piesa este rotită cu 180 grade, păstrându-și ordinea relativă în raport cu celelalte piese.

Ştiind că în timpul jocului pot fi efectuate cel mult K1 ROTIRI şi exact K2 ELIMINĂRI de piese, determinaţi cel mai mare număr care se poate forma prin scrierea în ordine, de la stânga la dreapta, a cifrelor de pe piesele rămase pe tabla de joc, în urma efectuării operaţiilor permise.