結果
| 問題 | No.491 10^9+1と回文 |
| ユーザー |
 IL_msta
|
| 提出日時 | 2017-03-11 02:07:43 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 103 |
ソースコード
#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 regiontypedef 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 regiontemplate<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;//OVFret %= MOD;}return ret;}#pragma endregion //組み合わせnCk(,10^5)#pragma region CGLclass 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 regiontemplate<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==Cvector< 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 mainsigned main(void){std::cin.tie(0);std::ios::sync_with_stdio(false);std::cout << std::fixed;//小数を10進数表示cout << setprecision(16);//小数点以下の桁数を指定solve();}#pragma endregion //main()