Lista de probleme 888

Un gospodar are N iepuri (pe care i-a numerotat de la 1 la N) și foarte mulți morcovi. Ce e mai deosebit în această gospodărie este că iepurii sunt organizați ierarhic, în funcție de vârstă, autoritate și nevoile nutriționale. Astfel, fiecare iepure are exact un șef direct (exceptându-l pe Rilă Iepurilă, care este șeful cel mare, șeful tuturor iepurilor). Orice iepure poate avea 0, 1 sau mai mulți subordonați direcți. Orice iepure-șef va mânca cel puțin un morcov mai puțin decât fiecare dintre subordonații săi direcți. Gospodarul nu se poate hotărî câți morcovi să dea fiecărui iepure și ar vrea să știe în câte moduri poate împărți morcovi la iepuri știind că fiecare iepure poate să mănânce minim un morcov și maxim K morcovi. Scrieți un program care calculează numărul de posibilități modulo 30011 de a împărți morcovi la cei N iepuri știind că orice iepure poate mânca între 1 și K morcovi și trebuie să mănânce cu cel puțin un morcov mai puțin decât fiecare dintre iepurii care îi sunt subordonați direcți.

Anul acesta se organizează prima ediție a Olimpiadei Pluridisciplinare pentru Centrele de Excelență, PluriCEX. Fiecare Centru de Excelență din țară va trimite la concurs o echipă formată din k membri (toți participanți la Centrul de Excelență). Echipa va trebui să rezolve probleme interdisciplinare, disciplinele vizate fiind cele de la Centrul de Excelenţă (D discipline, pe care le vom considera numerotate de la 1 la D).
Directorul CEX Iași a făcut o listă cu primii n cei mai buni elevi de la CEX, apoi a numerotat elevii de la 1 la n, în ordinea apariției lor în listă. Pentru fiecare elev, directorul a notat disciplinele la care el participă la CEX. Scrieți un program care să determine toate echipele ce pot fi formate din k dintre cei n elevi de pe lista directorului, cu condiția ca pentru fiecare disciplină să existe în echipă cel puțin un membru care să studieze la CEX disciplina respectivă.

Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri X și Y ca fiind un lanț de lungime minimă care are ca extremități vârfurile X și Y. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului. Fiind dat un graf neorientat conex cu N vârfuri etichetate cu numerele de ordine 1, 2, …, N și două vârfuri ale sale notate X și Y (1 ≤ X, Y ≤ N, X≠Y ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre X și Y.

În Roma antică există n așezări senatoriale distincte, câte una pentru fiecare dintre cei n senatori ai Republicii. Așezările senatoriale sunt numerotate de la 1 la n, între oricare două așezări existând legături directe sau indirecte. O legătură este directă dacă ea nu mai trece prin alte așezări senatoriale intermediare. Edilii au pavat unele dintre legăturile directe dintre două așezări (numind o astfel de legătură pavată stradă), astfel încât între oricare două așezări senatoriale să existe o singură succesiune de străzi prin care se poate ajunge de la o așezare senatorială la cealaltă.
Toţi senatorii trebuie să participe la şedinţele Senatului. In acest scop, ei se deplasează cu lectica. Orice senator care se deplasează pe o stradă plăteşte 1 ban pentru că a fost transportat cu lectica pe acea stradă.

La alegerea sa ca prim consul, Cezar a promis că va dota Roma cu o lectică gratuită care să circule pe un număr de k străzi ale Romei astfel încât orice senator care va circula pe străzile respective, să poată folosi lectica gratuită fără a plăti. Străzile pe care se deplasează lectica gratuită trebuie să fie legate între ele (zborul, metroul sau teleportarea nefiind posibile la acea vreme).

În plus, Cezar a promis să stabilească sediul sălii de şedinţe a Senatului într-una dintre aşezările senatoriale aflate pe traseul lecticii gratuite. Problema este de a alege cele k străzi şi amplasarea sediului sălii de şedinţe a Senatului astfel încât, prin folosirea transportului gratuit, senatorii, în drumul lor spre sala de şedinţe, să facă economii cât mai însemnate. În calculul costului total de transport, pentru toţi senatorii, Cezar a considerat că fiecare senator va călători exact o dată de la aşezarea sa până la sala de şedinţe a Senatului.

Scrieţi un program care determină costul minim care se poate obţine prin alegerea adecvată a celor k străzi pe care va circula lectica gratuită şi a locului de amplasare a sălii de ședință a Senatului.

Fie a și b două numere naturale nenule. Scrieți un program care determină numărul de numere naturale formate din exact a cifre care au fiecare produsul cifrelor egal cu b și afișează în fișierul de ieșire restul împărțirii valorii determinate la numărul 9973.

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ă.

Zoli joacă cu un labirint de dimensiune N x N, format din camere de dimensiune 1 x 1, inițial toate inaccesibile. Auzind că Zoli este mare informatician, Dănutz și D’Umbră au decis să îl pună la încercare, după cum urmează:

1 x y: Dănutz transformă camera inaccesibilă (x, y) într-una accesibilă.
2 x1 y1 x2 y2: D’Umbră îl întreabă pe Zoli care este numărul minim de camere ce trebuie traversate pentru a ajunge din camera accesibilă (x1, y1) în camera accesibilă (x2, y2).

Principala misiune a unei expediții științifice este de a studia evoluția vieții pe o planetă nou descoperită. În urma studiilor efectuate, cercetătorii au asociat fiecărui organism viu descoperit pe acea planetă un cod caracteristic. Codul caracteristic este un număr natural de maximum 200 de cifre zecimale nenule. De asemenea, cercetătorii au observat că pentru orice organism viu de pe planetă, codurile caracteristice ale strămoșilor săi pe scara evoluției se pot obține prin ștergerea unor cifre din codul caracteristic al organismului respectiv, iar un organism este cu atât mai evoluat cu cât codul său caracteristic are o valoare mai mare.

Date fiind codurile caracteristice ale două organisme vii diferite, scrieți un program care să determine codul caracteristic al celui mai evoluat strămoș comun al lor.

În fața palatului Prințesei Mofturoase se află n pețitori așezați la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre prețioase pe care dorește să le ofere prințesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, prințesa a decis să-i determine ca n-1 dintre ei să renunțe în chip pașnic, pețitorul rămas devenind alesul prințesei (indiferent de numărul de pietre prețioase deținute de acesta). Doi pețitori vecini la coadă se pot înțelege între ei astfel: cel care are mai puține pietre prețioase pleacă de la coadă primind de la celălalt un număr de pietre astfel încât să plece acasă cu un număr dublu de pietre față de câte avea. Dacă doi pețitori au același număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său. Un pețitor se poate înțelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui pețitor, toți cei din spatele lui avansează.

Fie P numărul de pietre prețioase pe care le are pețitorul care va deveni alesul prințesei. Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.

Definim o permutare dublă de ordin n ca fiind un șir format din primele 2n numere naturale nenule: (a[1], a[2], ... , a[n], a[n+1], a[n+2], ... , a[2n]). Această permutare dublă este de trei ori în creștere, dacă sunt adevărate următoarele trei proprietăți:

1. secvența formată din primele n elemente este crescătoare: a[1]<a[2]< ... < a[n]
2. secvența formată din ultimele n elemente este crescătoare: a[n+1]<a[n+2]< ... < a[2n]
3. perechile ordonate formate din elementele aflate pe poziții identice ale celor două secvențe sunt de asemenea în ordine crescătoare: a[1]<a[n+1], a[2]<a[n+2], ... , a[n]<a[2n].

Pentru simplificare în continuare permutarea dublă de trei ori în creștere se va numi permutare. Vom considera toate permutările de ordin n ordonate lexicografic, numerotate începând cu 1.

Există două tipuri de întrebări:

1. Ce permutare se află pe o poziție dată?
2. Pe ce poziție se află o permutare dată?

Să se răspundă corect la un set de întrebări.