Lista de probleme 649

Regina stupului este plecată, iar cele N albinuțe nou născute trebuie hrănite. Maya este albina care trebuie să îndeplinească această sarcină. Maya își face un plan pentru a putea acționa. Pentru fiecare albinuță, Maya pornește dintr-o celulă inițială ce conține cantitatea de miere necesară și se deplasează din celulă în celulă, până la albinuța pe care o va hrăni.
Un fagure este format din coloane numerotate cu litere mari ale alfabetului englez de la A la Z, iar poziția fiecărei celule de pe o coloană este identificată prin valori 1, 2, 3, 4, 5, … de jos în sus, ca în figură. Fiecare celulă a fagurelui are formă hexagonală. Dintr-o celulă se poate ajunge în cele 6 celule vecine, prin deplasarea în direcțiile: 1 – sus, 2 – dreapta sus, 3 – dreapta jos, etc. Fagurele este circular, astfel după coloana Z urmează, spre dreapta, coloana A, iar înainte de coloana A se află, la stânga, coloana Z. Știind care sunt adresele celulelor din care va pleca Maya, se cere:
1. Să se afișeze coloanele care conțin cele mai multe celule inițiale.
2. Cunoscând, în plus, secvențele de mutări pe care le va executa Maya, pentru a ajunge la fiecare albinuță, se cer adresele celor N celule destinație.

Sa se afiseze cate cifre are \({a}^{b}\)

Numim poligon drept un poligon cu laturile consecutive perpendiculare și lungimile laturilor numere naturale nenule. Un poligon drept cu n laturi este descris de un șir de n numere întregi nenule în care lungimile laturilor sunt date de valoarea absolută a numerelor din șir, iar semnul precizează poziția laturilor, un număr pozitiv însemnând latură spre dreapta sau în sus față de extremitatea laturii precedente, iar un număr negativ însemnând latură în jos sau spre stânga față de extremitatea laturii precedente; de exemplu șirul 1, 1, -1, -1 reprezintă un pătrat de latură 1 (prima latură spre dreapta, a doua în sus, a treia spre stânga, a patra în jos). Vom considera laturile ca fiind orizontale sau verticale, prima latură enumerată fiind orizontală spre dreapta, dacă numărul este pozitiv, sau spre stânga, dacă numărul este negativ.
Se dau unul sau mai multe șiruri de numere întregi nenule.
1. Să se stabilească, pentru fiecare dintre ele, dacă reprezintă un poligon drept.
2. Știind că șirurile date reprezintă poligoane drepte, să se determine aria fiecăruia.

Două personaje ale căror nume se vor da în datele de intrare (momentan îi numim Bossanip și Dicsi) își petrec nopțile prin discoteci. Toată lumea știe că Bossanip este membru V.I.P în toate discotecile din lume și Dicsi profită mereu de celebritatea prietenului său. Ajuns pe meleaguri străine, Dicsi s-a confruntat cu o problemă foarte mare. Cum intră la V.I.P când este pe cont propriu? Astfel, Dicsi s-a apucat de infracțiuni precum furtul de identitate. Dicsi dorește să permute literele din numele lui (să găsească o anagramă a propriului nume) astfel încât noul nume să difere prin exact K poziții de numele lui Bossanip. Mai mult, dorește ca această anagramă să fie minimă lexicografic. Dacă reușește, este posibil să se dea drept Bossanip și să intre și el ca membru V.I.P.

Roboțelul WALL-E este captiv într-un labirint dreptunghiular de dimensiuni N x M. Analizând harta, WALL-E constată că are de-a face cu un labirint extrem de sofisticat. El reușește să identifice următoarele tipuri de celule:

• W – celula unde, la început, se află WALL-E,
• E – celula ‘EXIT’ care poate fi accesată de WALL-E și care îl poate teleporta pe acesta instantaneu în afara labirintului, într-un loc sigur,
• . – celule libere, care pot fi accesate de WALL-E,
• # – celule de tip zid, care NU pot fi accesate de WALL-E,
• + – celule de tip ușă, care pot fi accesate de WALL-E, dar continuarea deplasării la o celulă vecină se poate face doar după o așteptare de exact T secunde,
• P – celule de tip portal, care îl teleportează pe WALL-E instantaneu, la întâmplare, într-una dintre celelalte celule de tip portal. Dacă WALL-E accesează o celulă (x1, y1) de tip portal, atunci el va fi instantaneu teleportat la o altă celulă (x2,y2) de tip portal, iar mai departe el se va deplasa numai într-o celulă vecină cu (x2,y2) (nu poate sta pe loc)

