Recovering a Password
National Olympiad — Municipal round
Submission name: pass.cpp
Problem summary
A password is a sequence of at least two integers in 1…100. It is partitioned into blocks of at least two elements, with arbitrary positive distractor integers inserted before, between or after blocks. The first given sequence is this expanded sequence; the second replaces each password block with its sum and leaves distractors unchanged. Recover the password in its original order.
Input
N; N integers; M; M integers.
Output
The recovered password, with spaces between its numbers.
Constraints
1 < N < 100; 0 < M < N. All sequence values are positive. The input is valid and the password is unique.
Worked example
An independently prepared example for this explanation.
Input
5 8 1 2 9 7 4 8 3 9 7
Output
1 2
Solution analysis
- For each second-sequence value, consume consecutive first-sequence values until their sum reaches it.
- If the group has at least two elements, append all of them to the password. A single element is a distractor.
Why it works
Positive entries make prefix sums strictly increasing, so the group matching each second-sequence value has a unique endpoint. Groups of length at least two are exactly replaced password blocks.
Watch out. Do not output the sums. Positivity is essential to the greedy grouping.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Positive entries make prefix sums strictly increasing, so the group matching each second-
// sequence value has a unique endpoint. Groups of length at least two are exactly replaced password
// blocks.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n,m;
cin>>n;
vector<long long>a(n);
for(auto&x:a){
cin>>x;
}
cin>>m;
int p=0;
vector<long long>ans;
while(m--){
long long target;
cin>>target;
int start=p;
long long sum=0;
while(sum<target){
sum+=a[p++];
}
if(p-start>=2){
for(int j=start;j<p;j++){
ans.push_back(a[j]);
}
}
}
for(int i=0;i<(int)ans.size();i++){
cout<<ans[i]<<(i+1==(int)ans.size()?'\n':' ');
}
}