Lista de probleme 193

Mircea şi Andrei sunt pasionaţi de construcţiile realizate din piese Lego. Fiecare dintre ei are un set format din N cuburi negre de latură 1 şi mai multe piese paralelipipedice de culoare albă cu care va construi o clădire de formă paralelipipedică având baza un pătrat de latură 2 şi înălţimea H.

Toate piesele de culoare albă au înălţimea 2 iar celelalte laturi egale cu 1 şi nu pot fi răsturnate în momentul în care se asamblează pentru a construi clădirea. Aceasta va conţine întotdeauna toate piesele negre din set şi atâtea piese de culoare albă cât e necesar pentru finalizarea ei.

În momentul finalizării clădirii, cei doi băieţi observă că deşi au folosit aceleaşi seturi de piese, cele două clădiri sunt diferite deoarece combinaţiile de culori alb-negru de pe faţadele (nordică, sudică, vestică sau estică) clădirilor nu arată la fel.

Scrieţi un program care să calculeze numărul T de clădiri diferite care se pot construi cu piesele date, ştiind că două clădiri sunt identice dacă sunt îndeplinite simultan următoarele condiţii:

• faţada dinspre nord a uneia este identică cu faţada dinspre nord a celeilalte;
• faţada dinspre est a uneia este identică cu faţada dinspre est a celeilalte;
• faţada dinspre sud a uneia este identică cu faţada dinspre sud a celeilalte;
• faţada dinspre vest a uneia este identică cu faţada dinspre vest a celeilalte.

Programul va afişa restul împărţirii numărului T la 666013.

Jocul cmin constă în a găsi o strategie pentru a deplasa un anumit număr de jetoane identice pe o tablă pătratică, în scopul obţinerii unei configuraţii finale, cu un cost minim.

Tabla are n*n celule, aflate la intersecţia a n rânduri numerotate de la 1 la n de sus în jos şi a n coloane, numerotate de la 1 la n de la stânga spre dreapta. Numărul n este întotdeauna par.

La momentul iniţial al jocului, pe tablă se găsesc k jetoane în poziţii cunoscute. Fiecare jeton poate fi deplasat doar pe verticală, din celula iniţială într-o celulă finală neocupată de un alt jeton. Un jeton poate fi deplasat chiar dacă între poziţia sa iniţială şi cea finală există celule ocupate de către alte jetoane.

Costul deplasării unui jeton pe verticală, din celula curentă într-o celulă adiacentă este 1 (o unitate). Un jeton poate fi mutat de mai multe ori. Jucătorul decide ordinea deplasării jetoanelor. Acesta poate să mute 0, 1 sau chiar toate jetoanele pentru a termina jocul cu un cost total minim. Costul total este suma costurilor deplasării tuturor jetoanelor.

Jocul cmin se termină când diferenţa în valoare absolută dintre numărul de jetoane care se află pe primele n/2 rânduri (cele de sus) şi numărul de jetoane care se găsesc pe ultimele n/2 rânduri (cele de jos), este minimă.

Cunoscând numărul n de rânduri şi de coloane ale tablei şi poziţiile iniţiale ale jetoanelor, determinaţi costul total minim necesar pentru deplasarea acestora, astfel încât diferenţa în valoare absolută dintre numărul jetoanelor care se vor găsi în final pe primele n/2 rânduri şi numărul jetoanelor care se vor găsi pe ultimele n/2 rânduri, să fie minimă.

Pentru a putea ţine evidenţa mai uşor, administratorul unui magazin întocmeşte o listă cu produsele care se găsesc în magazin la începutul zilei. El scrie numele produselor, folosind cuvinte de aceeaşi lungime, formate doar din literele mici ale alfabetului englez. Îndată finalizată lista, el îi asociază un cod reprezentând cel mai mic cuvânt în sens lexicografic, obţinut prin preluarea unei litere din fiecare nume de produs, în ordinea în care acestea au fost scrise pe listă.

