Overview

From the sequence of flower variety numbers listed in the order they were found, for each variety we adopt only the “first occurrence,” and compute the total number of adopted entries and the sum of variety numbers.

Analysis

The key task in this problem is determining “whether a variety number has already been recorded in the encyclopedia.” Even if the same variety appears multiple times, we count only the first occurrence and ignore all subsequent ones.

For example, when \(S = [3, 1, 3, 2, 1]\): - 3 (first appearance) → adopted - 1 (first appearance) → adopted - 3 (second time) → not adopted - 2 (first appearance) → adopted - 1 (second time) → not adopted

So the number of adopted entries is \(3\), and the sum is \(3+1+2=6\).

If we naively perform a linear search each time to check “whether the variety is already in the list of adopted varieties,” the worst case is \(O(N^2)\), which is too slow for \(N \le 2 \times 10^5\). Instead, we can leverage the fact that “variety numbers are small, ranging from \(1\) to \(100\),” and manage occurrence tracking with an array, allowing \(O(1)\) lookup for each element.

Algorithm

1. Prepare a boolean array seen of length \(101\), initialized to all False (seen[x] represents “whether variety \(x\) has already been adopted”).
2. Initialize cnt = 0 (number of adopted entries) and total = 0 (sum).
3. Iterate through the input sequence from the beginning, letting \(x\) be the variety number:
   • If seen[x] is False, this is the first appearance, so adopt it: set seen[x] = True, cnt += 1, total += x.
   • Otherwise, it has already been adopted, so do nothing.
4. Finally, output cnt and total.

Complexity

• Time complexity: \(O(N)\) (each element is processed once with \(O(1)\) lookup)
• Space complexity: \(O(1)\) (seen is a fixed-size array of size \(101\))

Implementation Notes

• Since variety numbers range from \(1\) to \(100\), managing them with a fixed-length array like seen = [False] * 101 is simple and fast (the index directly corresponds to the variety number).

• Since the input can be large, in Python using sys.stdin.buffer.read() to read all input at once provides stable and fast performance.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    s = data[1:1+n]

    seen = [False] * 101
    cnt = 0
    total = 0
    for x in s:
        if not seen[x]:
            seen[x] = True
            cnt += 1
            total += x

    print(cnt, total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.