Lista de probleme 6

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

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.

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.

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.

Avem N persoane notate cu etichetele 1, 2, …, N, într-o ordine oarecare și o scară cu N trepte. Persoanele sunt așezate în șir indian, cu fața spre locul unde se află scara. Treptele scării sunt inițial neocupate. În mod repetat persoana aflată la acel moment la capătul din dreapta al șirului se poziționează pe scară pe prima treaptă neocupată, iar fiecare dintre persoanele aflate pe treptele inferioare coboară de pe scară și se repoziționează la capătul din dreapta al șirului, începând cu cea de la prima treaptă a scării. Acțiunea se oprește atunci când sunt ocupate toate treptele pe scară. Se cere să se afișeze etichetele persoanelor în ordinea în care acestea sunt așezate pe scară la final.