Lista de probleme 610

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#725 Rege

Cunoscând dimensiunea m*n a tablei de şah, respectiv poziţia iniţială (l1,c1) şi poziţia finală (l2,c2) a traseului regelui, să se calculeze numărul drumurilor minime distincte în care regele poate parcurge drumul.

Matca cea tânără a decis să părăsească stupul şi să îşi facă propria familie de albine, lucru nu tocmai uşor. Ea, împreună cu albinele sale trebuie să meargă din floare în floare până la marginea plantaţiei. Plantaţia are formă dreptunghiulară cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). În fiecare punct este o floare. Florile sunt codificate cu 0 sau 1, cele codificate cu 0 putând fi ocupate doar de matcă, cele cu valoarea 1 doar de câte o albină. Roiul de albine pleacă de la marginea stângă a plantaţiei (coloana 1) şi trebuie să ajungă în marginea din dreapta (coloana M). La un pas, toate albinele (inclusiv matca) trebuie să se afle pe poziţii consecutive pe aceeaşi coloană. La pasul următor ele se pot deplasa doar pe coloana următoare, dar tot pe poziţii vecine (eventual îşi pot schimba ordinea). Efortul depus pentru deplasarea de pe o coloană pe alta este egal cu diferenţa dintre prima linie ocupată de un membru al roiului de albine (matca sau albină) la pasul anterior şi prima linie ocupată de un membru al roiului albine (matca sau albină) după mutare.

Determinaţi numărul maxim de membri ai roiului de albine (matcă + albine) care pot părăsi stupul pentru a traversa toată plantaţia în scopul formării unei noi familii. Determinaţi, de asemenea efortul total minim cu care matca poate traversa plantaţia cu numărul maxim de albine determinat.

#716 cmin

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

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.

#707 sumk

sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent.

Dacă jucătorul se găseşte în stagiul i pe nivelul j și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât K, el va trece în mod obligatoriu pe nivelul j+1 al stagiului i. Dacă jucătorul primește cel puţin un punct pe nivelul j și astfel punctajul său în stagiul i devine exact K, atunci jucătorul trece în mod automat pe nivelul j al stagiului i+1 sau termină jocul cu succes dacă i=N.

Cunoscând numărul N de stagii ale jocului şi numărul K de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo 578537 pentru ca jocul să se termine cu succes.

Lot Juniori, Baia Mare, 2013

Prin fibosir(N) înţelegem un şir construit prin adăugarea la sfârşit (concatenare) a primilor N termeni nenuli ai şirul Fibonacci definit astfel:

  • F1=1
  • F2=1
  • FN = FN-1 + FN-2

Pentru N valoare naturală dată, să se elimine din fibosir-ul construit M secvenţe disjuncte de lungime K fiecare, astfel încât numărul format din cifrele rămase în fiboşir să fie maxim.

#704 smsm

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.

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.

#694 sam

Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N].

Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]<X[i]>X[i+1], 1<i<K sau X[i-1]>X[i]<X[i+1], 1<i<K.

Vom nota cu nrex(X) numărul de extreme locale ale subșirului X.

Spunem că un subșir X[1], X[2],...,X[K] (K≥2) al șirului A este subșir alternant dacă nrex(X)=K-2, adică exceptând primul și ultimul termen din subșir toți ceilalți termeni sunt extreme locale ale subșirului X.

Dintre toate subșirurile alternante ale șirului A ne interesează cele de lungime maximă pe care le vom numi subșiruri alternante maximale.

Cunoscând N și tabloul A se cere să se determine restul obținut la împărțirea dintre numărul M al subșirurilor alternante maximale ale tabloului A și numărul 1000003.

#692 robot

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.