Fibonacci Crossouts
National Olympiad — Regional round (2009 season)
Submission name: lazy.cpp
Problem summary
Characters of a text are numbered from 1. Cross out each position that is a Fibonacci number (1, 1, 2, 3, 5, …). Count distinct crossed-out positions; the final period is a terminator and is excluded.
Input
A nonempty token with no spaces, terminated by a period.
Output
The number of crossed-out characters.
Constraints
At most 30,000 characters before the terminator. The prose says at least two, but an official example has one.
Worked example
An independently prepared example for this explanation.
Input
Abcdefghij.
Output
5
Solution analysis
- Read the token and subtract one from its length to exclude the final period. The actual characters do not affect which positions are marked.
- Generate the distinct Fibonacci positions as 1, 2, 3, 5, … rather than counting both copies of 1. Count each generated value no greater than the text length.
- A ten-character text has marked positions 1, 2, 3, 5, and 8. The next position, 13, is outside the text, so the answer is five.
Why it works
The loop enumerates each distinct positive Fibonacci number in increasing order. These and only these are crossed-out positions. Stopping at the first value larger than the text length counts exactly the valid positions.
Watch out. Count position 1 once and exclude the final period. The implementation also handles the one-character official example.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int main() {
string text;
cin >> text;
int length = static_cast<int>(text.size()) - 1;
// Generate distinct positions: 1, 2, 3, 5, ... .
int current = 1;
int next = 2;
int answer = 0;
while (current <= length) {
answer++;
int following = current + next;
current = next;
next = following;
}
cout << answer << '\n';
}