Description:
P種類の製品があり、製品には成分表が付いている。
成分表には少しでも含まれる成分は必ず記載されているが、何%含まれているかが必ず表示されているわけではない。
しかし、成分表は含有率の多いほうから順番に書かれていることが判っている。
この情報からある成分を最も多く/少なく含んでいる製品でありうる物を見つけて欲しい。
この問題で各製品に含まれる成分は、必ず1%単位であるとする。
製品の数 P : (1 <= P <= 10)
成分表に含まれる成分の数 n : (1 <= n <= 100)
成分表で表示されるパーセンテージ p : (0 <= p <= 100)
クエリの数Q : (1 <= Q <= 100)
各成分の名前は30文字まで。
Answer:
クエリで聞かれている成分の含有率の取りうる上限と下限を各製品について求めてやればよい。
上限/下限を求めるには、自分以外の成分を出来るだけ低く/高く見積もり、一次方程式を解いてやればよい。
含有量不明の成分は、必ず1%以上含まれているが、含有量が表示されている成分は0%もありえる事に注意。
Source: