A22504.Who Brings the Cookies? G

省选/NOI-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

农夫约翰的 N(1N1000)N(1 \le N \le 1000) 只奶牛(编号为 11NN)决定成立 M(1M100)M(1 \le M \le 100) 个学习小组。在学习小组 GiG_i 中有 SiS_i 只牛,分别为牛Gi1,Gi2,G_{i1},G_{i2},\cdots,一头牛可能会参加多个小组。

对于每个学习小组,有一只牛必须在每次聚会的时候带饼乾饮料请大家吃(衰~)。因为买这些零食会消耗牛们那为数不多的零花钱,还会花费牛们宝贵的时间,所以牛们希望尽可能公平地分摊带零食的责任。 牛们决定。如果一只牛参加了 KK 个学习小组,KK 个学习小组的大小分别为 c1,c2,cKc_1,c_2, \cdots c_K,那麽她最多负责为 1c1+1c2++1cK\lceil \frac{1}{c_1} + \frac {1}{c_2} + \cdots + \frac{1}{c_K} \rceil 个学习小组的聚会带零食。其中 \lceil \rceil为上取整函数。 请计算出一个方案,决定每个学习小组的聚会由哪一头牛负责带零食。如果没有一种方案可行,输出 -1

输入格式

  • Line 1: Two space-separated integers: N and M

  • Lines 2..M+1: Line i+1 contains many space-separated integers: S_i, G_i1, G_i2, ...

输出格式

  • Lines 1..M: If a mapping is possible, line i contains the number of the cow who brings cookies to study group i. Otherwise, line 1 contains just the integer -1.

输入输出样例

  • 输入#1

    5 6 
    3 2 4 5 
    2 1 3 
    3 1 2 3 
    1 1 
    2 2 5 
    3 2 3 4 
    

    输出#1

    5 
    1 
    3 
    1 
    2 
    4 
    

说明/提示

Cow1 can bring cookies to at most 2 meetings, cow2 can bring 2, cow3 can bring 2, cow4 can bring 1, and cow5 can bring 1.

首页