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

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

Szczegółowe omówienie zadania Liczby pechowe:

https://youtu.be/RvhRrdDvc30?t=7033

Omawia Mikołaj Bulge – laureat Olimpiady Informatycznej Juniorów, prowadzący koło zaawansowane OIJ w XIV Liceum / Staszic / Warszawa.

Link do zadania:
https://szkopul.edu.pl/problemset/problem/E5C9eMtXETZumVeWPrUaklAL/site/?key=statement

Zadanie pochodzi z I etapu XIV Olimpiady Informatycznej Juniorów.
Jest najtrudniejszym zadaniem w I etapie XIV OIJ.
Zadanie wymaga generacji wszystkich możliwości (backtracking i wyboru tych które spełniają warunki zadania.
——-
Poniżej kod wzorcowy do zadania użyty przez Mikołaja:
#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;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz