Largest Polygon Number
National Olympiad — Municipal round
Submission name: maxn.cpp
Problem summary
Digits are placed around a regular n-sided polygon. Start at any vertex and visit every vertex once, clockwise or counterclockwise. Find the largest decimal number that this produces.
Input
n, followed by n space-separated digits in clockwise order.
Output
The largest obtainable number, written as a string of digits.
Constraints
3 ≤ n ≤ 15; at least one digit is nonzero.
Worked example
An independently prepared example for this explanation.
Input
4 1 9 2 8
Output
9281
Solution analysis
- There are n choices of start and two directions, hence only 2n candidates.
- Construct each candidate by circular indexing.
- All candidates have n digits, so ordinary string comparison gives the same order as numeric comparison.
- Keep the largest candidate. A string avoids overflow for long numbers.
Why it works
Every permitted traversal is identified by its first vertex and direction. Both are enumerated, so the maximum examined string is the requested answer.
Watch out. C++ remainder can be negative. Add n before taking the remainder on each backward step.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>digit(n);
for(int&x:digit){
cin>>x;
}
string best;
for(int start=0;start<n;++start){
for(int dir:{-1,1}){
string candidate;
int position=start;
for(int j=0;j<n;++j){
candidate+=char('0'+digit[position]);
position=(position+dir+n)%n; // Wrap around the polygon.
}
if(candidate>best){
best=candidate;
}
}
}
cout<<best<<'\n';
}