Szczegółowe omówienie zadania “Zabawa Bajtka”

Szczegółowe omówienie zadania “Zabawa Bajtka”

Szczegółowe omówienie zadania  Zabawa Bajtka:

https://youtu.be/DsYaobsHhSk?t=4947

Omawia Jasiek Strzeszyński – zwycięzca Olimpiady Informatycznej Juniorów i złoty medalista Europejskiej Olimpiady Informatycznej Juniorów

Link do zadania:
https://szkopul.edu.pl/problemset/problem/zabawa/site/

Zadanie jest analogicznym zadaniem do zadania Liczby Pechowe z XIV Olimpiady Informatycznej Juniorów:
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 w powyższym omówieniu który otrzymuje 100%:
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
int n,k,w;
string s,akt;
void solve(int mi,int mx)
{
	int i,j;
	for(i=0;i+s.size()-1<akt.size();i++)
	{
		for(j=0;j<s.size();j++) { if(s[j]!=akt[i+j]) break; } if(j>=s.size())
		{
			w++;
			break;
		}
	}
	if(akt.size()==n)
		return;
	for(char c=max('a',(char)(mx-k));c<=min('z',(char)(mi+k));c++) { akt+=c; solve(min(mi,(int)c),max(mx,(int)c)); akt.pop_back(); } return; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>k>>s;
	for(char c='a';c<='z';c++)
	{
		akt=c;
		solve(c,c);
	}
	cout<<w<<"\n";	
	return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz