1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def max_stamps_to_give(n, stamps):
    from collections import Counter
    
    # Zliczamy wystąpienia każdego numeru miasta
    city_counts = Counter(stamps)
    
    # Tworzymy listę par (liczba_znaczków, liczba_miast)
    counts = sorted(city_counts.values(), reverse=True)
    
    # Obliczamy maksymalną liczbę znaczków do rozdania dla k chętnych
    max_stamps = [0] * n
    for k in range(1, n + 1):
        total_stamps = 0
        for count in counts:
            total_stamps += min(count, k)
        max_stamps[k-1] = total_stamps
    
    # Znajdujemy punkty, w których wartość się zmienia i wypełniamy luki
    results = []
    last_value = max_stamps[0]
    for i in range(n):
        if max_stamps[i] < last_value:
            last_value = max_stamps[i]
        results.append(last_value)
        if last_value == 0:  # Jeśli osiągniemy 0, nie ma sensu kontynuować
            results.extend([0] * (n - i - 1))
            break
    
    return results

# Przykładowe dane wejściowe
n = 9
stamps = [1, 1, 777, 42, 777, 1, 42, 1, 777]

# Wywołanie funkcji
results = max_stamps_to_give(n, stamps)

# Wyświetlenie wyniku
print(" ".join(map(str, results)))