Szczegółowe omówienie zadania “Liczby pechowe”

Szczegółowe omówienie zadania “Liczby pechowe”

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;
}
Kod C++ programu Liczby pechowe, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz