Lista de probleme 1987

Filtrare

#2069 roboti2

Ștefan a împlinit 15 ani. Fiind un pasionat membru al Clubului de Robotică, familia i-a dăruit de ziua lui foarte mulți roboți, fiecare dotat cu o armă de o anumită putere. El a așezat toți roboții în jurul său, pe circumferința unui cerc imaginar, în sensul acelor de ceasornic. Aceste dispozitive inteligente pot comunica între ele, unindu-și puterile armelor.

Cunoscând numărul de roboți, precum și puterea fiecăruia, să se scrie un program care determină:
1. Dimensiunea celei mai lungi secvențe de roboți pentru care puterile armelor lor formează un șir strict crescător.
2. O aranjare a roboților pe cerc, astfel încât suma produselor de câte două puteri vecine să fie maximă. Dacă există mai multe modalităţi de aranjare astfel încât să se obţină aceeaşi sumă maximă, se va determina cea minimă din punct de vedere lexicografic.

Olimpiada județeană de informatică, 2017

#2064 tripas

Se consideră aranjamentul piramidal de numere cunoscut și sub denumirea de triunghiul lui Pascal. În vârful și pe marginile laterale ale piramidei se află numărul 1. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra. Definim un tripas(r,c,L) ca fiind un triunghi echilateral de numere din interiorul triunghiului lui Pascal, pentru care se precizează poziția (r, c) a vârfului și L, lungimea laturii (r=rând, c=coloană, L=lungime latură). Exemplu: tripas(3,1,4) – reprezintă triunghiul de numere cu vârful poziționat pe rândul al treilea, primul element și care are lungimea laturii de 4 elemente, adică numerele (1), (1,3), (1,4,6), (1,5,10,10) – scrise de sus în jos și de la stânga la dreapta. Pe figura de mai sus, tripas(3,1,4) are elementele încadrate în dreptunghiuri. Notăm cu S suma elementelor unui tripas(r,c,L).

Lot informatica, Alexandria, 2017

În Japonia trenurile pot suporta un număr de vagoane și marfă. Toate vagoanele au încărcături egale. Calculați încărcătura din fiecare vagon.

#1748 Cursă C++

Costică este alergător la un maraton. El parcurge un traseu sub forma unei matrice cu n linii şi m coloane linie cu linie şi pe fiecare linie, de la stânga la dreapta. Dacă Costică întâlneşte un număr prim, el este penalizat, fiind trimis pe linia şi coloana anterioară, iar dacă acesta întâlneşte un număr perfect, poate avansa pe linia şi coloana următoare. Dacă mişcarea pe linie şi pe coloană depăşeşte limitele matricei, atunci se va efectua numai mişcarea care nu trece de aceste limite sau nu se va efectua nici o mişcare. Afişaţi timpul t în care parcurge Costică traseul.

2 numere puse în aşa fel încât rezultatul aX – aY să fie divizibil cu n. X și Y sunt numerele de pe inelele porumbeilor pe care îi va trimite la concurs.

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

#2058 Submat

Se consideră o matrice A având N linii și N coloane. Elementele acesteia aparțin mulțimii {0,1,2}. Pe fiecare linie și pe fiecare coloană valorile elementelor sunt dispuse crescător.

Fie două elemente din matrice situate pe linia i1 și coloana j1 respectiv i2 și j2,unde i1≤i2 și j1≤j2. O submatrice a lui A, având colțurile stânga-sus şi dreapta-jos în (i1,j1) și (i2,j2), este formată din toate elementele situate pe linii cuprinse între i1 și i2, inclusiv, și coloane între j1 și j2, inclusiv. Numim submatrice constantă o submatrice a matricei A, având toate elementele egale.

Realizați un program care determină numărul maxim K de elemente pe care îl are o submatrice constantă a lui A și numărul submatricilor constante formate din K elemente.

Să ne imaginăm faptul că la un anumit liceu există doar două clase per generație: una de Real și una de Uman. În prezent au loc înscrierile pentru clasa a IX-a. Cele două clase au fiecare câte M locuri disponibile, atât la Real, cât și la Uman. Dacă lista de elevi înscriși la o anumită clasă conține mai mult de M elevi, vor fi admiși acei M elevi care au notele cele mai mari. Ambele clase au deja M elevi înscriși, iar pentru fiecare se știe nota cu care a fost înscris la clasa respectivă.

