結果

問題 No.491 10^9+1と回文
ユーザー IL_mstaIL_msta
提出日時 2017-03-11 02:07:43
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 8,035 bytes
コンパイル時間 2,207 ms
コンパイル使用メモリ 139,428 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 08:28:12
合計ジャッジ時間 4,238 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 1 ms
5,248 KB
testcase_16 AC 1 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 1 ms
5,248 KB
testcase_19 AC 1 ms
5,248 KB
testcase_20 AC 1 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 1 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 1 ms
5,248 KB
testcase_26 AC 1 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 1 ms
5,248 KB
testcase_29 AC 1 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 1 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 1 ms
5,248 KB
testcase_35 AC 1 ms
5,248 KB
testcase_36 AC 1 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
testcase_39 AC 2 ms
5,248 KB
testcase_40 AC 1 ms
5,248 KB
testcase_41 AC 1 ms
5,248 KB
testcase_42 AC 1 ms
5,248 KB
testcase_43 AC 1 ms
5,248 KB
testcase_44 AC 2 ms
5,248 KB
testcase_45 AC 2 ms
5,248 KB
testcase_46 AC 2 ms
5,248 KB
testcase_47 AC 1 ms
5,248 KB
testcase_48 AC 2 ms
5,248 KB
testcase_49 AC 1 ms
5,248 KB
testcase_50 AC 1 ms
5,248 KB
testcase_51 AC 1 ms
5,248 KB
testcase_52 AC 2 ms
5,248 KB
testcase_53 AC 1 ms
5,248 KB
testcase_54 AC 1 ms
5,248 KB
testcase_55 AC 1 ms
5,248 KB
testcase_56 AC 2 ms
5,248 KB
testcase_57 AC 2 ms
5,248 KB
testcase_58 AC 2 ms
5,248 KB
testcase_59 AC 1 ms
5,248 KB
testcase_60 AC 2 ms
5,248 KB
testcase_61 AC 2 ms
5,248 KB
testcase_62 AC 2 ms
5,248 KB
testcase_63 AC 1 ms
5,248 KB
testcase_64 AC 1 ms
5,248 KB
testcase_65 AC 1 ms
5,248 KB
testcase_66 AC 1 ms
5,248 KB
testcase_67 AC 1 ms
5,248 KB
testcase_68 AC 2 ms
5,248 KB
testcase_69 AC 1 ms
5,248 KB
testcase_70 AC 1 ms
5,248 KB
testcase_71 AC 2 ms
5,248 KB
testcase_72 AC 1 ms
5,248 KB
testcase_73 AC 2 ms
5,248 KB
testcase_74 AC 2 ms
5,248 KB
testcase_75 AC 1 ms
5,248 KB
testcase_76 AC 2 ms
5,248 KB
testcase_77 AC 1 ms
5,248 KB
testcase_78 AC 2 ms
5,248 KB
testcase_79 AC 2 ms
5,248 KB
testcase_80 AC 1 ms
5,248 KB
testcase_81 AC 1 ms
5,248 KB
testcase_82 AC 1 ms
5,248 KB
testcase_83 AC 1 ms
5,248 KB
testcase_84 AC 2 ms
5,248 KB
testcase_85 AC 2 ms
5,248 KB
testcase_86 AC 1 ms
5,248 KB
testcase_87 AC 2 ms
5,248 KB
testcase_88 AC 1 ms
5,248 KB
testcase_89 AC 2 ms
5,248 KB
testcase_90 AC 1 ms
5,248 KB
testcase_91 AC 1 ms
5,248 KB
testcase_92 AC 2 ms
5,248 KB
testcase_93 AC 2 ms
5,248 KB
testcase_94 AC 1 ms
5,248 KB
testcase_95 AC 2 ms
5,248 KB
testcase_96 AC 2 ms
5,248 KB
testcase_97 AC 1 ms
5,248 KB
testcase_98 AC 1 ms
5,248 KB
testcase_99 AC 1 ms
5,248 KB
testcase_100 AC 2 ms
5,248 KB
testcase_101 AC 1 ms
5,248 KB
testcase_102 AC 1 ms
5,248 KB
testcase_103 AC 1 ms
5,248 KB
testcase_104 AC 1 ms
5,248 KB
testcase_105 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region GNUC
//以下を参考にした
//https://yukicoder.me/wiki/auto_vectorization
#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#endif
#pragma endregion

#define _USE_MATH_DEFINES

#pragma region
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <cstring>
#include <vector>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
/////////
//定数
const int INF = (int)1e9;
const int MOD = (int)1e9+7;
const LL LINF = (LL)1e18;
/////////
using namespace::std;
/////////
#pragma region Math
// 最大公約数
template<class T>
inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}
//inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}

