BitCell

Your IT power source

Skip to content


Problema cifre

C/C++ este un limbaj multi-paradigmă de nivel mediu, orientat pe obiecte, folosit pe scară largă în industria software datorită echilibrului dintre viteză şi complexitate. Dacă ai nelămuriri în legătură cu acest limbaj sau vrei să ne înveți ceva chiar tu, intră aici.
Post a reply

Problema cifre

Postby Cosmin_NTG » 26 Jan 2012, 18:46

Salut! Am dat peste o problema de pe campion.edu.ro care se numeste cifre1.
Enuntul este acesta:
Line number On/Off | Expand/Contract | Select all
  1. Fie N un numar natural nenul. Scriind în ordine, unul dupa altul, toate numerele naturale de la 1 la N obtinem o secventa de cifre. De exemplu, pentru N=22 obtinem:
  2. 12345678910111213141516171819202122
  3.  
  4. Cerinta
  5.  
  6. Scrieti un program care sa determine numarul de cifre dintr-o astfel de secventa.
  7.  
  8. Date de intrare
  9.  
  10.  
  11. Fisierul de intrare cifre1.in contine o singura linie pe care se afla numarul natural N.
  12.  
  13. Date de iesire
  14.  
  15. Fisierul de iesire cifre1.out contine o singura linie pe care se afla numarul de cifre determinat.
  16.  
  17. Restrictii
  18.  
  19. 1<=N<=1 000 000 000
  20.  
  21. Exemple
  22. cifre1.in   cifre1.out  cifre1.in   cifre1.out  cifre1.in   cifre1.out
  23. 5                 5        15         21         120        252
  24.  


Eu am incercat ceva care functioneaza doar pentru n<1000 si cred ca nu e prea eficient. Incerc de ceva timp sa gasesc o regula matematica dar nu reusesc. Cine ma poate ajuta?
Line number On/Off | Expand/Contract | Select all
  1. #include<iostream>
  2.  
  3. using namespace std;
  4. int s=0, n, k;
  5. int main()
  6. {
  7.  
  8.     cout<<"n=";
  9.     cin>>n;
  10.     k=n;
  11.     while(n)
  12.     {
  13.         n=n/10;
  14.         s++;
  15.     }
  16.     if(k<10)
  17.      cout<<k;
  18.     else if((k>10) && (k<100))
  19.      cout<<9+(k-9)*2;
  20.     else if((k>100)&& (k<1000))
  21.      cout<<189+300*(k/100%10-1)+((k/10%10)*10+k%10+1)*3;
  22.  
  23.  
  24.     return (0);
  25. }
  26.  

Aceasta este varianta mea.
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Problema cifre

Postby andreiandreiq » 26 Jan 2012, 20:31

Salut,

Nu am găsit o regula matematica, dar am reușit sa rezolv problema folosindu-ma de string-uri. Mai exact, am făcut un for de la 1 la n, și de fiecare data transformam numărul într-un string, și număram câte elemente avea și le rețineam într-o variabila. Eu l-am rezolvat în Pascal (fără fișiere), folosindu-ma de funcția STR, care transforma valori întregi sau raționale în string.

Acuma nu știu dacă în C++, exista o astfel de funcție, dar din moment ce bătrânul Pascal o are... presupun ca trebuie sa aibă și C++-ul.

Line number On/Off | Expand/Contract | Select all
  1.  
  2. var  j,i,n,x:integer;
  3.        sir:string;
  4. begin
  5.   write('Dati n:');
  6.   readln(n);
  7.   for i:=1 to n do
  8.   begin
  9.     STR(i,sir);
  10.     for j:=1 to length(sir) do
  11.     x:=x+1;
  12.   end;
  13.   writeln('X:=',x);
  14. end.
  15.  


P.S: Poate nu e cea mai buna rezolvare, dar merge. M-am uitat un pic pe net, și am văzut ca sunt ceva funcții care transforma un întreg în string (da un "sarci" pe "gogu").
0,0p / 0 votes
Image
User avatar
andreiandreiq
Word
 
Joined: 30 Dec 2009
Status: 33.33

Re: Problema cifre

Postby Cosmin_NTG » 26 Jan 2012, 21:26

