G - Mixture Drug
Editorial
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 点
問題文
イルカの手元には から までの番号が付いた 種類の薬品があります。
また、薬品の取り扱いについて書かれたリストが手元にあります。
このリストには 個の項目があり、リストの上から 番目の項目には「番号 と 番号 の薬品を混合すると毒が発生する。」と書いてあります。
イルカは、リストに基づいて毒が発生しないように、できる限り多くの種類の薬品を混合したいと考えています。
イルカは最大で何種類の薬品を混合できますか?
制約
- または
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
出力
イルカが混合できる薬品の最大種類数を出力せよ。
入力例 1Copy
Copy
4 1 1 2
出力例 1Copy
Copy
3
番号 と番号 の薬品を混合すると毒が発生するので、全ての薬品を混合することはできません。
一方で、番号 と番号 と番号 の薬品を混合した場合には、毒が発生しません。
したがって、最大 種類の薬品が使えるので、 と出力します。
入力例 2Copy
Copy
1 0
出力例 2Copy
Copy
1
入力例 3Copy
Copy
20 16 1 8 1 16 2 19 3 5 3 10 5 7 5 13 6 9 7 8 7 11 7 14 7 15 8 12 9 12 9 17 15 20
出力例 3Copy
Copy
12