Lista de probleme 212

Filtrare

#1968 bloc

Cifrele de la 1 la K se scriu într-un şir, iar secvenţa obţinută se repetă la nesfârşit. De exemplu, pentru K=9 se obţine şirul: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 …. Asupra unui asemenea şir se aplică succesiv operaţia de rostogolire de lungime P, ce presupune ca blocul format cu cifrele de pe primele P poziţii să se rotească cu 1800 şi să se scrie deasupra următoarei secvenţe de lungime P.
Astfel pe primele P poziţii se formează un bloc având la bază P cifre şi înălţimea N+1, unde N este numărul de rostogoliri de lungime P.
Pentru K, P şi N date se cer următoarele:
a) Suma elementelor blocului după N rostogoliri de lungime P.
b) Suma maximă a elementelor de pe o coloană a blocului după N rostogoliri de lungime P.
c) Dacă liniile blocului le privim ca pe nişte numere cu P cifre, să se afle cel mai mic dintre aceste numere ale blocului obţinut după N rostogoliri de lungime P.

#1967 cmmdc0

Andreea a primit de ziua ei un joc cu cifre de plastic, din fiecare cifră nenulă având 30 de exemplare. Cifrele se aflau într-un săculeţ, iar Andreea s-a gândit să scoată la întâmplare un număr oarecare de cifre din săculeţ, să efectueze produsul lor, şi dacă obţinea un număr mai mic decât 1.000.000.001 pe care nu-l mai obţinu-se până atunci, îl scria pe un cartonaş, punând apoi cifrele înapoi în săculeţ. Astfel, după o muncă asiduă, a scris toate numerele posibile pe cartonaşe. Prietena ei, Ana, făcându-i o vizită, a văzut cartonaşele, a luat la întâmplare unul dintre ele şi a calculat cel mai mare divizor comun al numărului de pe cartonaşul luat cu fiecare număr de pe cartonaşele rămase, scriind pe fiecare dintre cartonaşele rămase rezultatul obţinut. Dacă se cunosc numerele aflate pe N cartonaşe dintre cele scrise de Andreea şi Ana, aflaţi numărul de pe cartonaşul luat de Ana.

#1969 pdigit

Fie a un număr natural scris în baza 10. Notăm cu b, baza minimă în care poate fi scris a. Astfel, dacă a=21756, atunci baza minimă în care acesta poate fi scris este b=8.
Definim cifra de control a numărului a scris în baza b, notată cu c=digit(a)b, ca fiind numărul de o cifră obținut prin adunarea în baza b a cifrelor numărului a. Dacă rezultatul obținut este de o cifră, atunci acesta reprezintă valoarea lui c, dacă nu, se aplică repetat asupra rezultatului procedeul de însumare a cifrelor în baza b până când se obține o cifră.

De exemplu:

  • c=digit(21756)8=digit(2+1+7+5+6)8=25, întrucât c>8 procedeul continuă
  • c=digit(25)8=digit(2+5)8=7.

Se consideră un interval închis [x,y]. Să se determine:

  • a – primul număr prim mai mare sau egal ca x
  • b – baza minimă în care poate fi scris numărul prim a
  • c – cifra de control a numărului prim a
  • n – numărul de numere prime din intervalul [x,y] ce pot fi scrise în baza b și au cifra de control egală cu c.

#2010 Fermier

Dorel și-a achiziționat o fermă cu n plantații și o mașină de transport cu o capacitate c, pentru transportul de îngrășăminte la toate plantațiile. Îngrășămintele se află într-un depozit, în cantitate suficientă pentru scopul propus. Plantațiile și depozitul sunt dispuse sub forma unui cerc. Există drumuri doar între plantația i și plantația i+1 (1≤i≤n-1), precum și între depozit și plantația 1 și depozit și plantația n, ca în figură.

La o plantație i se poate ajunge de la depozit trecând prin plantațiile 1, 2,…, i-1 sau prin plantațiile n, n-1, …, i+1, alegerea făcându-se în funcție de traseul cel mai scurt. Se cunosc aceste distanțe, precum și cantitatea de îngrășăminte necesară pentru fiecare plantație. La fiecare încărcare, Dorel ia din depozit exact cantitatea c. Dorel vrea să-și organizeze bine munca la fermă și să consume cât mai puțină benzină prin alegerea celor mai scurte trasee de parcurs. Plantațiile trebuie să fie aprovizionate obligatoriu în ordinea următoare: mai întâi plantația 1, apoi plantația 2, plantația 3,…, plantația n. În plus, și-a propus să încarce o nouă cantitate de îngrășământ doar după ce a folosit toată cantitatea încărcată anterior. Transportarea îngrășămintelor pe plantații se face deci, începând cu plantația 1. După ce se transportă toată cantitatea necesară pentru această plantație, se trece la plantația 2, și tot așa în ordine la 3, 4 etc. până se deservește ultima plantație. Dacă după ce s-au transportat îngrășămintele necesare pentru plantația i în mașină au mai rămas încă îngrășăminte, acestea trebuie utilizate în continuare pentru alte plantații, alese în ordinea impusă (începând cu plantația i+1, apoi i+2 etc.), până se epuizează toată cantitatea transportată de mașină. Astfel, dacă de la plantația i trebuie să ajungă la plantația i+1, va alege cel mai scurt traseu dintre traseul direct de la plantația i la i+1 și traseul care trece prin plantațiile i-1, i-2, …, 1, depozit, n, n-1, …, i+1. La final, mașina trebuie să se întoarcă la depozit, goală sau cu cantitatea rămasă după aprovizionarea cu îngrășăminte a plantației n.