Comportamentul haotic al portalurilor îl îngrijorează pe WALL-E, astfel că își propune să afle care este numărul minim de secunde în care, cu certitudine, el va putea părăsi labirintul. Dacă nu se poate determina cu certitudine acest lucru, sau dacă WALL-E nu poate părăsi labirintul, răspunsul va fi -1.

Avem o clasă cu N elevi inventivi. Pentru fiecare dintre ei se cunoaște un coeficient de atitudine reprezentat printr-un număr natural nenul vk. Interacțiunile din cadrul grupului de elevi al clasei produc efecte secundare importante și conducerea școlii a definit o mărime scalară numită indicator de pericol care măsoară influența pe care un elev o are asupra celorlalți elevi din clasă. Indicatorul de pericol asociat elevului k, 1 ≤ k ≤ N, se obține calculând cel mai mare divizor comun dk,j pentru fiecare pereche (vk, vj), 1 ≤ j ≤ N, j ≠ k și apoi însumând valorile calculate. Să se calculeze, pentru fiecare elev, indicatorul de pericol asociat lui.

Se dau N și K. Se cere să se determine pentru a K-a permutare în ordine lexicografică a șirului 1, 2, 3, …, N câte poziții p există astfel încât nici p și nici valoarea de pe poziția p nu conțin cifra zero.

Arheologii au găsit un artifact care pare să conțină o ecuație matematică, care folosește simbolurile unei scrieri necunoscute încă. O serie de ipoteze au început să apară, așa că ei își propun să rezolve ecuația în vederea descifrării simbolurilor. Ecuația conține N + M termeni, fiecare termen reprezentând un număr codificat printr-o înșiruire de simboluri, care au fost înlocuite cu literele mari ale alfabetului englez, de la A la Z. Se presupune că suma primelor N numere trebuie să fie egală cu suma ultimelor M numere. De asemenea, fiecare literă corespunde unei cifre de la 0 la 9, iar două litere diferite sunt asociate cu două cifre diferite. Se cere să se afle câte soluții distincte admite ecuația găsită.

Casa de Modă Venus a decis să se modernizeze şi, începând cu 1 ianuarie 2020 ora 00:00, l-a angajat pe robotul Vasile. Vasile poate executa orice comandă în exact T ore, indiferent de complexitatea acesteia (mai exact, dacă Vasile începe să lucreze la comandă în momentul x, la momentul x+T ore comanda va fi gata de predare). Foarte încrezătoare în calitățile robotului Vasile, Casa de Modă Venus a lansat o campanie publicitară cu sloganul “Dacă am întârziat, primești produsul comandat gratis!”. Campania și-a atins scopul, ca urmare Casa de Modă a primit deja N comenzi pentru întreg anul 2020. Pentru fiecare comandă sunt specificate valoarea acesteia, precum și data și ora până la care produsul comandat trebuie să fie gata de predare. Dacă Vasile predă produsul exact la data și ora specificată în comandă (sau înainte) el încasează valoarea comenzii. Dacă nu, el tot trebuie să execute comanda respectivă, dar nu va primi suma reprezentând valoarea ei.
Deși lucrează fără nicio pauză, Vasile estimează că este posibil să nu poată preda la timp toate comenzile, dar își planifică lucrul, astfel încât pierderea să fie minimă (adică suma valorilor comenzilor care nu vor fi predate la timp să fie cât mai mică). Numim planificare optimală succesiunea în care Vasile trebuie să execute cele N comenzi, astfel încât pierderea să fie minimă.
Scrieți un program care, cunoscând informațiile referitoare la cele N comenzi, determină pierderea minimă, precum și o planificare optimală.

La nașterea unei fete în tribul Ragan Ama părinții trebuie să îi găsească cel mai frumos nume posibil. Sunt considerate nume frumoase doar anagramele unui cuvânt care, în limba lor, înseamnă “frumoasă ca roua dimineților, blândă ca mângâierea vântului printre frunze, binecuvântată de lumina soarelui și a lunii”.
Viața fetei va sta sub o stea norocoasă dacă numele său este cel mai mic din punct de vedere lexicografic, diferit de al oricăreia dintre fetele din trib. Fiindcă astăzi în trib s-a născut o fetiță, scrieți un program care, cunoscând numele fetelor din trib, rezolvă următoarele cerințe:
1. afișează numele pe care părinții ar trebui să i-l dea fetei pentru ca viața să-i stea sub o stea norocoasă;
2. determină câte nume frumoase, diferite de cele ale fetelor din trib, există.