Lista de probleme 4034

Părinții lui Rox au cumpărat de curând un teren care are N metri lățime și M metri lungime, pe care l-au împărţit în pătrate cu latura de un metru, denumite celule. Văzând planul terenului, lui Rox i-a venit o idee. Ea s-a decis să semene florile ei preferate în etape, pe U dintre parcele de teren. Denumirile florilor sunt litere mari ale alfabetului
englez. O parcelă este un dreptunghi inclus în teren, cu laturile paralele cu ale terenului și care conține doar celule complete.

În fiecare etapă în care Rox seamănă flori, procedează astfel: alege o parcelă pentru care reține indicii celulelor din stânga sus și dreapta jos, stabilește tipul florii pe care dorește să o semene peste tot în parcelă, apoi scrie aceste informații pe o foaie de hârtie. Documentându-se pe Internet, Rox ajunge la concluzia că apare următorul fenomen ciudat: dacă într-o celulă se seamănă același tip de floare într-un număr par de etape, semințele de acel tip pur și simplu dispar.

Când finalizează semănatul, Rox le povesteşte părinților despre isprava ei. Entuziasmați, părinții fetei îi pun mai multe întrebări de tipul ”Câte tipuri de flori au rămas semănate în celula de pe linia L și coloana C?”

Deoarece Rox a plantat foarte multe flori, ea nu poate să răspundă rapid întrebărilor părinților, așa încât vă cere ajutorul și vă va răsplăti efortul cu maxim 100 de puncte.

Algorel tocmai a avut un interviu la AlgoTech. Fiind isteţ din fire, el a reuşit să rezolve toate problemele, mai puţin una de care nu reuşeşte nicicum să se prindă cum se face. Aflând că la Iaşi are loc Concursul Urmaşii lui Moisil, s-a gândit să propună această problemă şi să ofere 100 de puncte ca recompensă celor care o rezolvă corect.

Fie un şir cu N cifre asupra căruia se poate efectua operaţia swap de maxim X ori. Prin swap se înţelege interschimbarea a două elemente din şir aflate pe poziţii vecine.

Să se determine numărul maxim care se poate obţine din şirul cu N cifre, după efectuarea a maxim X operaţii swap.

Într-un loc îndepărtat amplasat strategic, se află mai mulţi soldați identificaţi prin numere naturale nenule unice. Ordinea și disciplina militară impun aşezarea soldaților în linie la apelul de dimineață. Fiecare soldat a primit la sosirea în unitate numărul său și numerele de identificare ale camarazilor care trebuie să fie în stânga și în dreapta sa la aliniere. Excepţie fac doi soldaţi santinele care primesc doar numărul propriu de identificare şi se vor aşeza pe prima, respectiv pe ultima poziţie din linie. Uneori, unii soldaţi sunt plecați în misiuni, iar apelul de dimineaţă în unitate se face astfel: fiecare dintre cei prezenţi strigă cele trei numere primite – numărul lui, numărul camaradului din stânga lui şi al camaradului din dreapta lui, chiar dacă aceștia lipsesc.

Ei nu ştiu însă că, după un zid, stă pitită spioana Bulbuka, trimisă în recunoaștere. Ea îi ascultă şi înregistrează toate tripletele de numere care sunt strigate. După cele trei numere strigate de fiecare soldat, Bulbuka, fiind foarte inteligentă, deduce corect câte grupuri de soldaţi care și-au strigat prezența sunt până în momentul respectiv. Ea consideră că un grup este format din toţi acei soldaţi care şi-au strigat propriul număr şi care sunt aşezaţi unul lângă celălalt (dacă un soldat a strigat numărul camaradului, acesta din urmă nu este inclus în grup decât dacă a strigat şi el propriul număr).

Aflați care sunt numerele de grupuri de soldați deduse de Bulbuka în fiecare moment.

Un superstring este un şir infinit format din numere naturale nenule scrise fără spaţii între ele, începând cu 1: 1223334444...1010... (fiecare număr x apare de exact x ori).

Să se răspundă la T întrebări de forma: Ce cifră se află în superstring pe poziţia k?

Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică.

Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus.

GM are un şir de N numere naturale a1 , a2 ,…, aN , cu proprietatea ai ≤ ai+1 ≤ 2*ai pentru orice i, 1 ≤i < N. El doreşte să scrie în faţa fiecărei valori din şir un semn + sau - astfel încât valoarea S a expresiei obţinute să aibă proprietatea 0 ≤ S ≤ a1 .

Scrieţi un program care să-l ajute pe GM să determine un mod de a scrie cele N semne.

Pornind de la numărul 1,orice număr natural se poate obţine aplicând repetat în mod convenabil operaţii din cele de mai jos:

• înmulţire cu 3
• adunare cu 1
• scădere cu 1

Cunoscând numărul natural n,să se tipărească şirul de operaţii prin care se poate ajunge de la numărul iniţial 1 la numărul final n.

• înmulţire cu 3 (operaţie codificată cu 3);
• adunare cu 5 (operaţie codificată cu 5);
• adunare cu 7 (operaţie codificată cu 7);
• împărţire la 9 (operaţie codificată cu 9).

Cunoscând numărul natural n, să se tipărească şirul de operaţii prin care se poate ajunge de la numărul iniţial 1 la numărul final n.

Se dă o matrice cu numere naturale nenule, pătratică, cu liniile şi coloanele numerotate de la 1 la N. Fiecare număr din matrice reprezintă înălţimea unui pilon plasat în acea poziţie.

Putem plasa un observator “sub” matrice (adică pe o poziţie i j cu i > N şi 1 ≤ j ≤ N), de unde poate vedea în 3 direcţii:

• nord (pe coloana j);
• nord-vest (elemente din matrice de pe poziţii is,js cu i - is = j - js, dacă există astfel de elemente);
• nord-est (elemente din matrice de pe poziţii is,js cu i - is = js - j, dacă există astfel de elemente);

Se cunoaşte configuraţia matricei şi mai multe poziţii posibile ale observatorului. Să se determine, pentru fiecare poziţie, numărul de piloni pe care îi vede observatorul plasat acolo.

La ora de matematică Georgică a învăţat să evalueze expresii aritmetice. Pentru a verifica acest lucru profesorul de informatică îi propune lui Georgică să evalueze expresii aritmetice de forma:

A o₁ B o₂ C

Unde A, B, C sunt operanzi, iar o₁ şi o₂ operatori.

Valorile permise operanzilor pot fi numai termeni din şirul x₁ , x₂ , …, x_n , iar operatorii pot fi numai caracterele + (adunare) şi * (înmulţire).

Profesorul îi pune la dispoziţie lui Georgică o valoare numerică V şi îi cere să determine valorile operanzilor A, B şi C pentru care expresia are valoarea V.

Scrieţi un program, care pentru V, n, x₁ , x₂ , …, x_n şi o₁ , o₂ , date determină indicii corespunzători termenilor din şirul x₁ , x₂ , …, x_n ce corespund valorilor operanzilor A, B şi C pentru ca expresia dată să aibă valoarea V.