Informatică, întrebare adresată de alexalghisi, 8 ani în urmă

Ionel este pasionat de matematică. El inventează tot felul de probleme. De data aceasta Ionel s-a gândit să genereze un şir de cifre, plecând de la un număr natural şi aplicând o anumită regulă. De exemplu, pentru numărul 425 el va genera şirul: 4, 4, 4, 4, 2, 2, 5, 5, 5, 5, 5 astfel: ia, în acestă ordine, prima cifra din număr (4) şi o repetă de 4 ori, apoi ia a doua cifră (2) şi o repetă de 2 ori, apoi ia a 3-a cifra (5) şi o repetă de 5 ori. Ionel se întreabă ce cifră se găseşte în şir pe o pozitie precizată. De exemplu, pe poziţia 3 se găseşte cifra 4.
Cerinţă

Scrieţi un program care, pentru numărul N dat şi M, poziţia unui termen din şir, determină valoarea termenului al M-lea din şirul generat după regula de mai sus.

Restricţii

1≤ N ≤2000000000
1≤ M ≤ numărul total de termeni ai şirului


Exemplu:

425 5 output: 2

Explicatie:
Şirul: 4, 4, 4, 4, 2 ,2, 5, 5, 5, 5, 5
Pe poziţia 5 se găseşte cifra 2.

Trebuie sa existeceva formula magica de mate .. parerea mea.

Răspunsuri la întrebare

Răspuns de Petruccinator
1

#include <iostream>

#include <vector>

int main(){

   std::vector<int> vec;

   size_t n, poz;

   std::cin >> n >> poz;

   for(size_t t[3]={n}; t[0]; t[0] /= 10){

       t[2] = t[1] = t[0] % 10;

       while(t[2]--)

           vec.push_back(t[1]);

   }

   n = vec.size();

   while(n--){

       std::cout << vec[n] << ' ';

   }

   std::cout << "\nPe pozitia " << poz << " se gaseste cifra " << vec[vec.size() - poz];

}


alexalghisi: Nu pare ok. 465 5
stdout copy
4 4 4 4 6 6 6 6 6 6 5 5 5 5 5
Pe pozitia 5 se gaseste cifra 6
alexalghisi: Si oricum este restrictia 1≤ N ≤2000000000
Petruccinator: Noi nu suntem la olimpiada.
alexalghisi: Nasol. Atunci nu raspundeti aiurea macar!
Petruccinator: Stii ca tu nu faci reguli la intrebarea altcuiva. Tu ceva ai colaborat la info? Eye for an eye.
Petruccinator: Daca nu te aranjeaza, inlocuieste ultima functie cu
std::cout << poz
Petruccinator: Si elimina din cod:
while(n--){

std::cout << vec[n] << ' ';

}
Alte întrebări interesante