Lista de probleme 28

Despre numărul natural N spunem că are proprietatea okcpp dacă oricum alegem K cifre ale sale vom găsi printre ele cel puţin P cifre distincte (oricare k cel puțin p).

Cerințe

(1) Fiind date numerele naturale K, P, A și B să se calculeze și să se afișeze numărul de numere okcpp din intervalul [A,B].
(2) Fiind date numerele naturale K, P și N să se calculeze și să se afișeze cel mai mic număr okcpp care este mai mare sau egal cu N.

În tărâmul Jupânului există N + 1 orașe. Acestea au fost construite în linie dreaptă, începând cu cel în care este casa Jupânului. Între oricare 2 orașe consecutive s-a construit câte un drum. Pentru fiecare drum, se cunoaște lungimea lui, exprimată în metri și viteza cu care se poate parcurge, exprimată în metri pe secundă.

Jupânul trebuie să ajungă din orașul 0 în orașul N. Acesta știe că poate îmbunătăți un drum, mărindu-i viteza de la V metri pe secundă la V + 1 metri pe secundă, cu costul de 1 dolar. Acesta poate îmbunătăți un drum de mai multe ori.

Jupânul are un buget de X dolari și ar vrea să-i folosească pentru a micșora timpul în care ajunge din orașul 0 în orașul N.

Vlad a inventat un nou joc. Jocul conţine N standuri aşezate în linie dreaptă. Fiecare stand are o etichetă pe care este scris un număr natural. Eticheta este considerată corectă dacă numărul îndeplineşte următoarele două condiţii:

• conține atât cifre pare, cât și cifre impare;
• începe cu cifrele impare așezate în ordine crescătoare, urmate de cifrele pare în ordine descrescătoare.

Pentru jocul său, Vlad a construit robotul reparator care ştie să verifice numere şi să le repare, dacă este necesar. Robotul reparator se deplasează în linie dreaptă și se opreşte pe rând la fiecare dintre cele N standuri. La fiecare stand, robotul verifică eticheta şi dacă nu este corectă, o „repară”. Pentru a repara eticheta, robotul aranjează cifrele impare în ordine crescătoare, apoi, în continuare, aranjează cifrele pare în ordine descrescătoare; dacă eticheta nu conţine nicio cifră impară, cea mai mare cifră pară o înlocuieşte cu 9 ; dacă eticheta nu conţine nicio cifră pară, cea mai mică cifră impară o înlocuieşte cu 0 . Deplasarea de la un stand la altul durează t secunde, verificarea etichetei unui stand durează v secunde, iar repararea acesteia durează r secunde. Cursa robotului se încheie după ce robotul a verificat toate cele N standuri şi a reparat etichetele incorecte.

Scrieţi un program care citeşte numărul N de standuri, timpul (ora h , minutul m , secunda s) când robotul ajunge la primul stand, timpii t , v și r cu semnificaţia din enunţ şi etichetele standurilor și care rezolvă următoarele cerințe:

1. calculează şi afişează timpul (ora, minutul şi secunda) când robotul a încheiat verificarea tuturor celor N standuri şi repararea etichetelor incorecte;
2. repară (unde este necesar) etichetele standurilor şi afişează etichetele celor N standuri la final.

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.

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

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.

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.

Zeno are n cutii cu bomboane, iar în fiecare cutie se găsește un număr natural nenul de bomboane. Zeno poate împărți bomboanele din toate cutiile colegilor în două moduri: frățește sau diferențiat. Cunoscând n numărul de cutii și numărul de bomboane din fiecare cutie să se scrie un program care determină:
a) Numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
b) O modalitate de împărțire a bomboanelor din fiecare cutie, dacă se face împărțirea diferențiată.

Mihai a construit o matrice pătratică A de dimensiune N cu valori în mulțimea {0,1}. El preferă acele matrice care au toate elementele identice și de aceea a calculat pentru matricea A, numărul K de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea A într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul D, și definește operația ZET care constă în alegerea unei submatrice pătratice de dimensiunea D din matricea precedentă în care schimbă toate elementele 0 în 1 și invers. El vrea să aplice operația ZET inițial pentru matricea A, apoi repetă operația pentru matricea obținută la momentul anterior, de un număr minim de ori, notat R, până când matricea obținută are toate elementele identice, sau dacă nu este posibil, R va avea valoarea -1.

Mihai vă roagă să calculați valorile K și R. Pentru a preciza tipul cerinței, Mihai folosește un cod T care dacă are valoarea 1, atunci solicită calcularea valorii K, iar dacă T are valoarea 2, atunci solicită calcularea valorii R.

Proba de 100 metri plat este una dintre cele mai populare și prestigioase probe din cadrul oricărui concurs de atletism. Recordul modial al acestei probe este deținut în prezent de sportivul jamaican Usain Bolt cu timpul de 9.58 secunde.
Uneori lupta dintre sportivi este atât de strânsă încât diferențierea dintre atleți se poate face doar cu ajutorul camerelor de luat vederi ce surprind finish-ul atleților. Au existat cazuri când doi sau mai multi atleți au fost declarați la egalitate.

Considerând N atleți, ce participă la o cursă de 100 metri plat, identificați prin numerele 1, 2, …, N, să se scrie un program care determină numărul P al clasamentelor distincte care pot fi obținute după finalizarea cursei. De exemplu, pentru N = 2, se pot obține 3 clasamente distincte: (1,2), (2,1), (1=2); unde (1=2) reprezintă situația când ambii atleți s-au clasat la egalitate.