El observă că acest cod poate fi obţinut în mai multe moduri. Doreşte însă să identifice varianta în care literele alese sunt cât mai apropiate, altfel spus, distanţa, reprezentând numărul de poziţii, între poziţia cea mai mică şi poziţia cea mai mare pe care sunt plasate caracterele alese, este minimă. De exemplu:

Pentru lista care cuprinde produsele de mai jos:

Se dă un șir de numere întregi a[0],a[1],..a[N-1]. Fiecare valoare a[i] reprezintă mărimea maximă a unui salt ce poate fi efectuat din pozitia i. Din poziţia i, se poate ajunge printr-un salt la oricare din poziţiile i+1, i+2,…, i+a[i], dacă a[i] este pozitiv, iar dacă a[i] este negativ se poate ajunge la oricare din poziţiile i-1,i-2,…, i+a[i].

Trebuie să se ajungă, prin salturi, de la poziția 0 la o poziție mai mare decât N-1 (în afara vectorului, la dreapta).

Scrieți un program care să determine numărul minim de salturi necesare pentru a ajunge de la poziția 0 la o poziție mai mare decât N-1.

Notăm X ca fiind mulţimea numerelor naturale care se pot scrie sub forma 2a*3b. Se consideră doar acele numere pentru care 0 ≤ a ≤ D şi 0 ≤ b ≤ T, unde D şi T sunt date. Pentru un număr v din X, considerăm asociatul lui v ca fiind valoarea (C*P)%Q unde C este ultima cifră a lui v iar P şi Q se dau (de exemplu, pentru P = 1 şi Q = 10 asociatul lui 21*32 este 8).

Se cere determinarea valorii maxime a sumei asociatelor elementelor unei submulţimi a lui X astfel încât oricare ar fi două elemente u şi v din submulţimea respectivă, u nu divide pe v şi nici v nu divide pe u.

O tablă pătratică este formată din N x N celule pătrate, identice ca dimensiune, grupate pe N linii şi N coloane numerotate de la 1 la N. Din oricare celulă aflată la linia i şi coloana j, se poate face o deplasare doar spre celula vecină (i + 1, j) sau (i, j + 1), dacă aceasta există. În interiorul a M celule ale acestei matrice s-a așezat câte un jeton.

Numim drum pe această tablă, orice succesiune de celule parcurse conform regulii de deplasare descrisă anterior. Lungimea unui asemenea drum este egală cu numărul de celule parcurse.

Cunoscând dimensiunea tablei N, numărul total de jetoane m şi două numere naturale L şi K, să se determine un număr d, reprezentând numărul de drumuri distincte modulo 31607 de lungime L care pornesc din celula (1, 1) şi care conţin fiecare câte K jetoane.

Studenţii Facultăţii de Informatică din cadrul Universităţii din Cluj, au conceput roboţi care şterg praful, plantează copaci, pun gresie, servesc masa, etc.

Botezat „Rosie“, robotul care şterge praful are două braţe ( S – stâng şi D – drept) pe care sunt montate nişte perii ce sunt învârtite cu ajutorul unui motoraş. Braţul robotului este programat să se poziţioneze în dreptul unei suprafeţe, periile învârtite de motoraş parcurg suprafaţa ştergând în acest fel praful de pe ea.

Pentru o demonstraţie, robotul este aşezat în faţa unei etajere cu N rafturi numerotate în ordine, de jos în sus, cu numere de la 1 la N. Braţul stâng ( S ) al robotului este poziţionat în dreptul primului raft iar celălat braţ ( D ) în dreptul celui de-al K-lea raft.

Pentru ştergerea prafului, deplasarea braţelor robotului este programată astfel:

• fiecare braţ se deplasează doar de jos în sus, de la raftul în dreptul căruia este poziţionat la un moment dat, la raftul situat imediat deasupra acestuia;
• din minut în minut, se deplasează doar unul din braţe, se poziţionează în dreptul raftului corespunzător şi şterge praful de pe acesta;
• dacă ambele braţe ajung în dreptul aceluiaşi raft, atunci robotul se blochează şi demonstraţia se încheie fără succes.

