Time Machine on a Circular Calendar
National Olympiad — National round (2010 season)
Submission name: machine.cpp
Problem summary
Extract the digits from a text. Form the largest and smallest numbers using all of them, without a leading zero, then travel their difference years forward from 2010 on the cycle 1005…4020.
Input
A text of at most 18 characters, containing at least one nonzero digit.
Output
The final calendar year.
Constraints
1 ≤ number of extracted digits ≤ 18. The inclusive calendar cycle has 3016 years.
Worked example
Input and output for the worked example discussed below.
Input
TiMe323MacHiNe0
Output
3297
Solution analysis
- Sort the extracted digits. Ascending order gives the minimum after swapping its first digit with the first nonzero digit; descending order gives the maximum. Keeping a leading zero would incorrectly turn the minimum into a shorter number.
- The calendar visits every integer year from 1005 through 4020, then returns to 1005, so its period is 4020−1005+1=3016. Convert year 2010 to offset 1005, add the travel difference modulo 3016, and convert back.
- For digits 3,2,3,0 the extremal numbers are 3320 and 2033. Their difference is 1287, and 2010+1287=3297 does not yet wrap. All 18-digit inputs fit signed 64-bit.
Why it works
Ascending digits with the smallest possible nonzero first digit minimize a fixed-length number; descending digits maximize it. Their difference is exactly the specified travel time. Modular arithmetic on offsets in an inclusive 3016-year cycle reproduces each wrap.
Watch out. The cycle length includes both endpoint years. Ignore letters, preserve all zeros after the leading-digit adjustment, and use long long for the numbers.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cctype>
#include<iostream>
#include<string>
using namespace std;
int main(){
string text;
getline(cin,text);
string digits;
for(unsigned char character:text){
if(isdigit(character)){
digits+=char(character);
}
}
sort(digits.begin(),digits.end());
string minimum=digits;
size_t firstNonzero=minimum.find_first_not_of('0');
swap(minimum[0],minimum[firstNonzero]);
reverse(digits.begin(),digits.end());
long long difference=stoll(digits)-stoll(minimum);
const int period=4020-1005+1;
// Convert to a zero-based offset in the inclusive calendar cycle.
cout<<1005+(2010-1005+difference%period)%period<<'\n';
}