Omówienie zadania Spy-string (Codeforces poziom F.)

Omówienie zadania Spy-string (Codeforces poziom F.)

Szczegółowe omówienie zadania Spy-string:

Link do powyższego omówienia zadania Spy-string:
https://youtu.be/V6axb24D1dw?t=855
Link do treści zadania Spy-string:
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;
}
Link do pliku ze wzorcowym kodem C++ zadania Spy-string 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz