C - ±1 Operation 1 Editorial by en_translator
First, \(D<0\) is difficult to handle with, so let us canonicalize as follows, so that \(D \ge 0\):
- Replace \(A=A+D \times (N-1)\) and \(D=-D\) (simultaneously).
This is equivalent to reversing the arithmetic progression. For example, if \(A=8,D=-3,N=3\), then the sequence \(S=(8,5,2)\), but by replacing with \(A=2,D=3,N=3\), we have \(S=(8,5,2)\), the reversed version of the previous one, while the set of “good numbers” stays invariant.
Solution 1: Find the nearest element of \(S\) to \(X\) by binary search
Sequence \(S\) contains \(A+kD\) for all integer \(k\) such that \(0 \le k \le N-1\). Since \(D \ge 0\), \(S\) is weakly monotonically increasing, so we can find the nearest element of \(S\) to \(X\) by binary searching over \(k\).
Sample code (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
long long x,a,d,n;
cin >> x >> a >> d >> n;
if(d<0){
long long fi=a+d*(n-1);
a=fi;
d*=-1;
}
long long st=0,fi=(n-1);
while(st<=fi){
long long te=(st+fi)/2;
if((a+d*te)<x){st=te+1;}
else{fi=te-1;}
}
long long res=8e18;
for(long long i=max(0ll,st-5);i<=min((n-1),st+5);i++){
res=min(abs(a+d*i-x),res);
}
cout << res << '\n';
return 0;
}
Solution 2: Resort to case division
Let \(st=A\) and \(fi=A+(N-1)D\) be the minimum and maximum value in the arithmetic progression, respectively.
- When \(st \le X \le fi\),
- If \(D = 0\), then the answer is \(0\).
- Otherwise, for all integer \(K\) such that \(0 \le k \le N-1\), \(S\) contains \(A+kD\), and \(A \le X \le A+(N-1)D\), so the answer is \(\min((X-A)\%D,D-(X-A)\%D)\) (where \(p\%q\) denotes the remainder when \(p\) is divided by \(q\)).
- When \(X < st\), the answer is \(st-X\).
- When \(fi < X\), the answer is \(X-fi\).
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
long long x,a,d,n;
cin >> x >> a >> d >> n;
if(d<0){
long long fi=a+d*(n-1);
a=fi;
d*=-1;
}
long long st=a;
long long fi=a+d*(n-1);
if(st<=x && x<=fi){
long long m;
if(d!=0){m=(x-st)%d;}
else{m=0;}
cout << min(m,d-m) << '\n';
}
else if(x<st){cout << st-x << '\n';}
else{cout << x-fi << '\n';}
return 0;
}
posted:
last update: