Szczegółowe
Link do powyższego omówienia 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/
–
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;
}