Lista de probleme 160

Se dă un limbaj format din N cuvinte și un text criptat format din M cuvinte. Spunem că un cuvânt se permută după un șir $x_1,x_2,\dots ,x_K$ dacă prima literă se permută cu $x_1$, a doua cu $x_2$, …, iar ultima cu $x_K$.
De exemplu, după șirul 1 5 6, “abc” devine “bgi”. Permutarea se face în ordinea literelor mici din alfabetul englez. Dacă o literă ar trece de finalul alfabetului, aceasta îl reia și apoi permută și litera următoare cu 1.
În cazul în care ultima literă trece de finalul alfabetului, atunci cuvântul devine invalid. De exemplu, “zza” permutat după șirul 1 2 3, devine “ace”. (adunarea se face cu transport pornind de la stânga). Dacă “zzz” s-ar permuta după șirul 1 2 3, ar deveni invalid. Cele mai “semnificative” litere sunt de la dreapta la stânga.
Vrem să decriptăm textul, folosind mai multe variante de șiruri pe care le considerăm valabile. Cel mai bun șir de decriptare este acela pentru care numărul de cuvinte din textul criptat care se găsesc, după operație, în limbaj, este maximal.

Pentru că este un bun sportiv și poate alerga constant cu x metri pe secundă, Gigel și-a propus să câștige competiția semarun. Această competiție începe la momentul 0 și constă în parcurgerea unui traseu de n metri, ce conține k semafoare. Deoarece Gigel știe că nu este important să ajungă primul la final, ci să parcurgă traseul într-un timp cat mai scurt, vă roagă să îl ajutați cu următoarea cerință: determinați momentele de timp pe care Gigel ar putea sa le aleagă pentru a începe parcurgerea traseului astfel încât să nu se oprească la niciun semafor și atunci când ajunge la final să nu fi trecut mai mult de s secunde de la începutul competiției (momentul 0).

N soldați, numerotați de la 1 la N, sunt prinși într-o ambuscadă. Asupra lor se execută M atacuri de tun. Atacurile afectează nu doar un soldat, ci un interval de soldați, provocând fiecăruia dintre aceștia o anumită pierdere (damage). De exemplu, atacul (3,7,5) afectează soldații 3,4,5,6,7 cu 5 damage. La început, toți soldații au V vieți. Câți soldați rămân în viață după cele M atacuri?

Se dau patru numere naturale a, b, k1, k2. Determinați numărul de submulțimi formate din două elemente
numere naturale x și y, cu x și y cuprinse între a și b, astfel încât cel mai mare divizor comun al lui x și y să fie multiplu de k1 sau multiplu de k2.

După consolidarea structurii de rezistență, a venit vremea refacerii zidului cetății. Acesta avea lungimea de L unități și înălțimea de H unități. El deteriorându-se în timp, acum nu mai este dreptunghiular ci, pe fiecare din cele L unități de lungime mai există $V_i)$ unități, de material, așezate una peste alta și sprijinite pe fundație, deci până la înălțimea $V_i)$ unități. Se dorește, evident, acoperirea zonelor rămase așa încât zidul să ajungă dreptunghiular, cu înălțimea de H unități pe fiecare din cele L unități de lungime.

Se dispune de bucăți de material, dreptunghiulare, cu o dimensiune de o unitate. Așadar putem spune că bucățile sunt de dimensiuni 1 X B(1 ≤ B ≤ L) și pentru fiecare valoare B dispunem de oricâte bucăți(să le numim de tipul B). Pentru ca zidul să fie stabil, bucățile trebuie să fie dispuse orizontal, adică una de dimensiune 1 X B va ocupa B unități pe lungime și o unitate pe înălțime. Se mai cunoaște că bucățile de același tip B au aceeași culoare și diferită de culoarea bucăților de alte tipuri. Pentru a fi zidul frumos, trebuie ca la aceeași înălțime față de fundație, să se folosească bucăți de material de aceeași culoare. Determinați numărul minim de bucăți necesare refacerii zidului.

Scrieți un program care citește un număr natural N, valorile matricei și pozițiile inițiale ale jucătorilor și afișează la ieșire răspunsul la Q întrebări de forma: “Care este primul moment de timp după care avem cel puțin P celule colorate în matrice?”. În cazul în care pentru o întrebare nu se vor putea colora P celule libere (după oricât de mult timp), se va afișa ca răspuns pentru acea întrebare valoarea -1.

Costel este pasionat de circuitele logice. El are la dispoziție două tipuri de circuite logice simple: circuit
ȘI, respectiv circuit SAU. Circuitele logice simple au două intrări și o ieșire.
Pentru un CLP dat, cu N nivele și pentru K șiruri de biți date la intrarea circuitului, să se determine, pentru fiecare șir, valoarea calculată la ieșirea din circuit. Pentru un CLP dat, cu N nivele și cunoscând valoarea obținută la ieșire (0 sau 1), să se determine numărul șirurilor de biți distincte ce pot fi date la intrare pentru a se obține valoarea specificată la ieșire. Rezultatul poate fi un număr foarte mare, de aceea el se va afișa modulo 666013.

Tommy este un motan alintat care adoră să se plimbe prin orice tunel. De aceea, stăpânii lui i-au construit o nouă jucărie, formată din N tuneluri interconectate (etichetate cu numerele distincte de la 1 la N. Toate tunelurile au aceeași lungime, sunt formate din M elemente unitare identice (numerotate cu numerele distincte de la 1 la M) și au ieșiri la ambele capete. Conectarea dintre două tuneluri alăturate se face printr-un element unitar numit pasaj.

Pentru a fi mai provocator, stăpânii motanului plasează în ultimul element unitar al ultimului tunel o recompensă.

Ajutați-l pe Tommy să ajungă cât mai repede la recompensă respectând regulile jocului!

Fie x un număr real subunitar cu cel mult 9 zecimale și N un număr natural. Să se determine fracția ireductibilă $\frac{a}{b}$ cu proprietățile:

• aproximează cel mai bine numărul real x, adică expresia $|x-\frac{a}{b}|$ are valoare minimă
• 1 ≤ b ≤ N

Dându-se N puncte laticiale, care este distanța Manhattan de buget minimă dintre două puncte de coordonate a b respectiv x y cu proprietatea că a-y >= x-b?