Lista de probleme 1162

Se consideră două șiruri D=(D1,D2,...,Dn) și E=(E1,E2,... ,En) ce reprezintă descompunerea în factori primi pentru un număr natural nenul X, după cum urmează: Di – factorul prim, Ei – puterea la care apare factorul prim Di în descompunerea numărului X (1≤i≤n), unde n reprezintă numărul factorilor primi.

Cerința

Să se determine:
1. numărul total de divizori naturali ai lui X
2. divizorii lui X care aparțin intervalului [A,B], unde A și B sunt două numere naturale date.

Cunoscând prietenul preferat și hobby-ul fiecărui copil, scrieți un program care determină numărul grupurilor care se vor forma și numărul grupurilor formate din copii care au hobby-uri identice; doi copii vor face parte din același grup, dacă cel puțin unul din cei doi l-a numit pe celălalt ca prieten.

Gigel este curios să afle în ce zonă a țării au trăit cei mai mulți dintre strămoșii săi. El reușește să adune informații despre structura genetică a persoanelor din diferite părți ale țării și speră că, prin compararea cu propria structură genetică, să identifice o zonă pătratică în care au trăit cei mai mulți dintre strămoșii săi.

Structura genetică a unei persoane este reprezentată sub forma unei secvențe cu cel mult 20 de caractere (litere mici ale alfabetului englez). O persoană poate fi considerată strămoș a lui Gigel dacă gradul de similaritate dintre secvența corespunzătoare persoanei respective și cea a lui Gigel este mai mare strict decât un număr K, cunoscut.

Gradul de similaritate dintre două secvențe este reprezentat de numărul de caractere comune celor două secvențe. De exemplu pentru secvențele abcdabd și acbdaad gradul de similaritate este 6 (2 caractere a, 2 caractere d, 1 caracter b, 1 caracter c).

Gigel reprezintă harta țării sub forma unui tablou bidimensional cu N linii și M coloane în care fiecare element reprezintă structura genetică a unei persoane din zona respectivă.

Cunoscând N , M , K , structura genetică pentru Gigel și reprezentarea hărții identificată de acesta, să se determine:

1) poziția pe hartă și structura genetică pentru persoana, sau persoanele, pentru care gradul de similaritate cu structura genetică a lui Gigel este maxim;
2) o zonă pătratică, de dimensiune maximă în care toate persoanele ar putea fi strămoși ai lui Gigel.

Pe când era la grădiniță, Maria era pasionată de colorat folosind cariocile. Într-o zi, doamna educatoare i-a dat 4 carioci (de culori diferite). I-a mai dat Mariei un număr foarte mare de cartonașe pătrate, identice ca dimensiuni. I-a spus acesteia să coloreze laturile (cele patru margini) fiecărui cartonaș, așa încât oricare cartonaș să aibă câte o latură de fiecare dintre cele 4 culori. Așa că, toată dimineața fetița a colorat.
Acum, ajungând în gimnaziu, după ce a găsit cartonașele pe care le-a colorat când era mai mică, s-a gândit la următoarea problemă: poate să așeze a x b cartonașe pe o suprafață dreptunghiulară cu a linii și b coloane, astfel încât să fie îndeplinite condițiile: fiecare dintre cele patru laturi ale zonei dreptunghiulare sa fie colorată cu o singură culoare (fiecare latură cu câte o culoare diferită); cartonașele vecine interioare să aibă latura comună de aceeași culoare.
Pentru mai multe perechi (a,b) date, să se afișeze o posibilitate de a aranja cartonașele sau să se spună că acest lucru nu este posibil.

O colonie de N furnici a început să exploreze sistematic teritoriul din preajma muşuroiului. Furnicile se deplasează doar la dreapta sau în jos. Această parte a teritoriului a fost împătrită în zone dispuse pe linii si coloane sub forma unei matrice cu NX linii şi NY coloane. Furnicile pornesc în explorare una câte una din celula din stânga-sus a matricei. Ele merg alternativ: prima spre dreapta, a doua în jos, a treia din nou la dreapta si tot așa. La fel procedează în fiecare celulă a matricei în care ajung, ghidându-se după feromoni lăsați de celelalte furnici. Astfel prima furnică ce ajunge într-o celulă continuă drumul spre celula din dreapta, a doua furnică care ajunge în aceeași celulă o ia în jos, a treia din nou la dreapta și tot așa. Furnicile merg în acest fel până ies din matrice.
Ce suprafaţă a matricei a rămas neexplorată dacă din muşuroi pornesc N furnici.

O tablă de joc cu n linii, numerotate de la 1 la n și m coloane, numerotate de la 1 la m conține n*m celule identice. Celula din colţul din stânga sus se află pe linia 1 şi coloana 1. O celulă poate fi: celulă liberă, celulă în care se află o piatră sau celulă de tip gaură.

Pietrele sunt numerotate cu valori începând de la 1. Numerotarea pietrelor pe tablă se face în ordinea în care sunt
date în fișierul de intrare. O celulă de pe tablă are maxim patru celule vecine, aflate în direcțiile: nord, vest, sud, est, iar o piatră poate sări doar peste o celulă vecină în care se află o piatră. În urma unei astfel de sărituri, piatra peste care s-a sărit dispare de pe tablă. Astfel, o piatră situată în celula de pe linia i și coloana j, poate sări :

