C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Ural1095. Nikifor 3 解题报告

Posted on 2012-03-01 13:50 C小加 阅读(238) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

题目保证至少有一个1234。说明这四个数是一个突破点。由此可以联想到以1234四个数字结尾的数保证能被7整除。这样不论前边的数怎样排列,后边四个数总有一种组合能够保证整体可以被7整除。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int z[7]={4123,1324,1234,2341,1243,3421,3142};
char s[23];
int ns[23];
int num0_9[10];
int atoi(char s)
{
    return s-'0';
}
int fun(int x,int num)//把前边的数排列成新数
{
    for(int i=0;i<num0_9[num];i++)
    {
        ns[x+i]=num;
    }
    return x+num0_9[num];
}
int fun2(int x)//求前边的数除以7的余数
{
    int yu=0;
    for(int i=0;i<x;i++)
    {
        yu=(yu*10+ns[i])%7;
    }
    return yu;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(num0_9,0,sizeof(num0_9));
        scanf("%s",s);
        int slen=strlen(s);
        //统计每个数的个数
        for(int i=0;i<slen;i++)
        {
          int num=atoi(s[i]);
          num0_9[num]++;
        }
        //减去1、2、3、4
        for(int i=1;i<=4;i++)
        {
            num0_9[i]--;
        }
        //求前边组成的新数
        int x=0;
        for(int i=1;i<=9;i++)
        {
            x=fun(x,i);
        }
        int yu=fun2(x);//求新数除以7的余数
        int i;
        //找到一种组合可以与前边的数组合起来被7整除
        for(i=0;i<7;i++)
        {
            if((yu*10000+z[i])%7==0)
            {
                break;
            }
        }
        //输出,后边可以补上0
        for(int j=0;j<x;j++)
        printf("%d",ns[j]);
        printf("%d",z[i]);
        for(int j=0;j<num0_9[0];j++)
        printf("0");
        printf("\n");

    }

    return 0;
}

 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理