Da, stiu despre ce e vorba. Initial am mers pe o implementare cu siruri dar nu am reusit si de aceea am incercat o varianta cu numere intregi, care nu este prea functionala. Acum, am incercat iar, in urma sfatului tau, si am reusit oarecum.
Line number On/Off | Expand/Contract | Select all
  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdlib>
  4. #include<fstream>
  5. #define CT 1000000L
  6. using namespace std;
  7. ifstream f("cifre1.in");
  8. ofstream g("cifre1.out");
  9. int main()
  10. {
  11.          char x[CT], y[CT]; int n, p=0;
  12.  
  13.          f>>n;
  14.          f.close();
  15.          for(int i=1; i<=n; i++)
  16.          {
  17.              itoa(i, x, 10);
  18.              for(int j=0; x[j]; j++)
  19.              {
  20.                  y[p]=x[j];
  21.                  p++;
  22.              }
  23.          }
  24.          y[p]='\0';
  25.          g<<strlen(y);
  26.          g.close();
  27.  
  28.          return (0);
  29. }
  30.  
. Functia care transforma un intreg in string este itoa (integer to ascii) si are 3 parametrii: nr-ul intreg ce trebuie transformat, sirul si baza in care este numarul dat. Am incarcat sursa pe site si la evaluare imi da o eroare conform careia functia itoa nu este definita. Din cate stiu eu, aceasta functie se gaseste in headerul cstdlib. Mie imi ruleaza perfect (am C::B cu GNU gcc compilator). M-am uitat pe cplusplus.com si acolo zice asa:
Line number On/Off | Expand/Contract | Select all
  1. This function is not defined in ANSI-C and is not part of C++, but is supported by some compilers.
. O sa incerc sa scriu sursa in C si apoi sa vad cum stau lucrurile.

P.S. Am incercat si in C:
Line number On/Off | Expand/Contract | Select all
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>
  4. #define CT 1000000L
  5. FILE *f, *g;
  6. int main()
  7. {
  8.          char x[CT], y[CT];
  9.          int n, p=0, i, j;
  10.          f=fopen("cifre1.in", "r");
  11.          g=fopen("cifre1.out", "w+");
  12.          fscanf(f, "%d", &n);
  13.          fclose(f);
  14.          for(i=1; i<=n; i++)
  15.          {
  16.              itoa(i, x, 10);
  17.              for(j=0; x[j]; j++)
  18.              {
  19.                  y[p]=x[j];
  20.                  p++;
  21.              }
  22.          }
  23.          y[p]='\0';
  24.          p=strlen(y);
  25.          fprintf(g, "%d", p);
  26.          fclose(g);
  27.  
  28.          return 0;
  29. }
  30.  
Aceeasi enervanta eroare. Oare compilatorul ala e atat de vechi?
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Problema cifre

Postby andreiandreiq » 26 Jan 2012, 22:52

@Cosmin: Încearcă alta metoda fără itoa, cred ca sunt si alte functii, uitate aici un pic, si aici. Sunt diverse metode, trebuie doar sa înțelegi cum se folosesc.
0,0p / 0 votes
Image
User avatar
andreiandreiq
Word
 
Joined: 30 Dec 2009
Status: 33.33

Re: Problema cifre

Postby begood » 26 Jan 2012, 23:21

{1-9} = 9
{10-99} = 9*20 = 180
{100-999} = 9*300 = 2700