// 最小公倍数
template<class T>
inline T lcm(T a, T b){return a / gcd(a, b) * b;}
//inline T lcm(T a, T b){return a * b / gcd(a, b);}

template<class T>
T powMod(T num,int n,T mod=MOD){
	if( n == 0 ){
		return (T)1;
	}
	T mul = num;
	T ans = (T)1;
	while(n){
		if( n&1){
			ans = (ans*mul)%mod;
		}
		mul = (mul*mul)%mod;
		n >>= 1;
	}
	return ans;
}
#pragma endregion //math
#pragma region
template<class T>
void UNIQUE(vector<T>& vec){
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end() );
}
#pragma endregion // sort erase unique
////////////////////////////////
struct edge{int to;LL cost;};
edge make_edge(int to,LL cost){
	edge ret = {to,cost};
	return ret;
}
#pragma region //グラフ
void dijkstra(int root,int V,vector<LL>& dist,
	vector< vector<edge> > G	){
	priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > que;
	dist.assign(V,LINF);
	dist[root] = 0;
	que.push(pair<LL,int>(0,root));//距離、頂点番号

	while( !que.empty() ){
		pair<LL,int> p = que.top();que.pop();
		int v = p.second;
		if( dist[v] < p.first ) continue;
		for(int i=0;i < (int)G[v].size();++i){
			edge e = G[v][i];
			if( dist[e.to] > dist[v] + e.cost ){
				dist[e.to] = dist[v] + e.cost;
				que.push(pair<LL,int>(dist[e.to],e.to));
			}
		}
	}
}
#pragma endregion //ダイクストラ法:O(|E|log|V|)
#pragma region //グラフ
void warshall_floyd(vector<vector<LL> >& dist,int V,const LL INF=LINF){
	for(int k=0;k<V;++k){
		for(int i=0;i<V;++i){
			if( dist[i][k] >= INF ) continue;
			for(int j=0;j<V;++j){
				if( dist[k][j] >= INF )continue;
				dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
}
#pragma endregion //ワーシャルフロイド:O(|V|**3)
#pragma region 
//http://sugarknri.hatenablog.com/entry/2016/07/16/165715
//LL inv[1000010];
void makeinv(vector<LL>& inv,const LL P){
	int i;
	inv = vector<LL>(1000010,0);
	inv[1]=1;
	for(i=2;i<=1000000;i++){
		inv[i] = inv[P%i] * (P-P/i)%P;//OVF
	}
}

ULL nCk(ULL N,ULL k){
	static vector<LL> inv;
	if( inv.size() == 0 ){
		makeinv(inv,MOD);
	}
	k = min(k,N-k);
	if( k == 0 ){return 1;}
	if( k == 1 ){return N%MOD;}
	ULL ret = 1;
	for(int i=1;i<=k;++i){
		ret *= ((N+1-i)*inv[i])%MOD;//OVF
		ret %= MOD;
	}
	return ret;
}
#pragma endregion //組み合わせnCk(,10^5)
#pragma region CGL
class Point{
public:
	double x,y;
	Point(double x=0,double y=0):x(x),y(y){}

	Point	operator +	(Point p){return Point(add(x,p.x),add(y,p.y));}
	void	operator +=	(Point p){x=add(x,p.x);y=add(y,p.y);}
	Point	operator -	(Point p){return Point(add(x,-p.x),add(y,-p.y));}
	void	operator -=	(Point p){x=add(x,-p.x);y=add(y,-p.y);}
	Point	operator *	(double a){return Point(x*a,y*a);}
	double	operator *	(Point p){return dot(p);}
	Point	operator /	(double a){return Point(x/a,y/a);}

	double norm(){return sqrt(x*x+y*y);}
	double dot(Point p){return add(x*p.x,y*p.y);}
	double rot(Point p){return add(x*p.y,-y*p.x);}
	double add(double a,double b){
		double EPS = 1e-10;
		if( abs(a+b) < EPS*(abs(a)+abs(b)) ){
			return 0;
		}
		return a+b;
	}
};
istream& operator>>(istream& in,Point& P){
	in >> P.x >> P.y;
	return in;
}

//線分p1-p2上に点qがあるか判定
bool on_seg(Point p1,Point p2,Point q){
	return (p1-q).rot(p2-q) == 0 && (p1-q).dot(p2-q) <= 0;
}
Point intersection(Point p1,Point p2,Point q1,Point q2){
	return p1+(p2-p1)*((q2-q1).rot(q1-p1)/(q2-q1).rot(p2-p1));
}
enum PointPotion{ON_SEGMENT,COUNTER_CLOCKWISE,ONLINE_BACK,CLOCKWISE,ONLINE_FRONT};
PointPotion ccw(Point A,Point B,Point C){
	B -= A;C -=A;
	if( B.rot(C) > 0 ) return COUNTER_CLOCKWISE;
	if( B.rot(C) < 0 ) return CLOCKWISE;
	if( B.dot(C) < 0 ) return ONLINE_BACK;
	if( B.norm() < C.norm() ) return ONLINE_FRONT;
	return ON_SEGMENT;
}
#pragma endregion //class Point
#pragma region
//辞書順で比較
bool cmp_x(const Point& p,const Point& q){
	if( p.x != q.x ) return p.x < q.x;
	return p.y < q.y;
}

//凸包を求める
vector<Point> convex_hull(vector<Point> ps,int n){
	sort(ps.begin(),ps.end(), cmp_x);
	int k = 0;//凸包の頂点数
	vector<Point> qs(n*2);//構築中の凸包
	//下側の凸包の作成
	for(int i=0;i<n;++i){
		while(k>1 && (qs[k-1]-qs[k-2]).rot(ps[i]-qs[k-1]) <=0){
			k--;
		}
		qs[k++] = ps[i];
	}
	//上側凸包の作成
	for(int i=n-2,t=k;i>=0;i--){
		while(k>t && (qs[k-1]-qs[k-2]).rot(ps[i]-qs[k-1]) <=0){
			k--;
		}
		qs[k++] = ps[i];
	}
	qs.resize(k-1);
	return qs;
}
#pragma endregion //凸包
#pragma region 
template<class T,class U>
istream& operator>>(istream& in,pair<T,U> P){
	in >> P.first >> P.second;
	return in;
}
#pragma endregion //cin pair<T,U>
#pragma region 
#pragma endregion //
const double PI = acos(-1.0);
const double EPS = 1e-9;

//行列の積
vector< vector<LL> > MUL( vector<vector<LL> > A,vector< vector<LL> > B,LL mod=MOD){
	int R = A.size();
	int cen = A[0].size();
	int C = B[0].size();
	vector< vector<LL> > ans(R,vector<LL>(C,0) );
	for(int row=0;row<R;++row){
		for(int col=0;col<C;++col){
			for(int inner=0;inner< cen;++inner){
				ans[row][col] = (ans[row][col] + A[row][inner]*B[inner][col])%mod;
			}
		}
	}
	return ans;
}
vector< vector<LL> > powMat(vector< vector<LL> > mat,LL N){
	int R = mat.size();
	int C = mat[0].size();
	//R==C
	vector< vector<LL> > I(R,vector<LL>(C,0));//単位元
	for(int i=0;i<R && i<C;++i){
		I[i][i] = 1;
	}
	if( N == 0 ){
		return I;
	}
	vector< vector<LL> > mul(R,vector<LL>(C)),ans(R,vector<LL>(C));
	ans = I;
	mul = mat;
	while(N){
		if( N & 1 ){
			ans = MUL(ans,mul);
		}
		N >>= 1;
		mul = MUL(mul,mul);
	}
	return ans;
}

void solve(){
	LL N;
	cin >> N;
	LL dat = (LL)1e9+1;
	LL A = (LL)1e9;
	LL a = N/A;
	LL b = N%A;
	LL c = 0;
	if( a > b ){
		--a;
	}
	c = a;
	if( a == 0 ){cout << 0 << endl;return;}
	
	vector<LL> kai(10);
	kai[1] = 9;
	kai[2] = 9;
	for(int i=3;i<10;++i){
		kai[i] = (LL)9*powMod((LL)10,(i-1)/2,(LL)100000000000);
	}
	
	vector< vector<LL> > dp(2,vector<LL>(11,0));
	int ket = 0;
	
	LL temp = c;
	vector<int> num;
	while(temp){
		++ket;
		num.push_back(temp%10);
		temp/=10;
	}
	reverse(num.begin(),num.end());
	
	//すべての桁を使う回文を調べる
	int cen = (ket-1)/2+1;//折り返し地点
	dp[0][0] = 1;
	dp[1][0] = max(0,num[0]-1);//ここでは0を入れない
	for(int i=1;i<cen;++i){
		dp[0][i] = dp[0][i-1];
		dp[1][i] = dp[1][i-1]*10 + num[i];
	}
	LL res = 0;
	for(int i=1;i<ket;++i){//短い桁の回文を全部足す
		res += kai[i];
	}
	res += dp[1][cen-1];
	
	int add = 1;
	for(int i=cen-1;i>=0;--i){
		if( num[i] == num[ket-i-1] ){
			continue;
		}else if(num[i] < num[ket-i-1]){
			add = 1;
			break;//すでに小さくなっている
		}else{//num[i] > num[ket-i-1]
			add = 0;
			break;
		}
	}
	res += add;
	cout << res << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定
	
	solve();
}
#pragma endregion //main()
0