Mai există însă N elevi, singurii încă neînscriși, care sunt privilegiați în acest proces (fiindcă au terminat gimnaziul la acest liceu). Privilegiul lor constă în următorul fapt: ei se pot înscrie acum, după ce înscrierile publice au fost încheiate, și se cunosc notele de înscriere la ambele clase. Fiecare din cei N elevi are câte două note: nota cu care ar fi înscris la Real și nota cu care ar fi înscris la Uman (acestea pot fi diferite, deoarece examenele de admitere de la cele două clase diferă). Fiecare din cei N elevi va alege să se înscrie în maxim o clasă. Ei își vor coordona alegerile astfel încât să maximizeze numărul de elevi admiși. Deoarece calculele devin destul de complicate, aceștia s-ar putea folosi de ajutorul vostru. Ei doresc răspunsul la două întrebări.

(1) Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă se pune restricția suplimentară ca toți elevii privilegiați admiși să fie admiși la aceeași clasă?
(2) Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă aceștia se pot înscrie la clase diferite?

#2056 Popcorn C++

Cu toții știm că popcornul este o adevărată delicatesă culinară. În pregătirile tale pentru lotul de anul acesta (și pentru petrecerile de după), ai făcut comandă de N tipuri de floricele de porumb pentru microunde. Fiecare tip are asociate 3 valori:

  • A[i] = Timpul (în secunde) la care orice floricică de acel tip “pocnește”;
  • B[i] = Timpul (în secunde) la care orice floricică de acel tip “se arde”;
  • C[i] = Cantitatea (în floricele) a respectivului tip.

Mai ai la dispoziție M pungi pentru floricele de unică folosință de capacitate foarte mare (practic, infinită) și un cuptor cu microunde. Cum, bineînțeles, nimănui nu îi plac floricelele nefăcute sau cele arse, îți dorești să le partiționezi convenabil în cele M pungi și apoi să le introduci pe rând în cuptorul cu microunde, setându-i un timp de preparare prep[i] corespunzător, astfel încât după cele M tranșe să obții cât mai multe floricele comestibile.

Formal, o floricică de tipul i introdusă în punga j , setată la timpul (în secunde) de preparare prep[j] este comestibilă dacă și numai dacă A[i] ≤ prep[j] < B[i].

Fiind date cele N tipuri de floricele și numărul de pungi disponibile, trebuie să găsești o partiție convenabilă și timpii optimi de preparare pentru fiecare pungă, astfel încât la final să obții numărul maxim de floricele comestibile, pe care să îl afișezi în fișierul de ieșire. Prea ușor!

#2055 ace

Pe o zonă în formă de dreptunghi cu laturile de lungimi N și M se găsesc NxM pătrate de latură 1. În centrul fiecărui pătrat se găsește înfipt câte un ac de grosime neglijabilă. Fiecare ac este descris de înălțimea sa. Această zonă se poate reprezenta ca un tablou bidimensional de dimensiuni N și M, iar fiecare element din matrice reprezintă înălțimea (număr natural nenul) fiecărui ac. În centrul pătratului (N,M) există o cameră de luat vederi de ultimă generație, mobilă, care se poate roti cu 3600 în orice plan, situată la nivelul solului. Dimensiunile camerei sunt neglijabile.

Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial . Acul (1,4) nu se vede pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece (4,2) și (4,1) sunt acoperite total de (4,3). Pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza acului (2,2), care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).

1. Câte ace vede camera de luat vederi dacă se poate roti în plan vertical, doar în direcțiile N și V?
2. Câte ace vede camera de luat vederi dacă se poate roti în orice plan și în orice direcții?

#2045 Faleza

Acum iarna s-a terminat și, apropiindu-se sezonul de vară, gospodarii din orașul de pe malul fluviului doresc să pregătească faleza pentru a primi cum se cuvine turiștii. Faleza este sub formă dreptunghiulară cu lungimea de n metri și lățimea de 2 metri. În toamnă ea era pavată cu 2*n dale pătrate cu latura de un metru, lipite una de alta și care acopereau complet zona falezei. În urma iernii grele, unele dale s-au deteriorat și acum se dorește înlocuirea lor.Cum de multe ori oamenii fac treaba doar “pe jumătate”, gospodarii au hotărât să cheltuie cât mai puțin pentru reamenajarea falezei, așa că au decis că nu trebuie neapărat să înlocuiască toate dalele deteriorate, ci doar un număr minim dintre acestea astfel încât să fie posibil să se parcurgă faleza de la un capăt la altul pășind doar pe dale bune (nedeteriorate). De pe o dală pe alta se poate păși doar dacă ele au o latură comună.

Scrieţi un program care să determine numărul minim de dale deteriorate ce trebuie înlocuite astfel încât faleza să
poată fi parcursă de la un capăt la altul.