Overview

Given \(N\) breed numbers, remove duplicates and find “how many distinct breeds there are” and “the sum of those breed numbers.”

Analysis

The key point of this problem is the rule: “When the same breed number appears multiple times, ignore all occurrences after the first.” In other words, this is the operation of removing duplicates from the given set of numbers and extracting only the unique values.

For example, if the input is 1, 2, 1, 3, 2: - 1st value 1: First occurrence, so include it - 2nd value 2: First occurrence, so include it - 3rd value 1: Already seen, so exclude it - 4th value 3: First occurrence, so include it - 5th value 2: Already seen, so exclude it

Ultimately, the encyclopedia will contain {1, 2, 3}, which is 3 entries, and the sum is \(1 + 2 + 3 = 6\).

Looking at the constraints, the number of flowers \(N\) is at most \(2 \times 10^5\), which is relatively large, but the breed numbers \(S_i\) fall within the very narrow range of \(1\) to \(100\). Therefore, as long as we manage duplicates efficiently, we can easily fit within the time limit.

Algorithm

To manage duplicates, the most efficient approach is to use the “set” data structure, which is a standard feature of programming languages.

1. Prepare an empty set.
2. Examine the given \(N\) breed numbers in order and add them to the set.
   • Since a set does not hold multiple copies of the same value, duplicates are automatically eliminated.
3. After examining all breed numbers, calculate and output:
   • Count: The number of elements in the set
   • Sum: The total sum of the elements in the set

Additionally, since breed numbers are at most 100, you can also solve this by preparing an array (bucket) of length 101 and marking the index of each breed number that appears.

Complexity

• Time complexity: \(O(N)\)
  • Reading \(N\) elements and adding them to a set takes \(O(1)\) on average per operation, so the overall complexity is \(O(N)\).
• Space complexity: \(O(N)\) or \(O(\max(S_i))\)
  • It is \(O(N)\) if storing all input data, or \(O(\max(S_i))\) if only considering the unique breed numbers stored in the set or array. Under the given constraints, both fit comfortably in memory.

Implementation Tips

• Efficient input: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Using sets: Simply writing set(s_values) easily creates a set with duplicates removed from the list.

• Computing the sum: The sum() function can also be applied to a set, making it straightforward to compute the total.

  Source Code

import sys

def main():
    # 入力をすべて読み込み、空白で分割してリスト化する
    # Nが大きくても効率的に処理するために sys.stdin.read を使用
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    # 1つ目の要素は N (花の個数)
    # n = int(input_data[0])
    
    # 2つ目以降の要素は品種番号 S_i
    # set を使用することで重複を除去し、各品種の最初に見つけたものだけを管理する
    s_values = map(int, input_data[1:])
    unique_species = set(s_values)
    
    # 図鑑に載せる花の枚数は、一意な品種番号の個数
    count = len(unique_species)
    
    # 品種番号の合計を計算
    total_sum = sum(unique_species)
    
    # 結果をスペース区切りで出力
    print(f"{count} {total_sum}")

if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3-flash-preview.