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