Lista de probleme 564

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

Fiind dat un șir de numere, numim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

Asupra unui şir se poate efectua următoarea operaţiune:

  1. se extrage un platou la alegere;
  2. se inserează platoul extras la pasul anterior într-o poziţie la alegere din şirul rezultat după extragere.

Să se scrie un program care citește un șir de n numere naturale și un număr k și determină:

  1. lungimea maximă a unui platou care poate să apară în şir în urma efectuării operaţiunii de mai sus de maxim k ori
  2. elementul din care este format platoul obținut după cele k operațiuni

Considerăm codificarea binară a caracterelor, în care fiecărui simbol îi revine reprezentarea pe 8 biți a codului său ASCII. De exemplu, caracterului ’A’, având codul ASCII 65, îi va corespunde reprezentarea binară 01000001.

Scrieți un program care citește din fișierul convert_submatrix.in un șir s format din n ≤ 100 caractere și construiește o matrice M cu n linii și 8 coloane, linia i a matricii reprezentând codificarea binară a caracterului de pe poziția i din șir. Se cere determinarea dimensiunii celei mai mari submatrice pătratice a lui M, care conține elemente cu aceeași valoare (fie 0, fie 1). Valoarea determinată se scrie în fișierul convert_submatrix.out.

#3294 Hmmm

Fie λ o permutare de grad și K un număr natural nenul. Să se afișeze toate soluțiile ecuației \({x}^{K}=λ\) în ordine lexicografică.

Orice șir de caractere poate fi descompus în palindromuri într-unul sau mai multe moduri. Dându-se un șir de caractere format numai din litere mici, să se determine numărul de moduri de a descompune șirul în palindromuri.

#3283 Lee1 C++

Se dă o matrice cu n linii și m coloane. Pentru k poziții date, se cere să se determine drumul de lungime minimă care pleacă de la poziția i1 și j1 și trece prin toate cele k poziții (nu contează în ce ordine), ajungând în final în poziția i2 si j2.

Fie un șir a = a1, a2, …, aN de numere naturale, nu neapărat distincte, cuprinse între 1 și N. Fie de asemenea două numere naturale x și y. Se definește operația transform(i) astfel: se determină valoarea w = 1 + (x * i + y * ai) mod N, apoi toate elementele egale cu ai din secvența ai, ai+1, …, aN își modifică valoarea în w. După fiecare operație de tip transform se calculează suma elementelor șirului obținut. Să se determine suma maximă care s-a obținut în șirul a efectuând pe rând asupra șirului operațiile transform(1), transform(2), …, transform(N).

Maria este mare amatoare de cumpărături. Ea și-a cumpărat în decursul mai multor zile de la magazinul său preferat N articole de îmbrăcăminte și încălțăminte cu preturile s1, s2, …, sN lei. Iulia, prietena Mariei, observând cumpărăturile, i-a spus:
- Puteai economisi mulți bani. Nu ai văzut promoțiile magazinului? Dacă ai fi cumpărat două produse deodată, cel mai ieftin din cele două l-ai fi cumpărat la jumătate de preț. Iar dacă ai fi cumpărat trei produse deodată, ai fi primit pe cel mai ieftin din cele trei gratuit!
Maria și Iulia s-au decis să afle care ar fi fost suma minimă cheltuită pentru a achiziționa în aceeași ordine cele N produse, dar grupând câte un produs, câte două sau câte trei. Pentru că cele două fete nu se descurcă așa de bine la informatică, ele te roagă să le ajuți să determine care este această sumă minimă.

Există N candidați la alegerile prezidențiale. Fiecare dintre cei N candidați știe exact cu cine va vota. O persoană poate vota o singură altă persoană (se poate vota și pe sine). Scopul tău este să creezi confuzie între candidați. Pentru asta, ai dreptul să le interzici la cel mult K dintre candidați să participe. Atunci când un candidat este eliminat, toți candidații care ar fi votat cu el votează cu persoana cu care ar fi votat candidatul eliminat (deoarece au încredere în decizia sa). Dacă cel eliminat ar fi votat cu sine sau era INDECIS, toți cei care ar fi votat cu el devin INDECIȘI. Pentru fiecare K de la 1 la N, se cere numărul minim de candidați “deciși” pe care îi putem avea dacă am elimina K dintre candidați.

Reședința Larei a fost invadată de șobolani. Putem descrie reședința Lorei ca un arbore cu N noduri având rădăcina în nodul 1. Inițial niciun nod nu este infestat. Diverse evenimente se pot întâmpla pe rând, fiecare eveniment fiind de următoarele patru tipuri:

  • 1 X – nodul X devine infestat
  • 2 X – Lora vrea să elimine șobolanii din drumul de la nodul 1 la nodul X (inclusiv) folosind ultrasunete în toate nodurile simultan. Dacă se folosesc ultrasunete într-un nod infestat, șobolanii de acolo se împrăștie în toate nodurile vecine unde nu se folosesc ultrasunete, acestea devenind infestate. Nodurile unde se folosesc ultrasunete nu mai sunt infestate. După ce șobolanii au plecat, ultrasunetele se opresc, adică nodurile curățate vor putea fi infestate iar în evenimentele ulterioare.
  • 3 X – Lora angajează profesioniști să curețe nodul X și fiii săi. Ca urmare, X și fiii direcți nu mai sunt infestați.
  • 4 X – Lora ar vrea să știe numărul total de noduri infestate din subarborele cu rădăcina X.

Ajutați-o pe Lora să scrie un program care prelucrează fiecare eveniment și determină răspunsurile la evenimentele de tip 4.

#3237 GCDnot1

Se dau m şi n numere naturale nenule. Să se determine două numere naturale a şi b astfel încât c.m.m.d.c.(a+i,b+j)>1 pentru orice i=0,m-1 şi orice j=0,n-1.