#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int get(int x){if(x==0||x==4||x==6||x==9) return 1;else if(x==1||x==2||x==3||x==5||x==7) return 0;else return 2;
}
LL dp[20][20][20]; //dp[pos][num][sum]前pos位，num已经出现了sum次
LL digit[20];LL dfs(int pos, int num, int sum, bool lead, bool limit){if(pos==0) return sum;if(!limit&&!lead&&dp[pos][num][sum]!=-1) return dp[pos][num][sum];int up=limit?digit[pos]:9;LL ans=0;if(!lead||pos==1) ans+=dfs(pos-1, num, sum+(num==0), 0, limit&&digit[pos]==0);else ans+=dfs(pos-1, num, sum, 1, limit&&digit[pos]==0);for(int i=1; i<=up; i++){ans+=dfs(pos-1, num, sum+(num==i), 0, limit&&digit[pos]==i);}if(!limit&&!lead) dp[pos][num][sum]=ans;return ans;
}LL f(LL x, int num){if(x<0) return 0;if(x==0) return num==0?1:0;int pos=0;while(x){digit[++pos]=x%10;x/=10;}return dfs(pos,num,0,1,1);
}
int main(){int T;LL a, b;scanf("%d", &T);memset(dp, -1, sizeof(dp));while(T--){LL ans = 0;scanf("%lld%lld", &a,&b);for(int i=0;i<=9;i++) ans+=(f(b,i)-f(a-1,i))*get(i);printf("%lld\n", ans);}
}

幼儿园的孩子们正在做游戏，每个人都有自己的帮派，帮派之间打架，然后赢者吞并弱者扩大自己的势力。最开始每个孩子的帮派中只有自己，然后接下来有会有两个人打架，这两个人会集结自己所属的势力开始打架，打赢的一方就会吞并输的一方，当然如果x，y是一个势力就不会打起来。有些聪明的小朋友会将自己的糖分给其他小朋友引诱他离开所属势力加入到自己势力。又有一些小朋友会对现在的势力不满，然后反叛出去自立门户。

作为打架的双方，只有人数大于另一方才能打赢。即：人数相等则没有输赢，两个帮派没有变化。

幼儿园里面共有N个孩子，接下来有M次操作，操作有如下4种
1)  query      查询现在有多少个势力。
2)  fight x y  表示x，y打架.并输出"z is winner!"胜利的一方(z是x或y),如果没有打平则输出"Either is winner!".如果x,y属于同一个势力不会打架,当然也不用输出.
3)  tempt x y  表示x诱惑y、将y拉入x的势力。
4)  revolt x   表示x反叛，（自立门户）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000010;
int n, m, cnt, ans, num[maxn], fa[maxn], Rank[maxn];
int find_set(int x){if(x==fa[x]) return x;else return fa[x] = find_set(fa[x]);
}
void del(int x){int fx = find_set(num[x]);if(Rank[fx]==1) return;Rank[fx]--;num[x] = ++cnt;fa[num[x]] = num[x];Rank[num[x]]=1;ans++;
}
int main(){int T;int ks = 0;scanf("%d", &T);while(T--){scanf("%d%d", &n,&m);for(int i=1; i<=n; i++) fa[i]=i,num[i]=i,Rank[i]=1;string op;ans = n;cnt = n;printf("Case #%d:\n", ++ks);while(m--){cin >> op;if(op=="query"){printf("%d\n", ans);}else if(op=="fight"){int x, y;scanf("%d%d", &x,&y);int fx = find_set(num[x]);int fy = find_set(num[y]);if(fx == fy) continue;if(Rank[fx]>Rank[fy]){printf("%d is winner!\n", x);fa[fy] = fx;Rank[fx] += Rank[fy];Rank[fy] = 0;ans--;}else if(Rank[fx]<Rank[fy]){fa[fx] = fy;Rank[fy] += Rank[fx];Rank[fx] = 0;ans--;printf("%d is winner!\n", y);}else{printf("Either is winner!\n");}}else if(op=="tempt"){int x,y;scanf("%d%d", &x,&y);int fx = find_set(num[x]);del(y);int fy = find_set(num[y]);if(fx ==fy) continue;fa[fy] = fx;Rank[fx] += Rank[fy];Rank[fy] = 0;ans--;}else if(op=="revolt"){int x;scanf("%d", &x);int fx = find_set(num[x]);if(Rank[fx]==1) continue;Rank[fx]--;num[x] = ++cnt;fa[num[x]] = num[x];Rank[num[x]]=1;ans++;}}}
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 100010;
LL dp[maxn];
struct node
{LL l, r;LL maxx;
} Tree[maxn * 4];
void push_up(LL rt)
{Tree[rt].maxx = max(Tree[rt << 1].maxx, Tree[rt << 1 | 1].maxx);
}
void build(LL l, LL r, LL rt)
{Tree[rt].maxx = 0;Tree[rt].l = l;Tree[rt].r = r;if (l == r) return;LL mid = (l + r) / 2;build(l, mid, rt << 1);build(mid + 1, r, rt << 1 | 1);push_up(rt);
}
void update(LL pos, LL val, LL rt)
{if (Tree[rt].l == Tree[rt].r){Tree[rt].maxx = val;return;}LL mid = (Tree[rt].l + Tree[rt].r) / 2;if (pos <= mid) update(pos, val, rt * 2);else update(pos, val, rt * 2 + 1);push_up(rt);
}
LL query(LL L, LL R, LL rt)
{if (L <= Tree[rt].l && Tree[rt].r <= R) return Tree[rt].maxx;LL mid = (Tree[rt].l + Tree[rt].r) / 2;LL ret = -__LONG_LONG_MAX__;if (L <= mid) ret = max(ret, query(L, R, rt << 1));if (mid < R) ret = max(ret, query(L, R, rt << 1 | 1));return ret;
}int main()
{LL n, x, a, y, b, z, c, L, R, temp, A;LL t;while (~scanf("%lld", &n)){scanf("%lld%lld", &x, &a);scanf("%lld%lld", &y, &b);scanf("%lld%lld", &z, &c);scanf("%lld%lld%lld%lld", &L, &R, &temp, &A);build(0, n, 1);for (LL i = 1; i <= n; i++){t = dp[i - 1];if (i >= x) t = max(t, dp[i - x] + a);if (i >= y) t = max(t, dp[i - y] + b);if (i >= z) t = max(t, dp[i - z] + c);LL ll = i - R, rr = i - L;if (ll < 0) ll = 0;if (i >= L) t = max(t, query(ll, rr, 1) + temp + 1LL * i * A - 1LL * L * A);dp[i] = t;update(i, t - 1LL * i * A, 1);}printf("%lld\n", dp[n]);}
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
double maxx[maxn*4];
double a[maxn];
void push_up(int rt){maxx[rt] = max(maxx[rt<<1], maxx[rt<<1|1]);
}
void build(int l, int r, int rt){if(l==r){maxx[rt] = a[l+1]-a[l];return;}int mid=(l+r)/2;build(l, mid, rt<<1);build(mid+1, r, rt<<1|1);push_up(rt);
}
void update(int pos, double val, int l, int r, int rt){if(l==r){maxx[rt] = val;return;}int mid=(l+r)/2;if(pos<=mid) update(pos, val, l, mid, rt*2);else update(pos, val, mid+1, r, rt*2+1);push_up(rt);
}
int query(int L, int R, int l, int r, int rt){if(L<=l&&r<=R) return maxx[rt];int mid = (l+r)/2;if(R<=mid) return query(L, R, l, mid, rt*2);else if(L>mid) return query(L, R, mid+1, r, rt*2+1);else return max(query(L, mid, l, mid, rt*2) , query(mid+1, R, mid+1, r, rt*2+1));
}int main(){int n, q;while(~scanf("%d", &n)){for(int i=1; i<=n; i++) scanf("%lf", &a[i]);build(1, n-1, 1);scanf("%d", &q);while(q--){int x, y;scanf("%d %d", &x,&y);a[x] = y;if(x!=n) update(x,a[x+1]-a[x],1,n-1,1);if(x!=1) update(x-1,a[x]-a[x-1],1,n-1,1);printf("%d.00\n", (int)maxx[1]);}}
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int ls[maxn], rs[maxn];
int ans = 0, flag, n, rt;
int dfs(int u)
{if (ls[u] && rs[u]){int l = dfs(ls[u]);int r = dfs(rs[u]);if (l > r){swap(ls[u], rs[u]);++ans;}return min(l, r);}else if (ls[u]){int l = dfs(ls[u]);if (l > u){swap(ls[u], rs[u]);++ans;}return min(l, u);}else if (rs[u]){int r = dfs(rs[u]);if (r < u){swap(ls[u], rs[u]);++ans;}return min(r, u);}else return u;
}
void print(int u)
{if (ls[u]) print(ls[u]);if (flag) putchar(' ');else flag = 1;printf("%d", u);if (rs[u]) print(rs[u]);
}
int main()
{while (~scanf("%d%d", &n, &rt)){for (int i = 1; i <= n; i++) scanf("%d%d", &ls[i], &rs[i]);flag = 0;dfs(rt);printf("%d\n", ans);print(rt);puts("");}
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
const LL Base[2]={121,131};
const LL Mod[2]={1000000007,1000000009};
int MinmalRep(char *s){int i=0,j=1,k=0,f,l=strlen(s);while(i<l&&j<l&&k<l){f=s[(i+k)%l]-s[(j+k)%l];if(!f)k++;else{if(f>0)i=i+k+1;else j=j+k+1;if(i==j)i++;k=0;}}return min(i,j);
}
char buf[maxn];
LL val[maxn];
//Tarjan
vector <int> G[maxn], s[maxn];
int low[maxn], dfn[maxn], Stack[maxn];
bool inStack[maxn];
int dfsclk,top,scc;
void Tarjan(int u){low[u]=dfn[u]=++dfsclk;Stack[top++]=u;inStack[u]=1;for(auto &v:G[u]){if(!dfn[v]){Tarjan(v);low[u] = min(low[u], low[v]);}else if(inStack[v]){low[u] = min(low[v], dfn[v]);}}if(low[u]==dfn[u]){scc++;int now;do{now=Stack[--top];inStack[now]=0;s[scc].push_back(now);}while(now!=u);}
}
void solve(int n){for(int i=1;i<=n;i++) dfn[i]=inStack[i]=0;dfsclk=top=scc=0;for(int i=1; i<=n; i++) if(!dfn[i]) Tarjan(i);
}
int main(){int n,m;while(~scanf("%d%d", &n,&m)){for(int i=0; i<maxn; i++) G[i].clear();for(int i=0; i<maxn; i++) s[i].clear();for(int i=1;i<=n;i++){scanf("%s", buf);int len=strlen(buf),loc=MinmalRep(buf);LL has[2]={0,0};for(int j=0;j<len;j++){int t=buf[(j+loc)%len]-'a'+1;for(int k=0;k<2;k++){has[k]=(has[k]*Base[k]+t)%Mod[k];}}val[i]=has[0]*Base[0]+has[1];}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);}solve(n);int ans=0;for(int i=1;i<=scc;i++){unordered_map<LL,int>cnt;for(auto &t:s[i]) cnt[val[t]]++;for(auto t:cnt) ans = max(ans,t.second);}printf("%d\n", ans);}
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 202;
const int mod = 1e9+7;
void add(int &x, int y){x += y;if(x>=mod) x%=mod;
}
int a[maxn],b[maxn],c[maxn];
void mul(int f[],int g[],int len){int tmp[maxn];for(int i=0;i<len;i++) tmp[i]=0;for(int i=0;i<len;i++)for(int j=0;j<len;j++)add(tmp[(i+j)%len],1LL*f[i]*g[j]%mod);for(int i=0;i<len;i++) f[i]=tmp[i];
}
int main(){int T,n,m,k;scanf("%d", &T);while(T--){scanf("%d%d%d", &n,&m,&k);for(int i=0;i<n;i++) scanf("%d", &a[i]);for(int i=0;i<n;i++) b[i]=i==0;for(int i=0;i<n;i++){int d=min(i,n-i);c[i]=(d>0&&d<k)*(k-d);}while(m){if(m&1) mul(b,c,n);mul(c,c,n);m/=2;}mul(a,b,n);for(int i=0;i<n;i++){if(i==0) printf("%d", a[i]);else printf(" %d", a[i]);}printf("\n");}
}

#include <bits/stdc++.h>
using namespace std;
const int  M=55;///公式的精度为O(1/(100*M^4))要造数据时把M调到1000 即可有10^-14的精度
const  double e=exp(1);
int c;
inline double F( double x)//原函数
{return 0.5*(log(x+e*c/x)+log(x));
}
inline double D( double x)//导函数
{return 1/(x*x+c*e)-2.0/((x+c*e/x)*(x+c*e/x));
}
inline double fun(int n)
{int i;double ans=0,l=0.5,r=0.5+n,u;if(c<2000||n<=M){l+=M;for(i=1; i<=M&&i<=n; i++){ans+=i/(i*i+c*e);}}if(n>M)ans+=F(r)-F(l)-(D(r)-D(l))/24.0;return ans;
}
int main()
{int n,q,i;double sum;while(scanf("%d%d",&n,&c)!=EOF){printf("%.10f\n",fun(n));}return 0;
}