Ştiind că demonstraţia se termină în momentul în care braţul drept ( D ) al robotului a ajuns pe ultimul raft al etajerei, scrieţi un program care calculează numărul M de modalităţi diferite în care poate fi programat robotul pentru a asigura succesul demonstraţiei.

Programul va afişa restul împărţirii numărului M la 64997.

Avem la dispoziţie un şir X cu n numere naturale date într-o bază b. Trebuie determinat un subşir al şirului dat care are următoarele proprietăţi:

• Fiecare cifră a bazei b: 0, 1, …, b – 1, apare, în total, în numerele acestui subşir de acelaşi număr de ori.
• În orice prefix al subşirului determinat, diferenţa dintre numerele de apariţii ale oricăror 2 cifre cuprinse între 0 şi b-1 este cel mult k (un prefix al subşirului determinat reprezintă o secvenţă de valori din subşir începând cu primul element al subşirului).

Determinaţi numărul maxim de elemente ale unui astfel de subşir.

Ecluza este o construcție hidrotehnică amenajată pe traseul unei căi navigabile, care asigură trecerea navelor între două suprafețe de apă cu niveluri diferite. O ecluză se compune dintr-un bazin numit “sas” sau “camera ecluzei”, prevăzut la ambele capete cu porţi etanşe şi dintr-o instalaţie puternică de pompare pentru umplerea sau golirea sasului până la nivelul dorit.

Specialiștii români au construit pe cursul navigabil al Dunării o succesiune de N ecluze numerotate de la 1 la N, care asigură condiții optime de navigare în sezoanele secetoase. Astfel, dacă o navă se află la un moment dat în ecluza i și nivelul apei din ecluză diferă de nivelul apei din ecluza i+1, pentru a-și continua navigarea în condiții optime se face modificarea nivelului apei fie din ecluza i la nivelul ecluzei i+1, fie se face modificarea nivelului apei din ecluza i+1 la nivelul ecluzei i.

Cunoscând nivelul apei din cele N ecluze, să se determine numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Pe țărmul insulei Mauritius sunt N localități, numerotate de la 1 la N, considerate puncte de maximă atracție pentru turiști. Acestea sunt conectate printr-o rețea feroviară cu linie ferată dublă ce leagă localitățile 1 de 2, 2 de 3, … , N-1 de N și N de 1, putându-se realiza astfel două circuite. Primul circuit presupune vizitarea localităţilor 1 2 .., N 1, în această ordine, iar cel de-al doilea, vizitarea localităţilor 1 N N – 1 … 2 1. În fiecare localitate există agenții ale tuturor celor M operatori de turism, numerotați de la 1 la M.

Un tichet de călătorie se poate achiziționa doar din localitatea în care se găsește călătorul și permite deplasarea din acea localitate până la următoarea localitate a circuitului. Pentru fidelizarea clienților, operatorii de turism utilizează următoarea regulă pentru prețurile tichetelor: dacă un călător a ajuns într-o gară, cu un tichet cumpărat de la un anumit operator de turism și își continuă călătoria către următoarea destinație cu un tichet pe care-l va cumpăra de la un alt operator de turism, atunci noul tichet își va dubla prețul.

Ștefan se află în concediu pe insulă în localitatea 1 și tocmai a câștigat un premiu oferit de operatorul de turism numerotat cu 1, pentru o excursie cu N tichete de călătorie pe insula Mauritius.

El pornește din localitatea în care se află și apoi parcurge cu trenul întregul circuit, astfel încât cu ultimul tichet cumpărat să se întoarcă în localitatea 1, de unde a plecat. Același operator de turism îi oferă contra cost, primul tichet de călătorie. Ștefan va studia toate ofertele și dacă e cazul poate refuza inclusiv acest prim tichet pentru a-l achiziționa de un alt operator de turism, chiar dacă i se va dubla prețul (fiindcă a schimbat operatorul).

Cunoscând prețul tichetelor de călătorie, stabilite de fiecare operator de turism, determinați suma minimă cu care Ștefan poate achiziționa cele N tichete necesare călătoriei sale.