Szczegółowe omówienie zadania Liczby pechowe:
Link do powyższego omówienia zadania Liczby pechowe:
–
Zadanie Liczby pechowe wymaga generacji wszystkich możliwości (backtracking i wyboru tych które spełniają warunki zadania.
–
Zadanie Liczby pechowe pochodzi z I etapu XIV Olimpiady Informatycznej Juniorów.
Jest najtrudniejszym zadaniem w I etapie XIV OIJ.
Omawia Mikołaj Bulge – laureat Olimpiady Informatycznej Juniorów, prowadzący koło zaawansowane OKI.
–
Oficjalne materiały Olimpiady Informatycznej Juniorów: omówienie zadania oraz kod wzorcowy zadania:
https://oij.edu.pl/oij14/etap1/zadania/
——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625
——-
Kod C++ programu Liczby pechowe, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include<bits/stdc++.h>
using namespace std;
long long n;
int res=0;
long long p10[15];
void backtrack(long long current, int power, int sigma, int last, bool was13){
long long newcurrent;
if(power==-1){
if(sigma==13&&was13) res++;
return;
}
for(int i=0; i<=9; i++){
newcurrent=current+p10[power]*i;
if(newcurrent>n||sigma+i>13) break;
if(last==1&&i==3) backtrack(newcurrent,power-1,sigma+i,i,1);
else backtrack(newcurrent,power -1,sigma+i,i,was13);
}
}
int main(){
int sajz=0;
cin>>n;
p10[0]=1;
for(int i=1; i<=14; i++) p10[i]=p10[i-1]*10;
for(int i=0; i<=13; i++){
if(p10[i]>n) break;
sajz++;
}
backtrack(0,sajz,0,0,0);
cout<<res;
}