Lista de probleme 557

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

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.

#3245 pion1

O tablă de șah se reprezintă ca o matrice cu n linii și n coloane în care pozițiile libere au valoarea 0, iar pozițiile ocupate de piese sunt marcate prin valoarea 1.
Să se determine numărul maxim de piese pe care le poate lua un pion care pleacă de pe prima linie a tablei și vrea să ajungă pe ultima linie.

#3247 subimp1

Se citește un număr natural n. Afișați în ordine lexicografică toate submulțimile mulțimii {1, 2, ..., n} care sunt formate dintr-un număr impar de elemente.

#3242 pdi

Se dă un şir format din n numere naturale nenule. Aflaţi lungimea maximă a unui subşir al şirului dat, astfel încât oricare două elemente consecutive din subşir să nu fie prime între ele.

Să se calculeze numărul de șiruri crescătoare de lungime n, cu numere de la 1 la m, în care fiecare element apare de cel mult k ori.

#3203 SimonaH

Din perfecţiunea Simonei H. a apărut şi noţiunea de p-număr, un număr natural cu cifre nenule, ale cărui cifre le putem permuta. Să se afle suma resturilor împărţirii tuturor numerelor obţinute prin permutarea cifrelor lui n la un număr dat p.

#3235 entries

Se consideră un graf care inițial este format din P noduri izolate, etichetate de la 1 la P. Se mai consideră N intrări, unde intrare poate însemna:

  • comandă – o comandă are forma I + J, cu semnificația că în graf se adaugă muchia care unește nodurile I și J (dacă I și J erau deja unite în acel moment, nu se întreprinde nici o acțiune);
  • întrebare – o întrebare este de forma I ? J, adică se întreabă dacă în acel moment I și J sunt în aceeași componentă conexă.

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se “unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă. Scrieți un program care să răspundă la întrebările din fișierul de intrare.