Ajutați-l pe Dorel să calculeze distanța parcursă pentru a transporta îngrășăminte la toate cele n plantații, conform cerințelor.

#2051 pp

Se consideră un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤…≤a[N]. În legătură cu acest șir de numere ne interesează perechile de poziții (i,j) cu 1≤i<j≤N și a[i]≠a[j] sau ne interesează suma elementelor anumitor secvențe.

Se cere să se scrie un program care să citească un număr C reprezentând tipul cerinței, un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N] și T perechi de numere naturale (p[k],q[k]) cu 1≤p[k]<q[k]≤N și 1≤k≤T și apoi:

(1) Dacă C=1, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) suma a[p]+a[p+1]+...+a[q].
(2) Dacă C=2, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) numărul de perechi (i,j) care respectă simultan condițiile p≤i<j≤q și a[i]≠a[j].

#2056 Popcorn C++

Cu toții știm că popcornul este o adevărată delicatesă culinară. În pregătirile tale pentru lotul de anul acesta (și pentru petrecerile de după), ai făcut comandă de N tipuri de floricele de porumb pentru microunde. Fiecare tip are asociate 3 valori:

  • A[i] = Timpul (în secunde) la care orice floricică de acel tip “pocnește”;
  • B[i] = Timpul (în secunde) la care orice floricică de acel tip “se arde”;
  • C[i] = Cantitatea (în floricele) a respectivului tip.

Mai ai la dispoziție M pungi pentru floricele de unică folosință de capacitate foarte mare (practic, infinită) și un cuptor cu microunde. Cum, bineînțeles, nimănui nu îi plac floricelele nefăcute sau cele arse, îți dorești să le partiționezi convenabil în cele M pungi și apoi să le introduci pe rând în cuptorul cu microunde, setându-i un timp de preparare prep[i] corespunzător, astfel încât după cele M tranșe să obții cât mai multe floricele comestibile.

Formal, o floricică de tipul i introdusă în punga j , setată la timpul (în secunde) de preparare prep[j] este comestibilă dacă și numai dacă A[i] ≤ prep[j] < B[i].

Fiind date cele N tipuri de floricele și numărul de pungi disponibile, trebuie să găsești o partiție convenabilă și timpii optimi de preparare pentru fiecare pungă, astfel încât la final să obții numărul maxim de floricele comestibile, pe care să îl afișezi în fișierul de ieșire. Prea ușor!

#2129 Prime1

Eu sunt fascinată de numerele prime. Consider că numerele prime sunt “scheletul” tuturor numerelor sau “atomii” acestora, pentru că orice număr natural mai mare decât 1 poate fi scris ca un produs de numere prime. Recent am aflat şi alte proprietăţi interesante legate de numerele prime, de exemplu:

  1. În şirul Fibonacci există o infinitate de numere prime. Vă mai amintiţi şirul Fibonacci? 0, 1, 1, 2, 3, 5, 8, 13, ... Este şirul în care fiecare termen, exceptând primii doi, se obţine ca suma celor doi termeni care îl precedă.
  2. Există numere naturale denumite „economice”. Un număr natural este economic dacă numărul de cifre necesare pentru scrierea sa este mai mare decât numărul de cifre necesare pentru scrierea descompunerii sale în factori primi (adică decât numărul de cifre necesare pentru scrierea factorilor primi şi a puterilor acestora). De exemplu 128 este economic pentru că 128 se scrie cu 3 cifre, iar descompunerea sa în factori primi se scrie cu două cifre (2^7); 4374 este economic pentru că se scrie cu 4 cifre, în timp ce descompunerea sa în factori primi se scrie cu 3 cifre (2*3^7). Observaţi că atunci când un factor prim apare la puterea 1, aceasta nu este necesar să fie scrisă.
  3. Multe numere naturale pot fi scrise ca sumă de două numere prime. Dar nu toate. De exemplu, 121 nu poate fi scris
    ca sumă de două numere prime.

