Eight Counts for Olympiad Practice
National Olympiad — National round (2025 season)
Submission name: preparation.cpp
Problem summary
Among integers 1…N, count: even numbers; three-digit numbers; numbers with digit sum four; numbers containing digit 5; powers of two including 1; distinct factorial values 1,2,6,…; decimal palindromes; and Fibonacci values from 1,2,3,5,… .
Input
One integer N.
Output
Eight counts on one line in the stated order.
Constraints
1 ≤ N ≤ 100000.
Worked example
An independently prepared example for this explanation.
Input
14
Output
7 0 2 1 4 3 10 6
Solution analysis
- The limit is small enough to inspect every integer. Count parity and three-digit range directly. Repeated decimal division gives its digit sum, whether digit five appears, and its reversed number for the palindrome test.
- Recognize powers of two by removing factors of two, leaving one. Generate the small set of factorials and Fibonacci numbers once up to N, then test set membership during enumeration.
- For N=14, the digit-sum-four values are 4 and 13; only 5 contains a five. The powers are 1,2,4,8; factorials are 1,2,6; palindromes are 1…9 and 11; Fibonacci values are 1,2,3,5,8,13. These give 7,0,2,1,4,3,10,6.
Why it works
Every integer from 1 to N is inspected once, and each direct predicate is its requested definition. Factorial and Fibonacci generation follows their recurrences and stops after exceeding N, so membership tests are exact. Independent counters therefore count each property correctly.
Watch out. Count the value 1 once as both a power of two and a factorial. Fibonacci begins 1,2, avoiding a repeated 1. Count a number containing several fives only once.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin >> n;
set<int> factorials, fibonacci;
long long factorial = 1;
for (int factor = 1; factorial <= n; factor++) {
factorial *= factor;
if (factorial <= n) {
factorials.insert(static_cast<int>(factorial));
}
}
// Start at 1,2 so Fibonacci values are unique, including a single 1.
int first = 1, second = 2;
while (first <= n) {
fibonacci.insert(first);
int next = first + second;
first = second;
second = next;
}
int count[8] = {};
for (int number = 1; number <= n; number++) {
count[0] += number % 2 == 0;
count[1] += number >= 100 && number <= 999;
int value = number, sum = 0, reversed = 0;
bool hasFive = false;
while (value > 0) {
int digit = value % 10;
sum += digit;
reversed = reversed * 10 + digit;
hasFive = hasFive || digit == 5;
value /= 10;
}
count[2] += sum == 4;
count[3] += hasFive;
value = number;
while (value % 2 == 0) {
value /= 2;
}
count[4] += value == 1;
count[5] += factorials.count(number) != 0;
count[6] += reversed == number;
count[7] += fibonacci.count(number) != 0;
}
for (int i = 0; i < 8; i++) {
if (i > 0) {
cout << ' ';
}
cout << count[i];
}
cout << '\n';
}