{1-999} = 9 * (1* 10^0 +2 * 10^1 + 3 * 10^2) = 9 * Sum[10^(n - 1) n, {n, 1, 3}], unde 3 este nrCifre (999) (notez cu * http://www.wolframalpha.com ).

{1-256} = {1-99} + {100-199} + {200-249} + {250-256} = 660

{1-99} = 189, calculati cu formula (*)
{100-199} = (2-1) * 300 = 300, acel 300 este nrCifre * 10^(nrCifre(N)-1)
{200-249} = 5 * 30 = 150, 30 = nrCifre * 10^(nrCifre(N)-2)
{250-256} = (6+1) * 3 = 21, 3 = nrCifre * 10^(nrCifre(N)-3)
---------------
189 + 300 + 150 + 21 = 660.

De aici programul e usor de scris.
0,0p / 0 votes
User avatar
begood
Bit
 
Joined: 08 Mar 2011
Status: 0

Re: Problema cifre

Postby Cosmin_NTG » 27 Jan 2012, 17:59

Da, interesant. Nu m-as fi gandit la asta. Ai explicat chiar inteligibil, lucru pentru care iti multumesc. Mai ramane o problema: atunci cand numarul are mai mult de 3 cifre, ce operatie se face inainte de inmultirea cu acel numar calculabil (300, 150 si 21 - aceste numere le pot calcula din formula).
Mai exact:
Aici: {100-199} = (2-1) * 300 = 300, acel 300 este nrCifre * 10^(nrCifre(N)-1) prima cifra a lui n, adica 2 se micsoreaza cu 1. Aici: {200-249} = 5 * 30 = 150, 30 = nrCifre * 10^(nrCifre(N)-2) a 2-a cifra a lui n, adica 5, ramane asa.
Aici: {250-256} = (6+1) * 3 = 21, 3 = nrCifre * 10^(nrCifre(N)-3) ultima cifra a lui n, adica 6 se mareste cu 1. Daca numarul are, spre exemplu 4 cifre, ce operatie se face cu prima cifra? Oare exista o ordine a operatiilor?
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Problema cifre

Postby begood » 27 Jan 2012, 18:06

din cifra cu rang cel mai mare de exemplu 5 din numarul de 4 cifre 5326 se scade intotdeauna 1, iar la unitati se adauga intotdeauna 1.
restul nu se modifica.
0,0p / 0 votes
User avatar
begood
Bit
 
Joined: 08 Mar 2011
Status: 0

Re: Problema cifre

Postby Cosmin_NTG » 27 Jan 2012, 20:09

Allright! Thanks again!
@Andrei: am incercat cu acele stringuri insa a intervenit o problema de incompatibilitate la un moment dat. Multumesc pentru ajutor!

L.E. (-- 27 Jan 2012, 19:09 --)

Ceva e in neregula. Ruleaza bine doar pe 3 teste (15 puncte in total). La celelalte (11) imi da wrong answer. S-a strecurat pe undeva vreo greseala pe care nu reusesc sa o gasesc.
Line number On/Off | Expand/Contract | Select all
  1. #include<iostream>
  2. #include<cmath>
  3. #include<fstream>
  4. using namespace std;
  5. ifstream f("cifre1.in");
  6. ofstream g("cifre1.out");
  7.  
  8. int main()
  9. {
  10.      int n, i=1, v[16], k, s1=0, j;
  11.      double s=0, z=0;
  12.      f>>n;
  13.      f.close();
  14.      k=n;
  15.      while(n)
  16.      {   v[i]=n%10;
  17.          n=n/10;
  18.          s++;
  19.          i++;
  20.      }
  21.      i--;
  22.      if(k<10)
  23.      g<<k;
  24.      else if((k>=10)&&(k<100))
  25.      g<<(k-9)*s+9;
  26.      else
  27.      {   z=2;
  28.          for(j=i-1; j>=2; j--)
  29.          {
  30.              s1=s1+v[j]*s*pow(10, s-z);
  31.              z++;
  32.          }
  33.          g<<189+(v[i]-1)*s*pow(10, s-1)+s1+(v[1]+1)*s;
  34.  
  35.      }
  36.      g.close();
  37.      return (0);
  38.  
  39. }
  40.  
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Problema cifre

Postby likeromanian » 29 Jan 2012, 21:31

Am invatat asta chiar acum cateva luni.O poti face folosind doar:
for(i=1;i<=n;i++)
while(n>0)
n=n/10; nrcif++;
0,0p / 0 votes
User avatar
likeromanian
Bit
 
Joined: 29 Jan 2012
Status: 0

Re: Problema cifre

Postby Cosmin_NTG » 29 Jan 2012, 21:52

Si tu crezi ca asta ar rula sub 0.1 secunde pentru...sa zicem...1923?
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Problema cifre

Postby cata45 » 29 Jan 2012, 22:02

Aici este o rezolvare de 100. Iti poti da seama de formula foarte usor. Ia cateva exemple mici. :)
Line number On/Off | Expand/Contract | Select all
  1. int main ()
  2. {
  3.     fscanf(f,"%Ld",&n);
  4.     p=1;coef=9;
  5.     aux=n;
  6.     while(aux>9)
  7.     {
  8.         nrc=nrc+p*coef;
  9.         aux=aux/10;
  10.         p++;
  11.         coef=coef*10;
  12.         ex=ex*10+9;
  13.     }
  14.     nrc=nrc+(p*(n-ex));
  15.     fprintf(g,"%Ld",nrc);
  16. }
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: Problema cifre

Postby Cosmin_NTG » 29 Jan 2012, 22:26

Wow! Poti explica un pic cum ai gandit-o?

L.E. (-- 29 Jan 2012, 21:26 --)

Ceva nu merge. Am pus-o pe site si imi da 0 puncte.
Line number On/Off | Expand/Contract | Select all
  1. #include<stdio.h>
  2. FILE *f, *g;
  3. int n, aux, p, coef, nrc, ex;
  4. int main()
  5. {   f=fopen("cifre1.in", "r");
  6.     g=fopen("cifre1.out", "w+");
  7.  
  8.     fscanf(f, "%Ld", &n);
  9.     fclose(f);
  10.     p=1;coef=9;
  11.     aux=n;
  12.     while(aux>9)
  13.     {
  14.         nrc=nrc+p*coef;
  15.         aux=aux/10;
  16.         p++;
  17.         coef=coef*10;
  18.         ex=ex*10+9;
  19.     }
  20.     nrc=nrc+(p*(n-ex));
  21.     fprintf(g, "%Ld", nrc);
  22.     fclose(g);
  23.     return (0);
  24. }
  25.  