Scrieţi un program care citeşte numărul natural n şi o secvenţă de n numere naturale, apoi rezolvă următoarele cerinţe:

  1. determină şi afişează câte dintre numerele din secvenţa dată sunt numere prime din şirul Fibonacci;
  2. determină şi afişează câte dintre numerele din secvenţa dată sunt numere economice;
  3. determină şi afişează câte dintre numerele din secvenţa dată nu pot fi scrise ca sumă de două numere prime.

#2135 Roua

Un copil dorește să vopsească ouăle de Paște, având la dispoziție vopsele de culoare roșie, galbenă, verde și albastră. Fiecare culoare va fi reprezentată printr-un singur caracter astfel: 'r' pentru culoarea roșie, 'g' pentru galben, 'v' pentru verde, 'a' pentru albastru. Pentru a vopsi ouăle, le așază în rând, unul după altul. Astfel, o colorare va fi o succesiune de N caractere din mulţimea {'r' , 'g' , 'v','a'}, reprezentând, în ordinea aşezării, culorile celor N ouă.

Numim “roua” o secvență de R caractere cu proprietatea că dintre acestea exact R-1 caractere reprezintă culoarea roșie, iar un caracter reprezintă una dintre celelalte 3 culori. De exemplu secvenţele roua de lungime 3 sunt "grr", "rgr", "rrg", "vrr", "rvr", "rrv", "arr", "rar", "rra" .

Copilul consideră că o colorare este R-frumoasă, dacă oricare R caractere consecutive din colorare formează o secvență roua. De exemplu, pentru N=11 ouă, şirul "arrrvrrrarr" reprezintă o colorare 4-frumoasă.

Cunoscând N, numărul de ouă vopsite, și numărul natural R, scrieți un program care determină și afișează:

  1. numărul de secvențe “roua” de lungime R existente în colorarea celor N ouă;
  2. numărul total al colorărilor R-frumoase pentru cele N ouă.

#2136 Peste

Ursul: Bună, cumătră! Da cât peşte ai? Dă-mi şi mie, că tare mi-i poftă!
Vulpea: Ia mai pune-ţi pofta-n cui. Dacă vrei pește, du-te şi-ţi înmoaie coada-n baltă şi vei avea ce să mănânci.
Ursul: Învaţă-mă, te rog, cumătră, că eu nu ştiu cum se prinde peştele.
Vulpea: Alei, cumetre! da’ nu ştii că nevoia te-nvaţă ce nici nu gândeşti? Du-te deseară la baltă și bagă-ţi coada-n apă. Stai pe loc, fără să te mişti, până spre ziuă. Între timp, ia foaia aceasta pe care am scris N numere naturale și până dimineață trebuie să procedezi în felul următor:

  • elimini exact două cifre alăturate din fiecare număr scris pe foaie, astfel încât, celelalte cifre rămase după eliminare să formeze, de la stânga la dreapta, cel mai mare număr posibil (de exemplu, din numărul 77196, elimini cifrele 7 și 1 pentru a obține cel mai mare număr posibil 796).
  • toate cele N numere obținute la pasul anterior, le lipești unul după altul, în ce ordine vrei tu. Uitându-te de la stânga la dreapta la cifrele numerelor lipite, observi că s-a format un nou număr X. Ai grijă cum procedezi, căci până
    dimineață, atâta pește se va prinde de coada ta cât vei obține tu valoarea lui X.

Ajutați-l pe urs să prindă cât mai mult pește posibil.

Scrieți un program care citește N numere naturale și determină:

  1. Cel mai mare număr de eliminări efectuate cu aceleași două cifre alăturate.
  2. Cel mai mare număr natural X determinat astfel încât ursul să prindă cât mai mult pește.

#2148 ADN

Pe Marte s-au descoperit N marțieni, identificați de către oamenii de știință de pe Pământ prin numerele de la 1 la N. Cercetările au dovedit că ADN-ul oricărui marțian X este format din mulțimea factorilor primi din descompunerea lui X.

Se știe că marțianul cu numărul de ordine Y îl moștenește pe marțianul cu numărul de ordine X dacă ADN(X) este inclus în ADN(Y), adică mulțimea factorilor primi ai lui X este inclusă în mulțimea factorilor primi ai lui Y.

Trebuie să specificăm că se pot întâlni situații extreme în care X îl moștenește pe Y dar și Y îl moștenește pe X, atunci când cei doi marțieni au ADN-urile egale.

Realizați un program care, considerând mulțimea celor N marțieni, determină numărul de perechi de marțieni (Y, X) pentru care Y îl moștenește pe X, unde 1 ≤ X ≤ N și 1 ≤ Y ≤ N.