Codeforces Round #268 DIV1 C問題/DIV2 E問題 - Hack it!

Source

Codeforces Round #268 DIV1 C問題 (1500pt)
Codeforces Round #268 DIV2 E問題 (2500pt)
Problem description

問題概要

$f(x)$ を $x$ を $10$ 進数で表記した時の数字の和とする．例えば，$f(112) = 1+1+2 = 4$．
正整数 $A$ が与えられるので
$\displaystyle \qquad \left(\sum_{x=L}^R f(x) \right)\ {\rm mod}\ A = 0$
となる $L,R$ を $1$ つ求める問題．
$L, R$ は $L < R$ で $10^{200}$ 未満でなければいけない．
答えが存在することは保証されている．

解法

$\displaystyle \qquad g(l,r) =\sum_{x=l}^r f(x)$
と書くことにする．
色々あるけど，以下の方法でやった．
まず，大きい整数 $x$ に対して $g(0,x)$ を計算する方法は，桁ごとの周期性を利用して，$1$ の桁ではいくら，$10$ の桁ではいくら…，と計算すれば良い．
$g(x,y) = g(0,y) - g(0,x-1)$ なので，任意の $g(x,y)$ は高速に計算することができる．
$L=1$ として，$g(L,R) \geq A$ となる最小の $R$ を二分探索で求めた．
その後，$g(L,R) < A$ なら $R$ を $1$ 増やす，$g(L,R) > A$ なら $L$ を $1$ 増やす，$g(L,R) = 0$ になれば終了と，尺取法を行った．
$L$ や $R$ を $1$ 増やした時に $g(L,R)$ の値の変化は高々数十で，ランダムにそれぐらい変化すると思えば，高々 $100$ 回ぐらいの試行で $g(L,R) = A$ となるものが見つけるのは想像に難くない．
実際にどのようなケースでもその程度で終わるかどうかはよくわからないが，実際のところは大丈夫そう．

他の方法は，$k$ が高々 $18$ 桁の正整数の場合，$g(k,10^{18}+k-1)$ は $k$ が $1$ 増えると $1$ 増える．
よって，適当な $k$ に対して，$g(k, 10^{18}+k-1)$ を計算して，後どれぐらい増やせば ${\rm mod}\ A$ で $0$ になるかを調べれば良い．
$k=1$ とか $k=10^{18}+1$ の時などは，$g(k, 10^{18}+k-1)$ が簡単に計算できる．

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

ll A;
ll L, R;

ll solve(ll N){
  ll i, j, k, p;
  ll res = 0;

  p = 1;
  for(;;){
    if(N < p) break;
    res += (N/(p*10)) * 45 * p;
    k = N%(p*10);
    rep(i,10){
      j = min(p, k);
      k -= j;
      res += j * i;
    }
    p *= 10;
  }

  return res;
}

int main(){
  int i, j, k;
  ll lef, rig, cen;
  ll val;

  reader(&A);
  L = 1;
  lef = 0; rig = 20000000000000000LL;
  while(lef < rig){
    cen = (lef + rig) / 2;
    R = cen;
    val = solve(R+1) - solve(L);
    if(val < A) lef = cen + 1; else rig = cen;
  }

  for(;;){
    val = solve(R+1) - solve(L);
    if(val==A) break;
    if(val<A) R++;
    else      L++;
  }
  writer(L, ' ');
  writer(R, '\n');

  myed;
  return 0;
}

Current time: 2024年04月25日10時45分01秒
Last modified: 2014年09月24日06時21分30秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF268 CF_Div1_C CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン：