Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem E
Eat or not to Eat?
Input: Standard Input
Output: Standard Output

A young farmer has N cows, but they produced really really a very very small amount of milk. John cannot live on the milk they made, so he's planning to eat some of the 'worst' cows to get rid of hunger. Each day, John chooses the cow that produces the LEAST amount of milk on that day and eat them. If there are more than one cow with minimal milk, John will be puzzled and will not eat any of them (Yeah! That's GREAT!!).

The i-th cow has a cycle of production Ti. That means, if it produces L unit milk on one day, it will also produce L unit after Ti days -- If it will not be eaten during these day :-). Though John is not a clever man, he doubts whether the cows will be eventually eaten up, so he asks for your help. Don't forget that he will offer you some nice beef for that!

Input

The first line of the input contains a single integer T, indicating the number of test cases. (1<=T<=50) Each test case begins with an integer N(1<=N<=1000), the number of cows. In the following N lines, each line contains an integer T_i(1<=T_i<=10), indicating the cycle of the i-th cow, then T_i integers M_j(0<=M_j<=250) follow, indicating the amount of milk it can produce on the j-th day.

Output

For each test case in the input, print a single line containing two integers C, D, indicating the number of cows that will NOT be eaten, and the number of days passed when the last cow is eaten. If no cow is eaten, the second number should be 0.

Sample Input

1
4
4 7 1 2 9
1 2
2 7 1
1 2

Sample Output

2 6
__________________________________________________________________________________________
Rujia Liu

題目描述：

每頭牛的生產牛奶的數量按照週期性生產，每天會將生產最少的牛殺掉，如果有相同少的牛，則一頭也不殺。

問最後剩下幾頭牛，而最後一頭是第幾天殺的。

題目解法：

由於週期最多 10 天，最小公倍數為 2520 天。

每次窮舉 2520 天，查找每一天是否有牛可以殺，直到某個循環任何一頭牛都殺不成。


#include <stdio.h>
// For the values: 10, 9, 8, 7, 6, 5, 4, 3, 2
// The LCM is: 2520
int main() {
    int testcase;
    int n, i, j, k;
    int T[1005][15], Tn[1005];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d", &Tn[i]);
            for(j = 0; j < Tn[i]; j++)
                scanf("%d", &T[i][j]);
        }
        int killed[1005] = {};
        int LCM = 2520, days = 0, lastDay = 0;
        int hasKilled = 1, sum;
        while(hasKilled) {
            hasKilled = 0;
            for(i = 0; i < LCM; i++) {
                days++;
                int mn = 0xfffffff, mncnt = 0, mnidx;
                for(j = 0; j < n; j++) {
                    if(killed[j])    continue;
                    int v = T[j][i%Tn[j]];
                    if(v < mn)
                        mn = v, mncnt = 0, mnidx = j;
                    if(v == mn)
                        mncnt++;
                }
                if(mncnt == 1) {
                    killed[mnidx] = 1;
                    lastDay = days;
                    hasKilled = 1;
                }
            }
        }
        for(i = 0, sum = 0; i < n; i++)
            sum += killed[i] == 0;
        printf("%d %d\n", sum, lastDay);
    }
    return 0;
}