Question

Problema control1 - Campion


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Cifra de control a unui număr natural se obţine prin adunarea cifrelor numărului; dacă rezultatul obţinut este o cifră, aceea este cifra de control a numărului dat; în caz contrar, se calculează suma cifrelor rezultatului obţinut, aplicând în mod repetat acest procedeu până când se obţine un rezultat de o singură cifră.
De exemplu cifra de control a numărului 998979 este 6, deoarece:
9+9+8+9+7+9 = 51, apoi
5+1 = 6
Cerinţă

Fiind date două numere naturale a şi b , precum şi o cifră c , să se determine câte numere cuprinse între a şi b , inclusiv a şi b , au cifra de control egală cu c .
Date de intrare

Fişierul de intrare control1.in conţine pe prima linie valorile a b c separate prin câte un spaţiu.
Date de ieşire

Fişierul de ieşire control1.out va conţine o singură linie pe care va fi scris un număr natural k care reprezintă numărul de valori cuprinse între a şi b (inclusiv) care au cifra de control egală cu c .
Restricţii

1 ≤ a ≤ b ≤ 2000000000
1 ≤ c ≤ 9
control1.in
10056 10105 7
control1.out
6
Explicaţii
Cele 6 numere care au cifra de control 7 cuprinse între 10056 şi 10105 sunt:
10060: 1+0+0+6+0 = 7
10069: 1+0+0+6+9 = 16; 1+6 = 7
10078: 1+0+0+7+8 = 16; 1+6 = 7
10087: 1+0+0+8+7 = 16; 1+6 = 7
10096: 1+0+0+9+6 = 16; 1+6 = 7
10105: 1+0+1+0+5 = 7

sursa mea de 40
#include

using namespace std;
ifstream f("control1.in");
ofstream g("control1.out");
int cifControl(int x)
{
if(x==0)
return 0;
if(x%9==0)
return 9;
return x%9;
}
int main()
{
unsigned long long int a,b,c,k=0;
f>>a>>b>>c;
for(int i=a;i<=b;i++)
if(cifControl(i)==c)
k++;
g< f.close();
g.close();
return 0;
}

Answer 1

Sursa ta primeste doar 40 de puncte deoarece este pur si simplu solutia standard de a parcurge toate numerele si a le verifica cifra de control, ceea ce nu e eficient pentru un interval mare! Atentie mare la restrictiile problemei, mai ales la cele de concurs cand lucrezi!!!

Solutie de 100 de puncte

#include <iostream>

#include <fstream>

int a, b, c, Nr, cc, n;

int main(){

   ifstream f("control1.in");

   ofstream g("control1.out");

   cin>>a>>b>>c;

   if (c>b) cout<<0;//printf("0");

   else{

       // caut primul, apoi aplic formula

       Nr=a-1;

       do{

           cc=++Nr;            // salvez numarul in cc = cifra de control

           do{

               n=cc;           // pastrez vechea cifra de control pentru lucru

               cc=0;           // o reinitializez cu 0 - aici calculez suma cifrelor

               while(n){

                   cc+=n%10; // aduna ultima cifra

                   n/=10;      // scapa de ea

               }

           }while(cc>=10); // pana cand am obtinut o cifra de control < 10

       }while(cc!=c);      // pana cand am gasit primul

       cout<<(b-Nr)/9+1;

   }

   return 0;

}