SPOJ 1167

https://www.spoj.pl/problems/MINCOUNT/
。。实际上就是正三角和倒三角重叠部分越多越好。。
那么画个图尝试一下。。感觉重叠部分最大是2/3。。
那么就有1/3需要移动。。。写了个暴搜发现是对的(就是枚举位移。。看重合。。)。。
那么就。。。直接上了。。
圆圈有h*(h+1)/2个。。
那么有h*(h+1)/6个要移动。。可惜不能直接算出来。。要溢出的。。
设h=2a+b,h+1=3c+d;
那么h*(h+1)=6ac+3bc+2ad+bd。。
h*(h+1)/6=ac+(3bc+2ad+bd)/6。。。
就可以避免一出了。。
就是不知道如果6换成一个素数的话。。该怎么搞?

#include<iostream>
#include<stdio.h>
using namespace std;
unsigned long long h,ans,a,b,c,d;

void solve()
{
    scanf("%lld", &h);
    a=h/2;b=h%2;h++;c=h/3;d=h%3;
    ans=a*c+(3*b*c+2*a*d+b*d)/6;
    printf("%lld\n", ans);
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
}

4 thoughts on “SPOJ 1167

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>