休闲赛18

contest

A OUHE_csc

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int main()
{
    int x, res;
    scanf("%d", &x);
    res = x;
    int n = 0;
    for(int i = 0; i < 31; i ++)
        if(x >> i & 1)  n = max(n, i);
    for(int i = 0; i < n; i ++)
    {
        x = (x << 1) % (1 << (n + 1)) | (x >> n & 1);
        res = max(res, x);
    }
    printf("%d", res);
    return 0;
}

B OUHE_csc

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 1 << n; i ++)
    {
        printf("%d:", i);
        for(int j = 0; j < n; j ++)
            if(i >> j & 1)  printf(" %d", j);
        puts("");
    }
    return 0;
}

C OUHE_csc

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    n --, m --;
    int res = n / m;
    if(n % m)  res ++;
    printf("%d", res);
    return 0;
}

D Calculus9

#include<stdio.h>
double cal(long long x)
{
    long long sum=0,temp=x;
    while(x)
    {
        sum+=x%10;
        x/=10;
    }
    return (double)temp/sum;
}
int main()
{
    long long num=0,bot=1,temp1,temp2;
    int k;
    scanf("%d",&k);
    while(1)
    {
        while(1)
        {
            temp1=num+bot;
            temp2=num+bot*10;
            if(cal(temp1)<=cal(temp2))break;
            else bot=temp2-num;
        }
        num+=bot;
        printf("%lld\n",num);
        k--;
        if(!k)break;
    }
}

E OUHE_csc

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
int num(int x)
{
    int res = 0;
    while(x)  res += x % 10, x /= 10;
    return res;
}
int f(int x)
{
    int res = 0;
    while(x > 9)
    {
        res += x;
        x = num(x);
    }
    res += x;
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = n; i >= n - 10000 && i >= 1; i --)
    {
        if(f(i) == n)
        {
            printf("%d", i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

F Calculus9

#include<stdio.h>
#include<math.h>
int main()
{
    double n,a,b;
    scanf("%lf",&n);
    a=(double)((int)n+1);
    b=sqrt(2)*n;
    printf("%.10lf\n",a>b?a:b);
}

G OUHE_csc

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1010;
const LL INF = 1e18;
PII a[N];
set<PII> S;
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        S.insert({a[i].x, a[i].y});
    }
    LL res = INF;
    for(int i = 0; i < n; i ++)
        for(int j = i + 1; j < n; j ++)
        {
            int x1 = a[i].x, y1 = a[i].y;
            int x2 = a[j].x, y2 = a[j].y;
            if(x1 == x2 || y1 == y2)  continue;
            if(S.count({x1, y2}) && S.count({x2, y1}))
                res = min(res, (LL)abs(x1 - x2) * abs(y1 - y2));
        }
    if(res == INF)  res = -1;
    printf("%lld", res);
    return 0;
}

H

I OUHE_csc

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 55, M = 100010, INF = 0x3f3f3f3f;
int w[N];
int f[M];
int main()
{
    int n, t = 1;
    while(scanf("%d", &n), n)
    {
        bool flag = true;
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &w[i]);
            if(i > 1 && w[i] % w[i - 1])  flag = false;
        }
        if(w[1] != 1)  printf("Case #%d: Cannot pay some amount\n", t ++);
        else if(flag)  printf("Case #%d: OK\n", t ++);
        else{
            int m = w[n] * 2;
            f[0] = 0;
            for(int i = 1; i <= m; i ++)  f[i] = INF;
            for(int i = 1; i <= n; i ++)
                for(int j = w[i]; j <= m; j ++)
                    f[j] = min(f[j], f[j - w[i]] + 1);
            flag = true;
            for(int i = 1; i <= m; i ++)
            {
                int x = i, res = 0;
                for(int j = n; j && x; j --)
                {
                    res += x / w[j];
                    x %= w[j];
                }
                if(res > f[i])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)  printf("Case #%d: OK\n", t ++);
            else  printf("Case #%d: Cannot use greedy algorithm\n", t ++);
        }
    }
    return 0;
}

