Lista de probleme 4

Filtrare

Dificultate

Operații intrare/ieșire

Etichete

#2725 aib

Aveți la dispoziție un număr natural nenul n și o permutare a = (a[1], a[2], ..., a[n]) a mulțimii {1, 2, ..., n}. Pentru fiecare număr a[i] trebuie să determinați câte numere mai mici decât a[i] se află la stânga sa, adică în secvența a[1], a[2], ..., a[i-1].

#2012 TSM

TH, Seba, Șcuțu și Năstuț se joacă noul joc numit TSM. TSM are un sistem de tip multiplayer foarte interesant: se formează două echipe care se vor confrunta, una ce conține 4 jucători ce vor avea rol de apărători și alta ce conține un singur jucător cu rol de atacator (foarte necinstit). Mygo a auzit că cei 4 prieteni și-au făcut echipă, iar pe el nu l-au invitat, așa că decide să îi provoace la joc. Într-o rundă de joc acțiunile se petrec pe un câmp de luptă, inițial gol, iar apărătorii disting următoarele evenimente:

1 x : TH observă că Mygo a trimis pe câmpul de luptă un tanc de coeficient x și își anunță aliații.
2 K : Seba consideră că cel mai periculos tip de tanc aflat pe câmpul de luptă este cel cu al K – lea cel mai mic coeficient și îl afișează în consolă, pe un nou rând.
3 : Năstuț scrie în consolă, pe un nou rând, coeficientul cel mai mic al unui tanc aflat în momentul respectiv pe câmpul de luptă.
4 : Șcuțu trage cu tunul într-un tanc de coeficient egal cu ultimul scris de Seba în consolă și îl elimină.

#2779 cntSQ

Se dă o matrice binară (valori 0 și 1). Să se determine câte pătrate exista cu proprietatea proprietatea că acestea au pe marginea lor doar valori 1.

Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.