2016年2月2日 星期二

[IOI Camp Judge 60]背包 EX(駭客題)(題目備份)

IOI Camp Judge是暫時性的,因此在此作題目備份
題解在這裡

背包 EX(駭客題)

Time Limit: 1s

Original Description

天秤女孩阿斯特莉亞收到了一個精美的天平作為她的生日禮物,開心的她馬上將一個重量 m 克的砝碼放入其中一側,天平便漸漸傾斜了。
阿斯特莉亞看著傾斜的天平和手邊 n 個重量分別為 a1,a2,,an 克的砝碼,忍不住想:「有沒有辦法從這些砝碼中挑一些放到另外一側,使得天平回到平衡的狀態呢?有辦法的話又有幾種不同的挑法呢?」

Original Input Format

第一行有一個正整數 T,代表總共有幾筆測試資料。每筆測試資料第一行為兩個整數 n,m,第二行為 n 個整數 a1,a2,,an

Original Output Format

對於每筆測試資料,請輸出一行一個整數,代表有幾種挑法可以使得天平回到平衡的狀態。由於答案可能很大,請輸出該數除以 1000000007 的餘數。

Sample Input

2
3 3
1 2 3
4 13
1 2 4 8

Sample Output

2
1

Hacked Program


#include <cstdio>
 
const int N = 42;
const int M = 777;
const int MOD = 1e9 + 7;
 
int t, n, m, a[N], dp[M + 1];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", a + i);
        for (int i = 0; i <= m; i++) dp[i] = 0;
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= a[i]; j--) {
                dp[j] += dp[j - a[i]];
                if (dp[j] > MOD) dp[j] -= MOD;
            }
        }
        printf("%d\n", dp[m]);
    }
    return 0;
}


Judge Method

雖然原題的 T 的範圍限制高達 100,但請輸出一個 T=1 的測試資料,使得上述的程式碼會輸出錯的答案。

Sample Program

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。



#include <cstdio>
int main() {
    puts("1");
    puts("3 3");
    puts("1 2 3");
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原