Length after Folding a Labeled Strip
Autumn Tournament (2009)
Submission name: strip.cpp
Problem summary
Fold a unit-width strip at a sequence of original boundary labels. All layers at the selected location fold together and remain glued. Find the final length. Labels that coincide refer to the same current fold line.
Input
n k; then k original boundary labels from0 through n.
Output
The final strip length.
Constraints
n is a positive integer with at most18 decimal digits; k≤10000.
Worked example
Original statement sample.
Input
7 2 3 2
Output
3
Solution analysis
- Always describe the current strip by coordinates0..length. Folding at coordinate c maps every old position x to |x−c|. The new length is max(c,length−c). This convention may reverse the drawn orientation, but orientation does not affect any future labeled fold.
- To find the current position of an original label p, replay all earlier transformations: p←|p−c1|, then p←|p−c2|, and so on. Store the current-coordinate fold lines, not their original labels. At most10000 folds means at most about50million simple transformations.
- For n=7, folding at original label3 gives c=3 and length4. Original label2 is now at |2−3|=1, so the second fold leaves max(1,4−1)=3. An endpoint fold is harmless: it may reverse orientation but leaves length unchanged.
Why it works
The absolute-value map sends both sides of a fold to their distances from the crease and exactly represents coincident glued layers. Applying all stored maps to an original label therefore gives its true current location. The farthest of the two endpoints determines the new length, establishing the algorithm by induction over folds.
Watch out. Do not allocate n cells: n may be near10^18. Store every crease in current coordinates. A crease at an endpoint is valid. Signed64-bit arithmetic is sufficient for coordinates and their differences.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
long long length;
int count;
cin>>length>>count;
vector<long long>creases;
for(int i=0;i<count;i++){
long long position;
cin>>position;
for(long long crease:creases){
// Replay how the original label moves under previous folds.
position=position>=crease?position-crease:crease-position;
}
length=max(position,length-position);
creases.push_back(position);
}
cout<<length<<'\n';
}