Locate a Repeated Number
National Olympiad — National round (2023 season)
Submission name: row.cpp
Problem summary
Group k consists of the next k unused positive integers, each repeated k times. Thus the sequence begins 1,2,2,3,3,4,4,4,5,5,5,6,6,6,… . Find its Nth element.
Input
One integer N.
Output
The value at one-based position N.
Constraints
1 < N < 10^18; memory limit 2 MB.
Worked example
An independently prepared example for this explanation.
Input
13
Output
6
Solution analysis
- Group k has k² positions, so its last position is S(k)=k(k+1)(2k+1)/6. Binary search the smallest k with S(k)≥N.
- The preceding groups use k(k−1)/2 distinct values. Inside group k, position offset N−S(k−1) is one-based and each value occupies k positions. Its zero-based value offset is (N−S(k−1)−1)/k.
- For N=13, S(2)=5 and S(3)=14, so group 3 contains the answer. Its offset is 8, hence its third repeated value is 3+1+floor(7/3)=6. Divide the factors in the square-sum formula before multiplying to keep 64-bit arithmetic safe.
Why it works
The increasing cumulative sizes identify exactly the group containing N. There are k(k−1)/2 values in earlier groups, and integer division counts the full length-k runs before the target within its group. Adding these offsets gives the required value.
Watch out. Positions are one-based; subtract one before dividing the offset. A search bound of 2000000 covers N<10^18 and keeps the canceled square-sum products within signed 64-bit range.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
long long squareSum(long long k) {
long long a = k, b = k + 1, c = 2 * k + 1;
// Cancel the denominator before multiplying the square-sum factors.
if (a % 2 == 0) {
a /= 2;
} else {
b /= 2;
}
if (a % 3 == 0) {
a /= 3;
} else if (b % 3 == 0) {
b /= 3;
} else {
c /= 3;
}
return a * b * c;
}
int main() {
long long n;
cin >> n;
long long low = 1, high = 2000000;
while (low < high) {
long long middle = (low + high) / 2;
if (squareSum(middle) >= n) {
high = middle;
} else {
low = middle + 1;
}
}
long long k = low;
long long offset = n - squareSum(k - 1) - 1;
cout << k * (k - 1) / 2 + 1 + offset / k << '\n';
}