A Power from Consecutive Digits
National Olympiad — National round (2017 season)
Submission name: 100.cpp
Problem summary
Insert plus/minus signs between some consecutive base-p digits 0,1,…,p−1 so the expression equals a positive power of p. More trailing zeroes earn more points in this scored optimization task.
Source clarification. The official analysis does not establish the optimal exponent for general bases and explicitly describes the constructions as asymptotically optimal. This implementation guarantees expression validity and impossibility decisions; its general-case score is not guaranteed maximal.
Input
Base p in decimal.
Output
NO if impossible, otherwise dots for the p digits in order with inserted + and − signs.
Constraints
2 ≤ p ≤ 1000. Score for a valid expression is proportional to its exponent relative to the best known exponent.
Worked example
An independently prepared example for this explanation.
Input
10
Output
.+...+.-.+..-..
Solution analysis
- This is a scored construction problem: validity is provable, while a maximum exponent is not claimed for all bases. For p≤16 use expressions found by exhaustive enumeration of all three choices at every digit gap. For p≡1 (mod 4), parity proves impossibility; p=2 is also impossible.
- For p=4k+2, concatenate blocks 1…k+1, k+2…2k+1, 2k+2…3k+1, 3k+2…4k+1 with signs +,−,−,+. Their value is p^k. For p=4k+3, use blocks 1…k−1, k…2k, 2k+1…3k+1, 3k+2…4k+2 with signs +,−,−,+. Start with digit zero and explicitly separate nonempty blocks.
- For p=4k+8≥20, use the nine blocks 1; 2…k; k+1…2k; 2k+1…2k+2; 2k+3…2k+4; 2k+5…3k+4; 3k+5…4k+4; 4k+5…4k+6; 4k+7 with signs −,−,+,−,−,+,−,+,−. The value is p^k. In base ten the sample expression is 0+123+4−5+67−89=100.
Why it works
When p=4k+1, p is odd and every term has the parity of its digit sum. Changing signs preserves parity, so every obtainable expression has parity p(p−1)/2, which is even; every positive power of p is odd, making a solution impossible. For the other cases, substitute each consecutive block into the finite geometric-sum formula; cancellation leaves exactly p^k. Equivalently align the block digits by place value and cancel their constant per-column sums. The small-base table is verified exhaustively. These constructions establish valid answers for all remaining bases but do not prove globally maximal exponents.
Watch out. Do not print numerical digit symbols above nine: the required format uses dots. Do not advertise maximum scores for the general constructions; they are asymptotically optimal, with exponents floor(p/4) or p/4−2.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
// Algorithm: This is a scored construction problem: validity is provable, while a maximum
// exponent is not claimed for all bases.
using namespace std;
int main(){
int base;
cin>>base;
const string small[]={"","","NO","..+.",".-.+.+.","NO","...-.-.+.","...+.-.+..","...-.+.+..+.",
"NO",".+...+.-.+..-..","..-.+...+...+..","..-..+...+...+.-.","NO",".....-...-...+...",
".....+.-.+.-..+.-..-..",".....+.+.+.-..+.-.-..-.."};
if(base<=16){
cout<<small[base]<<'\n';
return 0;
}
if(base%4==1){
cout<<"NO\n";
return 0;
}
string answer=".";
auto block=[&](char sign,int first,int last){
if(first>last){
return;
}
answer+=sign;
answer+=string(last-first+1,'.');
};
if(base%4==2){
int k=base/4;
block('+',1,k+1);
block('-',k+2,2*k+1);
block('-',2*k+2,3*k+1);
block('+',3*k+2,4*k+1);
}
else if(base%4==3){
int k=base/4;
block('+',1,k-1);
block('-',k,2*k);
block('-',2*k+1,3*k+1);
block('+',3*k+2,4*k+2);
}
else{
int k=(base-8)/4;
block('-',1,1);
block('-',2,k);
block('+',k+1,2*k);
block('-',2*k+1,2*k+2);
block('-',2*k+3,2*k+4);
block('+',2*k+5,3*k+4);
block('-',3*k+5,4*k+4);
block('+',4*k+5,4*k+6);
block('-',4*k+7,4*k+7);
}
cout<<answer<<'\n';
}