Tamflexの貯蔵庫

やる気のない備忘録

codeIQ 2529

codeiq.jp

f,gは割と簡単だけど,hが面倒.

#include <bits/stdc++.h>

#define EPS 1e-10

ll power(ll x,ll n){ll a=1;REP(i,n)a*=x;return a;}

ll f(double a, double b, double c, double d)
{
  double e = 180-(b+c+d);
  double f = 180-(a+b+c);
  a *= M_PI/180;
  b *= M_PI/180;
  c *= M_PI/180;
  d *= M_PI/180;
  e *= M_PI/180;
  f *= M_PI/180;
  double den = sin(b+c);
  double num = cos(b+c)+(sin(b)*sin(d)*sin(f))/(sin(a)*sin(c)*sin(e));
  double ans = atan2(den,num)*180/M_PI+EPS;
  return (ll) (ans*1000000);
}

ll g(ll x)
{
  x--;
  ll ans = 1;
  ll d = 2;
  while(x > 1 && d <=sqrt(x))
  {
    ll t=1,u=d;
    while(x%d==0)
    {
      t+=u;
      u*=d;
      x/=d;
    }
    ans *= t;
    d++;
  }
  if(x>1) ans *= (1+x);
  ans--;
  return ans;
}

ll A[14], B[14], C[14];

void hinit()
{
  A[0]=0;A[1]=45;A[2]=495;
  B[0]=0;B[1]=10;B[2]=10;
  C[0]=0;C[1]=45;C[2]=495;
  ll d=100;
  FOR(i,3,13)
  {
    A[i] = (d+1)*45*B[i-2]+C[i-2]*90;
    B[i] = 10*B[i-2];
    C[i] = (d+1)*45*B[i-2]+C[i-2]*100;
    d*=10;
  }
}

string hminus(string s,ll y)
{
  ll n = s.size();
  ll x = stoll(s)-y;
  if(x<0) return "";
  string t = to_string(x);
  ll c = n-t.size();
  REP(i,c) t="0"+t;
  return t;
}

ll hnum(string s, bool p)
{
  ll n = s.size();
  string t = p ? hminus(s,1) : s;
  if(t.size()==0) return 0;
  string s1 = t.substr(0,ceil(n*0.5));
  string s2 = t.substr(n/2,ceil(n*0.5));
  ll t1 = stoll(s1);
  reverse(s1.begin(),s1.end());
  ll l = stoll(s1);
  ll r = stoll(s2);
  ll e = t1-(l>r)+1;
  return e;
}

ll hsum(string s, int y, bool p)
{
  ll n = s.size();
  string t = p ? hminus(s,1) : s;
  if(t.size()==0) return 0;
  ll x = stoll(t);
  if(n==0) return 0;
  else if(n==1) return (1+x)*x*0.5;
  else if(n==2) return (11+(x/11)*11)*(x/11)*0.5;
  else
  {
    ll ans = 0;
    ll d = power(10,n-1);
    ll e = (x%d)/10;
    FOR(i,y,t[0]-'0'-1) ans += (d+1)*i*B[n-2]+C[n-2]*10;
    string cen = t.substr(1,n-2);
    ans += (d+1)*(t[0]-'0')*hnum(cen,t[0]>t[n-1]);
    ans += hsum(cen,0,t[0]>t[n-1])*10;
    return ans;
  }
}

ll h(ll x)
{
  hinit();
  ll ans = 0;
  string s = to_string(x);
  FOR(i,1,s.size()-1) ans+=A[i];
  ans += hsum(s,1,false);
  return ans;
}

int main()
{
  double a,b,c,d; cin>>a>>b>>c>>d;
  cout << h(g(f(a,b,c,d))) << endl;
  return 0;
}