Official
Solution 2: analyze from the positions of
C - Hurdle Parsing Editorial by en_translator
Solution 1: scan the string and analyze
The string starts with |
.
After ignoring this initial character, the problem can be solved by scanning the string as follows:
- Prepare a variable \(c=0\).
- If you find
-
, add \(1\) to the variable \(c\). - If you find
|
, we find that \(A_i=\) (current) \(c\). Record that, and set \(c=0\).
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int c=0;
vector<int> a;
for(int i=1;i<s.size();i++){
if(s[i]=='-'){
c++;
}
else{
a.push_back(c);
c=0;
}
}
for(int i=0;i<a.size();i++){
if(i){cout << " ";}
cout << a[i];
}cout << "\n";
return 0;
}
Solution 2: analyze from the positions of |
Suppose that |
are at positions \(X_1,X_2,\dots\). Then, \(A_i = S_{i+1}-S_{i}-1\).
For example, if \(S=\) |-|-|-|------|
, then \(X=(1,3,5,7,14)\), so \(S\) is indeed generated from \(A=(1,1,1,6)\).
Thus, once you find \(X\) you can also easily find \(A\). Here, \(X\) can be found with a for
loop.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
vector<int> x;
for(int i=0;i<s.size();i++){
if(s[i]=='|'){x.push_back(i);}
}
for(int i=1;i<x.size();i++){
if(i>1){cout << " ";}
cout << x[i]-x[i-1]-1;
}cout << "\n";
return 0;
}
posted:
last update: