First Appearance in the Sequence
National Olympiad — Regional round (2019 season)
Submission name: sequence.cpp
Problem summary
Block K is the integer sequence 1,2,…,K−1,K,K−1,…,2,1. Concatenate blocks K=1,2,3,…, treating each integer as one term even when it has multiple digits. Find the 1-based position where n first appears.
Source clarification. The third output is 7 in the rendered official PDF. Its text extraction can misleadingly appear as 17; the sequence definition and the visible sample agree on 7.
Input
One positive integer n.
Output
The first position of the term n.
Constraints
1 ≤ n ≤ 1000000.
Worked example
An independently prepared example for this explanation.
Input
1
Output
1
Solution analysis
- The number n cannot occur in a block with a smaller peak. It first occurs in block n, at that block’s n-th position, while the block is increasing.
- Block K has 2K−1 terms. Before block n there are 1+3+…+(2n−3)=(n−1)² terms. Add the offset n to obtain (n−1)²+n.
- For n=3, the first two blocks are [1] and [1,2,1], totaling four terms. In the third block [1,2,3,2,1], the 3 is the third term, giving overall position 4+3=7.
Why it works
All earlier blocks have maximum below n, so none contains n. Block n reaches n after its first n terms. Summing the odd lengths of earlier blocks gives (n−1)², so adding n yields the first possible and actual occurrence.
Watch out. Count sequence elements, not decimal characters. The result can exceed 32-bit range.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
long long n;
cin >> n;
// Earlier blocks have total length 1+3+...+(2*n-3) = (n-1)^2.
cout << (n - 1) * (n - 1) + n << '\n';
}