Sper sa nu fi gresit la implementare.
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Problema cifre

Postby likeromanian » 30 Jan 2012, 10:04

Buna!Asa ne-a explicat profesorul .Daca pui ld(long) si ai pus int o sa primesti un cadou insuportabil.Incearca de forma:


#include<stdio.h>
using namespace std;
freopen(" .in","r",stdin);
freopen(" .out","w",stdout)

...
return 0; // nu return (0);!

sau

#include<fstream.h>
int main(){
int...
ifstream f("date1.in");
ofstream g("date1.out");
f>>
....

g<< ;
f.close();
g.close();
return 0;
}
0,0p / 0 votes
User avatar
likeromanian
Bit
 
Joined: 29 Jan 2012
Status: 0

Re: Problema cifre

Postby cata45 » 30 Jan 2012, 15:16

^^ Imi spui ce nume ai pe campion? Sau un link catre borderoul de evaluare al sursei. :)
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: Problema cifre

Postby Cosmin_NTG » 30 Jan 2012, 20:38

Numele de utilizator este CosminNTG. Am observat o gresala de implementare (este de fapt observatia Marei): n-ul trebuia declarat de tip long pentru ca il citesc in format long. Am modificat sursa:
Line number On/Off | Expand/Contract | Select all
  1. #include<stdio.h>
  2. FILE *f, *g;
  3. int aux, p, coef, nrc, ex;
  4. unsigned long long n;
  5. int main()
  6. {   f=fopen("cifre1.in", "r");
  7.     g=fopen("cifre1.out", "w+");
  8.  
  9.     fscanf(f, "%Ld", &n);
  10.     fclose(f);
  11.     p=1;coef=9;
  12.     aux=n;
  13.     while(aux>9)
  14.     {
  15.         nrc=nrc+p*coef;
  16.         aux=aux/10;
  17.         p++;
  18.         coef=coef*10;
  19.         ex=ex*10+9;
  20.     }
  21.     nrc=nrc+(p*(n-ex));
  22.     fprintf(g, "%Ld", nrc);
  23.     fclose(g);
  24.     return (0);
  25. }
  26.  
. Cu toate acestea, tot esueaza pe 2 teste. Aici este link-ul catre borderoul de evaluare: http://campion.edu.ro/arhiva/index.php?page=source&action=view&id=103936.
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10

Re: Problema cifre

Postby likeromanian » 30 Jan 2012, 22:28

Ooo,imi cer scuze ca nu m-am prins.Tu faceai in limbaj c si de aia era ceva modificat...Acum mi-am dat seama dupa ce m-am uitat la borderou.Imi cer scuze:)
0,0p / 0 votes
User avatar
likeromanian
Bit
 
Joined: 29 Jan 2012
Status: 0

Re: Problema cifre

Postby cata45 » 30 Jan 2012, 23:00

^^ incearca sa inlocuiesti "%Ld" cu "%lld" si poti sa tii toate variabilele de tip long long (nu unsigned long long)
0,0p / 0 votes
The EARTH without ART is just EH.
User avatar
cata45
Byte
 
Joined: 02 Sep 2010
Status: 9

Re: Problema cifre

Postby morpheus » 31 Jan 2012, 17:17

^^^ %lld e ok pentru gcc, dar ... specificatorii de format pentru a parsa long long nu sunt standard in C89, asta inseamna ca codul tau in general nu va fi portabil.
0,0p / 0 votes
Curiosity killed the cat
User avatar
morpheus
Word
 
Joined: 30 Dec 2009
Location: Bucharest, Romania
Status: 54.84

Re: Problema cifre

Postby likeromanian » 31 Jan 2012, 21:18

Incearca sa faci in c++.e mult mai usor.
0,0p / 0 votes
User avatar
likeromanian
Bit
 
Joined: 29 Jan 2012
Status: 0

Re: Problema cifre

Postby Cosmin_NTG » 31 Jan 2012, 21:30

Am reusit, in final. Am pus toate variabilele de tip unsigned long long. Thanks a lot guys! \m/
0,0p / 0 votes
"Cel mai de neinteles lucru din lumea asta este acela ca lumea poate fi inteleasa" A.Einstein
User avatar
Cosmin_NTG
Byte
 
Joined: 11 Jan 2011
Location: 192.2L1.44G
Status: 10
Post a reply

Return to C / C++

Who is online

Users browsing this forum: No registered users and 0 guests


Powered by phpBB © phpBB Group
cron