c548: Boook 愛鴿子

2019-08-24

內容

Boook 從國中開始喜歡上了養鴿子，如今已經有了豐富的經驗與技術，今年將代表台灣去日本東京參加『國際鴿子大賽 IOI 』（ International Olympia In doves keeping ）。

比賽方式如下：

一開始參賽者必須將每隻鴿子隨機標記一個數字代表這隻鴿子的分數，比賽開始後由大會隨機決定一個數字 K ，而每位參賽者都要從他擁有的所有鴿子中選出一些鴿子使這些鴿子的分數總和為 K 的倍數，最快的獲勝。

Boook 想要用程式幫助他能快速的決定要選擇哪些編號的鴿子，才能完成比賽條件。

現在 Boook 給你他每隻鴿子的分值，現在請你寫個程式，告訴 Boook 有沒有可能符合比賽需求，如果可以，要選擇哪些鴿子使 Boook 順利完成比賽。

（本題答案可能有多組解，請輸出任意一組）

輸入

第一行共兩個數字 n 跟 k ，分別代表 Boook 的鴿子數量及比賽要求的數字。

(1 <= n <= 100000 , 2 <= k <= n)

接下來一行共 n 個數字 a [ i ] ( 1 <= a [ i ] <= 2147483647 ) ，代表每隻鴿子的分數。

5 3
7 92 47 5 1

輸出

(答案可能有很多，輸出任何一組即可)

第一行一個數字 m ，代表 Boook 共要選幾隻鴿子。

(如果無法贏得比賽，請輸出 0 )

接下來一行共 m 個數字代表要選的鴿子編號。

2
4 5

解題思路

由於只需輸入任一組，所以用 DFS 遍歷全部可能性，找到第一組時將其記錄下來並跳出遞迴輸出即可。

完整程式碼

AC (19ms, 8.7MB)

#include <stdio.h>
#define MAX 100010

int n, k, list[MAX], ans[MAX], aLen;

char dfs(int s, long long sum)
{
    if (!(sum % k) && sum)
        return 1;
    for (int i = s; i <= n; i++)
    {
        if (dfs(i + 1, sum + list[i]))
        {
            ans[aLen++] = i;
            return 1;
        }
    }
    return 0;
}

int main()
{
    while (scanf(" %d %d", &n, &k) == 2)
    {
        aLen = 0;
        for (int i = 1; i <= n; i++)
            scanf(" %d", &list[i]);
        if (dfs(1, 0))
        {
            printf("%d\n", aLen);
            for (int i = 0; i < aLen; i++)
                printf("%d ", ans[i]);
            putchar('\n');
        }
        else
        {
            puts("0");
        }
    }
    return 0;
}