Szczegółowe omówienie zadania Spy-string:
Link do powyższego omówienia zadania Spy-string:
https://youtu.be/V6axb24D1dw?t=855
https://youtu.be/V6axb24D1dw?t=855
Link do treści zadania Spy-string:
https://codeforces.com/problemset/problem/1360/F
https://codeforces.com/problemset/problem/1360/F
Zadanie Spy-string wymaga jedynie dość prostego pomysłu – nie potrzeba żadnej zaawansowanej algorytmiki.
Zadanie tak naprawdę jest drobną modyfikacją brutalnej metody rozpatrzenia wszystkich możliwych przypadków
Zadanie Spy-string pochodzi z jednej z najbardziej popularnych platform algorytmicznych: Codeforces.
Daje nam piękny wpis do informatycznego CV:
https://youtu.be/QgLyXYmFQeU?t=3507
Zadanie omawia Mikołaj Bulge – prowadzący zajęcia Olimpijskiego Koła Informatycznego, laureat Olimpiad Informatycznych.
https://youtu.be/OC_xrHSMYlA?t=1087
—–
Jak się uczyć na podstawie tego zadania?
https://tiny.pl/7x1gg
——-
Kod C++ programu Spy-string, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include<bits/stdc++.h>
using namespace std;
constexpr int M=17;
string s[M];
string candidate;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,n,m,differences;
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>s[i];
for(int i=0; i<m; i++){
for(char j='a'; j<='z'; j++){
candidate.clear();
for(int k=0; k<i; k++) candidate+=s[1][k];
candidate+=j;
for(int k=i+1; k<m; k++) candidate+=s[1][k];
for(int j=2; j<=n; j++){
differences=0;
for(int k=0; k<m; k++) differences+=(candidate[k]!=s[j][k]);
if(differences>1) goto NOTOK;
}
cout<<candidate<<'\n';
goto OK;
NOTOK:;
}
}
cout<<-1<<'\n';
OK:;
}
return 0;
}