https://www.acmicpc.net/problem/1078
1078번: 뒤집음
어떤 수를 뒤집는다는 것은 오른쪽부터 다시 쓰는것이다. 예를 들어, 1234를 뒤집으면 4321이 되고, 100을 뒤집으면 1이 된다. (앞에 0은 무시) 어떤 수 D가 주어질 때, x – (x를 뒤집은 수)가 D가 되는
www.acmicpc.net
자릿수에 관한 관찰이 필요한 문제이다. 따라서 0-based index로
이때 문제의 정답이 되는 최소의 자연수를
1.
2.
3.
1,2번 식을 3번 식에 대입하여 정리하면 다음과 같은 식을 얻을 수 있다.
여기서 임의의 음이 아닌 정수
다만,
우리는
위의 모든 풀이가 정답의 길이
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll ipow(ll a,int n){
if(n==0)return 1;
if(n==1)return a;
if(n==2)return a*a;
ll res = ipow(a*a,n/2);
if(n%2)res *= a;
return res;
}
ll f(ll D,int l){
ll res = 0;
ll Dp=D;
for(int i=0;2*i<l;i++){
if(D%10>0||(D%10==0&&i!=0))res += D%10*ipow(10,l-i);
if(D%10==0&&i==0)res += ipow(10,l-i)+(l-i!=i)*ipow(10,i);
if(D%10<0)res -= D%10*ipow(10,i);
D-=D%10*(ipow(10,l-2*i)-1)/9;
D/=10;
}
if(D)return -1;
else return res;
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
ll D;
cin>>D;
if(D%9){
cout<<"-1";
return 0;
}
D/=9;
for(int i=1;i<=17;i++){
ll r = f(D,i);
if(r!=-1){
cout<<r;
return 0;
}
}
cout<<"-1";
return 0;
}
'알고리즘' 카테고리의 다른 글
FORTRAN I Compiler's Operator-precedence parsing Algorithm (Operator ordering with string replacing) (0) | 2022.07.30 |
---|---|
[BOJ Solution] BOJ2727 - 2,3 거듭제곱의 합 (0) | 2022.06.28 |
[BOJ Solution] BOJ9556 - 수학 숙제 (0) | 2022.06.19 |