J Calculus9

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct crystal{double x,y;}p[100005],q[100005];
bool cmpx(struct crystal a,struct crystal b){return a.x<b.x;} 
bool cmpy(struct crystal a,struct crystal b){return a.y<b.y;} 
double dis(struct crystal a,struct crystal b){double x=a.x-b.x,y=a.y-b.y;return sqrt(x*x+y*y);}
double getMin(double a,double b){return a<b?a:b;}
double ans=-1;
void closest(int l,int r)
{
    if(r-l==1)
    {
        if(dis(p[l],p[r])<ans||ans<0)ans=dis(p[l],p[r]);
        return ;
    }
    else if(r-l==2)
    {
        double temp=getMin(getMin(dis(p[l],p[l+1]),dis(p[l],p[l+2])),dis(p[l+1],p[l+2]));
        if(temp<ans||ans<0)ans=temp;
        return ;
    }
    int mid=(r+l)/2,c=0;
    closest(l,mid);
    closest(mid+1,r);
    for(int i=mid;i>=l;i--)
    {
        if(p[mid].x-p[i].x<ans)
        {
            q[c].x=p[i].x;
            q[c].y=p[i].y;
            c++;
        }
        else break;
    }
    for(int i=mid+1;i<=r;i++)
    {
        if(p[i].x-p[mid].x<ans)
        {
            q[c].x=p[i].x;
            q[c].y=p[i].y;
            c++;
        }
        else break;
    }
    sort(q,q+c,cmpy);
    for(int i=0;i<c;i++)
    {
        for(int j=i+1;j<c&&q[j].y-q[i].y<ans;j++)
        {
            if(q[j].y-q[i].y>ans)break;
            else if(dis(q[i],q[j])<ans||ans<0)ans=dis(q[i],q[j]);
        }
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        ans=-1;
        for(int i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
        sort(p,p+n,cmpx);
        closest(0,n-1);
        printf("%.8lf\n",ans);
    }
}

K Calculus9

#include<stdio.h>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
long long pre[100005]={1},a[100005],ans=0;
int n,k;
bool cmp(long long a,long long b)
{
    return a<b;
}
/*快速幂板子*/
long long qmul(long long a,long long b)
{
    long long res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
/*组合数板子*/
long long C(long long a,long long b)
{
    if(a<=0||b<=0||a<b)return 0;
    long long k1=pre[a]%mod;
    long long k2=qmul(pre[b]%mod,mod-2)%mod;
    long long k3=qmul(pre[a-b]%mod,mod-2)%mod;
    return ((k1*k2)%mod*k3)%mod;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    sort(a,a+n,cmp);
    pre[0]=1;
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]*i%mod;
    for(int i=0;i<n;i++)
    {
        if(n-i-1>=k-1)ans+=(mod-C(n-i-1,k-1))*a[i]%mod;
        if(i>=k-1)ans+=C(i,k-1)%mod*a[i]%mod;
        ans%=mod;
    }
    while(ans<0)ans+=mod;
    printf("%lld\n",ans%mod);
}

L _Wallace_

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e6+7;
int Array[N];
namespace SGTree{
    int L[N<<2],R[N<<2];
    vector<int> dat[N<<2];
    void build(int l,int r,int rt=1)
    {
        L[rt]=l,R[rt]=r;
        if(l==r)
        {
            dat[rt].resize(1);
            dat[rt][0]=Array[l];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);
        dat[rt].resize(r-l+1);
        merge(dat[rt<<1].begin(),dat[rt<<1].end(),
              dat[rt<<1|1].begin(),dat[rt<<1|1].end(),
              dat[rt].begin());
    }
    int count(int l,int r,int x,int y,int rt=1)//count elements which is in [x,y]
    {
        if(l<=L[rt]&&R[rt]<=r)
            return upper_bound(dat[rt].begin(),dat[rt].end(),y)
                  -lower_bound(dat[rt].begin(),dat[rt].end(),x);
        int mid=(L[rt]+R[rt])>>1,ret=0;
        if(l<=mid) ret+=count(l,r,x,y,rt<<1);
        if(r>mid) ret+=count(l,r,x,y,rt<<1|1);
        return ret;
    }
}
int n,m;
signed main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        scanf("%d",Array+i);
    SGTree::build(1,n);
    scanf("%d",&m);
    int i,j,k,a,b;
    while(m--)
    {
        scanf("%d%d%d",&i,&j,&k);
        a=min(Array[i],Array[j])-k;
        b=max(Array[i],Array[j])+k;
        printf("%d\n",(j-i+1)-SGTree::count(i,j,a,b));
    }
    return 0;
}