专栏首页算法修养POJ-2356 Find a multiple(DFS,抽屉原理)

POJ-2356 Find a multiple(DFS,抽屉原理)

Find a multiple Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7133 Accepted: 3122 Special Judge Description

The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k). Input

The first line of the input contains the single number N. Each of next N lines contains one number from the given set. Output

In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order.

If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them. Sample Input

5 1 2 3 4 1 Sample Output

2 2 3

dfs:

#include <iostream>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;
int a[10005];
int vis[10005];
int n;
int m;
int dfs(int x,int sum)
{
    if(sum%n==0&&sum>=n)
    {
        cout<<m<<endl;
        return 1;
    }
    for(int i=x+1;i<=n;i++)
    {
        m++;
        if(dfs(i,sum+a[i]))
        {
                cout<<a[i]<<endl;
                return 1;
        }
        m--;
    }
    return 0;

}
int main()
{

    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        m=0;
        if(!dfs(0,0))
            printf("0\n");

    }
     return 0;
}

抽屉原理改天补上

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 甲级 1003Emergency(Dijkstra最短路)

    1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序...

    ShenduCC
  • CodeForces 157A Game Outcome

    A. Game Outcome time limit per test 2 seconds memory limit per test 256 me...

    ShenduCC
  • ZOJ 3713 In 7-bit

    Very often, especially in programming contests, we treat a sequence of non-white...

    ShenduCC
  • 组合数学-抽屉原理

    抽屉原理又称鸽巢原理:把 n+1个物品放进 n个盒子里,那么至少有一个盒子包含两个及以上的物品。

    唔仄lo咚锵
  • poj-1007-DNA Sorting

    One measure of ``unsortedness'' in a sequence is the number of pairs of entries ...

    瑾诺学长
  • 扩增子图表解读1箱线图:Alpha多样性,老板再也不操心的我文献阅读了

    作者: 刘永鑫 日期:2017-6-17 阅读时长:10 min 宏基因组学 宏基因组学目前的主要研究方法包括:16S/ITS/18S扩增子、宏基因组、宏转录...

    生信宝典
  • 3.1.2 使用绘图API绘制Contour的思路

    A week or so back I wrote about a package I ported/modified to create the Delaun...

    周星星9527
  • 【Codeforces】1213C - Book Reading

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 生物信息学算法之 Python 实现|Rosalind 刷题笔记:007 兔子问题和递推

    递推关系是一种用来定义序列的方法,可以通过前面的项,推导出后面的项。如斐波那契兔子问题,某月的兔子数,等于上一个月的兔子数,加上新生的兔子数;一个关键的现象是,...

    简说基因
  • ZOJ 3713 In 7-bit

    Very often, especially in programming contests, we treat a sequence of non-white...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券