Lista de probleme 752

Decodificati un mesaj folosind cifrul Four Square.

Se dă un număr natural n. Să se afișeze DA dacă numărul este prim altfel se afișează NU.

O culegere conține n probleme, dintre care m sunt probleme ușoare. În câte moduri pot fi alese k probleme, astfel încât între cele k probleme alese să existe cel puțin s probleme ușoare?

Marciuc este un băiat foarte neastâmpărat. El refuză să învețe informatică, așa că înainte de fiecare oră el pleacă pentru a explora noul său liceu. La plecare le promite colegilor lui că o să treacă pe la magazin înainte de a se întoarce în clasă, pentru a avea ce să mănânce în pauza următoare. Însă, dacă va ajunge în clasă în mai mult de T secunde, va întarza la ora așa că în acest caz va folosi o ruta directă spre clasă.

Liceul poate fi reprezentat sub forma unei matrice cu n linii și n coloane. Există 3 tipuri de celule:

• celulă liberă, pe unde băiatul poate avansa, o mutare durând o secundă;
• celulă ocupată de un zid, pe unde băiatul nu poate avansa;
• celulă în care se află o scurtătură, ce îl duce într-o secundă de la poziția, x1 y1, la poziția x2 y2 sau invers;

Fiind dat numărul n de linii și de coloane, coordonatele celulelor ocupate de zid și coordonatele scurtăturilor, se cere să se afișeze numărul de secunde în care Marciuc reușește să ajungă în clasă, trecând și pe la magazin. Dacă magazinul nu este accesibil sau daca va ajunge în clasă in mai mult de T secunde, atunci el nu va mai merge la magazin și se va afișa numărul de secunde în care acesta ajunge de la poziția lui la clasă. De asemenea, se va afișa și traseul folosit.

Se consideră n copaci de diferite înălţimi, aflaţi în linie dreaptă la distanţe egale, numerotaţi de la 1 la n. Pentru fiecare copac se cunoaşte înălţimea sa \( {H}_{i} \). Cum şi copacii simt nevoia să socializeze, fiecare dintre ei are prieteni printre ceilalţi copaci. Prietenii oricărui copac i se pot afla atât la stânga, cât şi la dreapta sa. Relaţiile de prietenie sunt definite în felul următor: pentru fiecare copac i considerăm un şir \( {d}_{1}, {d}_{2}, …, {d}_{x} \) reprezentând prietenii copacului i situaţi în dreapta sa şi un şir \( {s}_{1}, {s}_{2}, …, {s}_{y} \) reprezentând prietenii copacului i situaţi în stânga acestuia. Copacii din cele două şiruri corespunzătoare unui copac i formează împreună lista prietenilor acestuia. Şirurile corespunzătoare copacului i se definesc astfel:

1. \( {d}_{1} = i + 1 \) (dacă i = n, atunci copacul i nu are niciun prieten la dreapta sa, şirul rămânând vid). Pentru fiecare k ≥ 2, \( {d}_{k} \) este cel mai mic indice (\( 1 ≤ {d}_{k} ≤ n \)) cu proprietatea că \( {d}_{k} > {d}_{k-1} \) şi \( {H}_{{d}_{k}} > {H}_{{d}_{k-1}} \). Dacă \( {d}_{k} \) nu există, atunci lista de prieteni la dreapta ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.
2. \( {s}_{1} = i – 1 \) (dacă i = 1, atunci copacul i nu are niciun prieten la stânga sa, şirul rămânând vid). Pentru fiecare k ≥ 2, \( {s}_{k} \) este cel mai mare indice (\( 1 ≤ {s}_{k} ≤ n \)) cu proprietatea că \( {s}_{k} < {s}_{k-1} \) şi \( {H}_{{s}_{k}} > {H}_{{s}_{k-1}} \). Dacă \( {s}_{k} \) nu există, atunci lista de prieteni la stânga ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.

Determinaţi în câte moduri se pot alege 3 copaci diferiţi dintre cei n cu proprietatea că, oricum am alege 2 copaci dintre cei 3, fie aceştia copacul A şi copacul B, atunci A este prieten cu B şi B este prieten cu A.

Să se cripteze sau să se decripteze un mesaj folosind cifrul Playfair.

Se consideră o expresie corectă formată din numere naturale, paranteze rotunde și operatorii +, -, *. Să se evalueze expresia.

RAU-Gigel se gândește la un joc cu piesele de șah. El desenează o tablă de șah sub forma unei matrici pătratice de latură N și așează în fiecare dintre cele N x N celule câte o piesă de șah. Se consideră că dispune de N X N exemplare din fiecare piesă posibilă (regi, regine, ture, nebuni, cai, pioni), iar culoarea nu este relevantă. RAU-Gigel se întreabă care este numărul minim de căsuțe (celule) prin care trebuie să treacă un rege oarecare ca să ajungă la o regină oarecare. Regele se poate deplasa câte o celulă în patru direcții posibile: N, E, S, V.

Dar asta nu e tot. La începutul jocului, toți regii au 16 vieți. Atunci când RAU-Gigel mută un rege (oarecare) peste primul pion, acesta pierde o viață. Vestea bună este că, după aceea, regele respectiv poate lua oricâți pioni fără ca numărul său de vieți să fie afectat. Când ia un cal, regele pierde două vieți, dar după aceea poate lua, fără pierderi, oricâți cai. La fel se întâmplă și în cazul nebunilor, primul nebun îl costa patru vieți și, respectiv al turelor, care îl costă opt vieți.

RAU-Gigel dorește să afle ce rege să aleagă și pe ce traseu trebuie să meargă acesta către o regină oarecare, astfel încât la sfârșitul jocului să îi rămână cât mai multe vieți, iar traseul să fie cât mai scurt.

Se dă un string s. Asupra acestuia, se aplică 5 tipuri de operații:

• (1, c) – se adaugă caracterul c la începutul string-ului
• (2, c) – se adaugă caracterul c la finalul string-ului
• (3) – se șterge primul caracter al string-ului
• (4) – se șterge ultimul caracter al string-ului
• (5) – string-ul se va transforma în răsturnatul său

Să se afișeze string-ul rezultat după cele q operații.

Se consideră o expresie aritmetică formată din numere naturale și operatorii binari + (adunare), - (scădere), * (înmulțire), ^ (ridicare la putere). Să se determine forma postfixată corespunzătoare și să se calculeze valoarea expresiei.