1. în direcția nord peste piatra situată în celula de pe linia i-1 și coloana j și ajunge în celula de pe linia i-2 și coloana j, iar piatra aflată pe linia i-1 și coloana j dispare; o astfel de săritură se notează cu litera N;
2. în direcția est peste piatra situată în celula de pe linia i și coloana j+1 și ajunge în celula de pe linia i și coloana j+2, iar piatra aflată pe linia i și coloana j+2 dispare; o astfel de săritură se notează cu litera E;
3. în direcția sud peste piatra situată în celula de pe linia i+1 și coloana j și ajunge în celula de pe linia i+2 și coloana j, iar piatra aflată pe linia i+1 și coloana j dispare; o astfel de săritură se notează cu litera S;
4. în direcția vest peste piatra situată în celula de pe linia i și coloana j-1 și ajunge în celula de pe linia i și coloana j-2, iar piatra aflată pe linia i și coloana j-1 dispare; o astfel de săritură se notează cu litera V.

O săritură a unei pietre este permisă doar dacă celula în care urmează să ajungă se află pe tabla de joc, este liberă și în celula peste care sare există o piatră.

Se cunoaște o succesiune de sărituri formată din maxim 255 de caractere S, N, E sau V, după care o piatră realizează săriturile specificate, în ordine, de la stânga la dreapta. Dacă piatra ar trebui execute o săritură care nu este permisă, poziţia ei nu se modifică şi se trece la săritura următoare din succesiune.

Să se determine numărul pietrei care efectuând sărituri în conformitate cu succesiunea dată, conduce la o configuraţie finală formată dintr-un număr minim de pietre pe tablă. Dacă există mai multe pietre care ar conduce la acelaşi număr minim de pietre în configuraţia finală, se va afişa valoarea cea mai mică dintre numerele de identificare ale pietrelor respective.

Un număr natural n se numește număr VIP dacă este format din cel puțin două cifre, conține cel puțin o cifră impară și cel puțin o cifră pară, iar toate cifrele impare sunt scrise înaintea tuturor celor pare. ( VIP = Valori Impare Pare). De exemplu, 352, 7546 sunt numere VIP, iar 35, 468, 5483, 387 nu sunt numere VIP. Se numește SECVENȚĂ VIP într-un șir de cifre, o succesiune de cifre (aflate pe poziții consecutive în șir) care formează, în ordine, un număr VIP.

Pentru un șir de cifre nenule, se cere să se determine:

1. Numărul de SECVENȚE VIP din șir.
2. Lungimea minimă a unui șir de cifre care conține același număr de SECVENȚE VIP ca șirul dat și are toate cifrele impare situate înaintea celor pare.
3. Suma tuturor numerelor ce se pot forma, astfel încât fiecare număr să conțină toate cifrele distincte ale celui mai mare număr VIP din șirul dat, fiecare cifră fiind folosită exact o dată, și nicio altă cifră diferită de acestea.

Se consideră un șir de numere naturale f[1], f[2], …, f[n]. Fiecărui element al șirului i se calculează numărul biților de 1 din reprezentarea în baza 2. De exemplu, numărul 15 are 4 biți de 1 în baza 2.
Să se determine numărul total de biți de 1 al tuturor numerelor din șir.

Supărat că fata de care-i plăcea l-a respins, Bogdan și-a făcut bagajele și a pornit într-o excursie de-a lungul întregii lumi. Acesta a vizitat mai toate continentele, însă acum este blocat în Africa din cauza faptului că Bogdan, băiat mai neastâmpărat din fire, s-a apucat să se bată cu țânțarii Mosquito.Bineînțeles că a fost înțepat și că acum trebuie să caute antidot pentru venin, altfel Bogdan se va transforma și el în Mosquito. Acesta s-a dus să-i ceară ajutorul lui Aashiq, care îi spune următoarele: “Te voi vindeca de înțepături dacă reușești să duci la bun sfârșit sarcina pe care ți-o dau.”, însă Bogdan nu prea se pricepe la sarcini complicate, așa că vă roagă să rezolvați voi cerința în locul lui.

Dându-se trei numere naturale, a, n, k, trebuie să aflați valoarea următoarei expresii: ak•ak+2k•...•ak+2k+...+nk. Antidotul pentru înțepăturile de Mosquito necesită foarte multă muncă, motiv pentru care vor trebui îndeplinite t teste.

Andra este o fetiță pasionată de desen. Pentru a-și îmbunătăți performanțele școlare la geometrie, Andra îmbină pasiunea pentru desen cu rezolvarea problemelor de geometrie. Astfel, pe o foaie de matematică împărțită în pătrățele dispuse pe \(2^N \) linii şi \(2^N \) coloane, Andra desenează în centru o figură de forma unui pătrat de latură \(2^{N-1} \) (figura 1) . Pentru fiecare colț al figurii, Andra desenează alte 4 noi figuri cu latura egală cu jumătate din latura figurii inițiale (Figura 2). Repetă procedeul de desenare pentru fiecare nouă figură obținută, până când ajunge la marginea foii de hârtie, fără a depăși marginile acesteia. Fiecare pătrățel care face parte dintr-o figură desenată este colorat, pentru a se distinge pe foaia de hârtie. Fiecare figură desenată este un pătrat cu laturile paralele cu marginile foii de hârtie.

Scrieţi un program care citește numărul N , corespunzător dimensiunii de \(2^N\) x \(2^N \) a foii de desen şi determină:

1) Numărul de figuri de latură minimă desenate;
2) Numărul total de pătrățele colorate cel puțin o dată de pe foaia de hârtie.