Lizak – Omówienie zadania z I etapu Olimpiady Informatycznej

Lizak – Omówienie zadania z I etapu Olimpiady Informatycznej

Szczegółowe omówienie zadania Lizak.
I etap Olimpiady Informatycznej Licealistów:

Link do powyższego omówienia zadania Lizak:
https://youtu.be/cf1_M4sHTHw?t=978
Zadanie Lizak wymaga jedynie pomysłu!
Bardzo motywujące zadanie które pokazuje że możemy spokojnie wystartować w Olimpiadzie Informatycznej!
Zadanie Lizak pochodzi z I etapu XVIII Olimpiady Informatycznej Licealistów:
https://szkopul.edu.pl/task_archive/oi/
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
———

#include<bits/stdc++.h>
using namespace std;

constexpr int M=2e6+7;

pair<int,int>ans[M];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m,k,totalsum=0,firstone=-1,lastone=-1,ptr1,ptr2,currentsum;
	string s;
	
	cin >> n >> m >> s;
	
	for(int i=0; i<n; i++){
		if( s[i] == 'T' ) totalsum+=2;
		else{
			totalsum++;
			lastone = i;
			if( firstone == -1 ) firstone = i;
		}
	}
	for(int i=0; i<M; i++) ans[i]={-1,-1}; 		
	
	
	ptr1 = 0; //początek aktualnego fragmentu
	ptr2 = n-1; //koniec aktualnego fragmentu
	currentsum = totalsum;
	
	while(currentsum>0){
		ans[currentsum] = {ptr1,ptr2};
		
		if( s[ptr1] == 'T' ) ptr1++;
		else if( s[ptr2] == 'T' ) ptr2--;
		else{ //na obu końcach są W
			ptr1++;
			ptr2--;
		}
		
		currentsum-=2;
	}
	
	
	if( firstone <= (n-1) - lastone ){
		ptr1 = firstone+1;
		ptr2 = n-1;
		currentsum = totalsum - ( 2*firstone ) - 1;
	}
	else{
		ptr1 = 0;
		ptr2 = lastone-1;
		currentsum = totalsum -  2*( (n-1) - lastone ) - 1;
	}

	while(currentsum>0){
		ans[currentsum] = {ptr1,ptr2};
		
		if( s[ptr1] == 'T' ) ptr1++;
		else if( s[ptr2] == 'T' ) ptr2--;
		else{ //na obu końcach są W
			ptr1++;
			ptr2--;
		}
		
		currentsum-=2;
	}
	
	
	while(m--){
		cin >> k;
		
		if(ans[k].first!=-1) cout << ans[k].first+1 << ' ' << ans[k].second+1 << '\n';
		else cout << "NIE\n";
	}
	
	return 0;
}
Kod C++ programu Lizak, który jest omówiony w powyższym filmie i który otrzymuje 100% 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz