<span>HDU3183 A Magic Lamp</span>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#define MAXN 1005;
char a[MAXN];
int ans[MAXN],f[MAXN][20];
int minc(int i,int j)
{
    return a[i]<=a[j]?i:j;
}
void ST(int n)
{
    for(int i=0; i<n; i++) f[i][0]=i;
    for(int j=1; (1<<j)<=n; j++)
        for(int i=0; i+(1<<j)-1<n; i++)
            f[i][j]=minc(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int getmin(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return minc(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    int m;
    while(~scanf("%s%d",a,&m))
    {
        int n=strlen(a),p=-1;
        ST(n);
        for(int i=1; i<=n-m; i++)
        {
            p=getmin(p+1,m+i-1);
            ans[i]=a[p]-'0';
        }
        int i;
        for(i=1; i<=n-m; i++)
            if(ans[i]) break;
        if(i>n-m)printf("0\n");
        else
        {
            for(; i<=n-m; i++)
            {
                printf("%d",ans[i]);
            }
            printf("\n");
        }
    }
    return 0;
}