|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Gaus
|
Profesor Đurić u poslednje vreme ima velikih problema sa svojim nestašnim đacima.
Da bi ih smirio, odlučio je da im da, na prvi pogled, mnogo težak zadatak. U prošlosti
su se često primenjivale takve mere smirivanja, i omiljen zadatak je bio sabiranje prvih
1000 brojeva. Ali, otkako je mali Gaus našao način da brzo izračuna taj zbir, profesori
su morali da promene zadatak. I tako je prof. Đurić smislio sledeće: daće đacima nenegativne
cele brojeve A i B, i tražiće od njih da mu kažu koliko brojeva iz intervala
[A,B] (tj. svi brojevi veći ili jednaki od A i manji ili jednaki od B) ima paran zbir
cifara (npr, zbir cifara broja 1234 je 1 + 2 + 3 + 4 = 10, dakle paran broj). Međutim,
među đacima se nalazi i mali Draganče koji, poput malog Gausa, želi da što pre reši
taj zadatak i nastavi da pravi probleme prof. Đuriću. Kako Draganče nije uspeo da nađe
rešenje zadatka, pomoć je potražio od njegovih drugova, mladih programera.
Ulaz:
(Ulazni podaci se nalaze u datoteci gaus.in) U prvom redu tekstualne datoteke
zapisani su brojevi A i B, odvojeni jednim razmakom.
Izlaz:
(Izlazne podatke upisati u datoteku gaus.out) U izlaznu datoteku ispisati samo
jedan broj - koliko ima brojeva iz intervala [A,B] takvih da im je zbir cifara paran broj.
Ograničenja:
- 0 ≤ A ≤ B ≤ 230
- vremensko ograničenje za izvršavanje programa je 1 s.
Primer 1:
Primer 2:
|
|
fajl: gaus.cpp
|
// Gaus, Okruzno 2007
#include <cstdio>
#include <vector>
using namespace std;
vector<int> cifra;
long count(long n, bool paran, bool manje){
if (n==-1){
if (paran) return 1;
else return 0;
}
else{
long ret=0;
if (manje){
ret += 5*count(n-1,paran,true) + 5*count(n-1,!paran,true);
}
else{
if (cifra[n]%2==0) ret += count(n-1, paran, false);
else ret += count(n-1,!paran,false);
if (cifra[n]>0){
int p=1 + (cifra[n]-1)/2;
int np=(1 + cifra[n]-1)/2;
ret += p * count(n-1,paran,true);
ret += np * count(n-1,!paran,true);
}
}
return ret;
}
}
int main(){
long A,B;
FILE *f;
f=fopen("gaus.10.in","r");
fscanf(f,"%ld %ld",&A,&B);
fclose(f);
long res=0;
while (B>0){
cifra.push_back(B%10);
B/=10;
}
res+=count(cifra.size()-1,true,false);
cifra.clear();
A--;
while (A>0){
cifra.push_back(A%10);
A/=10;
}
res-=count(cifra.size()-1,true,false);
f=fopen("gaus.10.out","w");
fprintf(f,"%ld\n",res);
fclose(f);
return 0;
}
|
|
|