рдкрд╛рдпрдерди рдкреНрд░реЛрдЧреНрд░рд╛рдорд┐рдВрдЧ рдХреМрд╢рд▓ рдХрд╛ рдкрд░реАрдХреНрд╖рдг рдХреИрд╕реЗ рдХрд░реЗрдВ? рдпрд╛рдВрдбреЗрдХреНрд╕ рд╕реЗ рдХрд╛рд░реНрдп


рдмреИрдХреЗрдВрдб рдбреЗрд╡рд▓рдкрдореЗрдВрдЯ рд╕реНрдХреВрд▓ рдореЗрдВ рд╣реИрдХрдереЙрди

2019 рдореЗрдВ, рд╣рдореЗрдВ рд╕реИрдХрдбрд╝реЛрдВ рдбреЗрд╡рд▓рдкрд░реНрд╕ рдХреЗ рд╕рд╛рде рдкрд╛рдпрдерди рдХреЛрдб рд▓рд┐рдЦрдиреЗ рдХреА рдХреНрд╖рдорддрд╛ рдХрд╛ рд╕реНрд╡рдЪрд╛рд▓рд┐рдд рд░реВрдк рд╕реЗ рдкрд░реАрдХреНрд╖рдг рдХрд░рдиреЗ рдХреА рдЖрд╡рд╢реНрдпрдХрддрд╛ рдереАред рдЗрд╕рд▓рд┐рдП рд╣рдордиреЗ рдмреИрдХреЗрдВрдб рдбреЗрд╡рд▓рдкрдореЗрдВрдЯ рд╕реНрдХреВрд▓ рдХреЗ рд▓рд┐рдП рднрд╡рд┐рд╖реНрдп рдХреЗ рдЫрд╛рддреНрд░реЛрдВ рдХрд╛ рдЪрдпрди рдХрд┐рдпрд╛ред рдпрд╣ рдХрд╛рдЧрдЬ рдХреЗ рдПрдХ рдЯреБрдХрдбрд╝реЗ рдкрд░ рдПрдХ рд╕рдорд╕реНрдпрд╛ рдХреЛ рд╣рд▓ рдХрд░рдиреЗ рдХреА рдкреЗрд╢рдХрд╢ рдХреЗ рд╕рдорд╛рди рдирд╣реАрдВ рд╣реИ, рдЬреИрд╕рд╛ рдХрд┐ рдПрдХ рд╕рд╛рдХреНрд╖рд╛рддреНрдХрд╛рд░ рдореЗрдВред рджреВрд╕рд░реА рдУрд░, рд╣рдо рдЕрдкрдиреА рдкреНрд░реЛрдЧреНрд░рд╛рдорд┐рдВрдЧ рдкреНрд░рддрд┐рдпреЛрдЧрд┐рддрд╛рдУрдВ рдХреЗ рд▓рд┐рдП рдкрд╣рд▓реЗ рд╕реЗ рддреИрдпрд╛рд░ рдХрд┐рдП рдЧрдП рдХрд╛рд░реНрдп рд╕реНрдерд┐рддрд┐рдпреЛрдВ рдХрд╛ рднреА рдкреБрди: рдЙрдкрдпреЛрдЧ рдирд╣реАрдВ рдХрд░ рд╕рдХрддреЗ рд╣реИрдВред рддрдереНрдп рдпрд╣ рд╣реИ рдХрд┐ рд╕рд░реНрд╡рд╢реНрд░реЗрд╖реНрда рдХреЛ рдирд┐рд░реНрдзрд╛рд░рд┐рдд рдХрд░рдиреЗ рдХреА рдкреНрд░рддрд┐рдпреЛрдЧрд┐рддрд╛ рдПрдХ рдЪреАрдЬ рд╣реИ, рдФрд░ рд╕реНрдХреВрд▓ рдореЗрдВ рдХрдо рдЕрдиреБрднрд╡ рд╡рд╛рд▓реЗ рд╡рд┐рд╢реЗрд╖рдЬреНрдЮреЛрдВ рдХрд╛ рдЪрдпрди рдПрдХ рдФрд░ рд╣реИред рд╣рдореЗрдВ рдХрд╛рд░реНрдпреЛрдВ рдХреА рдЖрд╡рд╢реНрдпрдХрддрд╛ рдереА, рдЬрд┐рдирдХреЗ рд╕рдорд╛рдзрд╛рди рд╕реЗ рдпрд╣ рд╕реНрдкрд╖реНрдЯ рд╣реЛрдЧрд╛ рдХрд┐ рдХреНрдпрд╛ рдбреЗрд╡рд▓рдкрд░ рдХреЗ рдкрд╛рд╕ рдХреЛрдб рд▓рд┐рдЦрдиреЗ рдХрд╛ рдмреБрдирд┐рдпрд╛рджреА рдХреМрд╢рд▓ рдФрд░ рд╕реНрдореГрддрд┐ рдФрд░ рд╕рдордп рдХрд╛ рд╕рд╣реА рдЙрдкрдпреЛрдЧ рдХрд░рдиреЗ рдХреА рдХреНрд╖рдорддрд╛ рд╣реИ рдпрд╛ рдирд╣реАрдВред рдпреЗ рд╡реЗ рд╕реНрдерд┐рддрд┐рдпрд╛рдВ рд╣реИрдВ, рдЬреЛ рд╣рдордиреЗ рдмрдирд╛рдИ рд╣реИрдВред

рдмрд╛рд░-рдмрд╛рд░ рдордж

рд╕рдорд╛рдзрд╛рди рд▓реЗрдЦрдХ: рдорд┐рдЦрд╛рдЗрд▓ рд╢реБрд╖реНрдкрд╛рдиреЛрд╡ mishushред рдЗрд╕ рд╕рдорд╕реНрдпрд╛ рдХреЛ 50% рдкреНрд░рддрд┐рднрд╛рдЧрд┐рдпреЛрдВ рдиреЗ рд╣рд▓ рдХрд┐рдпрд╛

ред рдПрдХ рдкреНрд░реЛрдЧреНрд░рд╛рдо рд▓рд┐рдЦреЗрдВ рдЬреЛ рд╕рдВрдЦреНрдпрд╛ рдХреЛ рд╕рдмрд╕реЗ рдЕрдзрд┐рдХ рдмрд╛рд░ рд╕рд░рдгреА рдореЗрдВ рдкрд╛рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рд╕рдордп рд╕реАрдорд╛: 2 рдПрд╕, рдореЗрдореЛрд░реА рд╕реАрдорд╛: 256 рдПрдордмреАред

рдЗрдирдкреБрдЯ рдкреНрд░рд╛рд░реВрдк рдЗрдирдкреБрдЯ
рдХреА рдкрд╣рд▓реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдирдВрдмрд░ n (1 тЙд n) 300,000) рд╣реЛрддрд╛ рд╣реИред
рджреВрд╕рд░реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдПрди рдкреВрд░реНрдгрд╛рдВрдХ рдПрдХ i (0 i i i 1 1 000 000 000) рд╣реИред

рдЖрдЙрдЯрдкреБрдЯ рд╕реНрд╡рд░реВрдк
рдХреЗрд╡рд▓ рд╕рдВрдЦреНрдпрд╛ x рдХреЛ рдкреНрд░рд┐рдВрдЯ рдХрд░реЗрдВ, рд╕рдмрд╕реЗ рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛ рдЬреЛ рдЕрдХреНрд╕рд░ рд╕рд░рдгреА a рдореЗрдВ рдкрд╛рдИ рдЬрд╛рддреА рд╣реИред

рдлреЗрд╕рд▓рд╛
рдПрдХ рд╕рд░рд▓ рдХрд╛рд░реНрдп рдЬрд┐рд╕реЗ рдПрдХ рдирд┐рдпрдорд┐рдд рд╢рдмреНрджрдХреЛрд╢ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рдХреЗ рдФрд░ рд╕рдВрдЧреНрд░рд╣ рдореЙрдбреНрдпреВрд▓ рд╕реЗ рдХрд╛рдЙрдВрдЯрд░ рд╕рдВрд░рдЪрдирд╛ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рдХреЗ рд╣рд▓ рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред

рд╕рдмрд╕реЗ рдкрд╣рд▓реЗ, рдЖрдк рдЧрдгрдирд╛ рдХрд░ рд╕рдХрддреЗ рд╣реИрдВ рдХрд┐ рдкреНрд░рддреНрдпреЗрдХ рддрддреНрд╡ рдХрд┐рддрдиреА рдмрд╛рд░ рд╣реЛрддрд╛ рд╣реИ, рдлрд┐рд░ рдЙрди рд▓реЛрдЧреЛрдВ рдореЗрдВ рд╕реЗ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рдЪреБрдиреЗрдВ рдЬреЛ рд╕рдмрд╕реЗ рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛ рдореЗрдВ рд╣реЛрддреЗ рд╣реИрдВред рд╕рдорд╛рдзрд╛рди рдХреЗ рд▓рд┐рдП O (n) рд╕рдордп рдФрд░ O (n) рдЕрддрд┐рд░рд┐рдХреНрдд рдореЗрдореЛрд░реА рдХреА рдЖрд╡рд╢реНрдпрдХрддрд╛ рд╣реЛрддреА рд╣реИред

from collections import Counter

n = int(input()) 
a = [int(i) for i in input().split()] 

counter = Counter(a)

result = a[0]
max_count = counter[result]
for number, count in counter.items():
    if count > max_count or (count == max_count and number > result):
        result = number
        max_count = count

print(result) 

рдЕрдиреБрдХреНрд░рдо рддрддреНрд╡ рдорд╛рди

рд▓реЗрдЦрдХ: рдорд┐рдЦрд╛рдЗрд▓ рд╢реБрд╖реНрдкрд╛рдиреЛрд╡ рд╕рдорд╕реНрдпрд╛ 20% рдкреНрд░рддрд┐рднрд╛рдЧрд┐рдпреЛрдВ рджреНрд╡рд╛рд░рд╛ рд╣рд▓ рдХреА рдЧрдИ рдереАред

рдЕрдиреБрдХреНрд░рдо рдПрдл 0 , рдПрдл 1 , рдПрдл 2 , ... рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕рдВрдмрдВрдзреЛрдВ рджреНрд╡рд╛рд░рд╛ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ рдПрдл 0 = 0, рдПрдл 1 = 1, рдПрдл 2 = 2, рдПрдл рдХреЗ = рдПрдл рдХреЗ - 1 + рдПрдл рдХреЗ - 3 ред

рдПрдХ рдкреНрд░реЛрдЧреНрд░рд╛рдо рд▓рд┐рдЦреЗрдВ рдЬреЛ рдЗрд╕ рдХреНрд░рдо рдХреЗ n рддрддреНрд╡реЛрдВ рдХреЛ рд╕рдВрдЦреНрдпрд╛ 1 , k 2 , ..., k n рдХреЗ рд╕рд╛рде рдЧрдгрдирд╛ рдХрд░рддрд╛ рд╣реИред рд╕рдордп рд╕реАрдорд╛: 1 рдПрд╕, рдореЗрдореЛрд░реА рд╕реАрдорд╛: 10 рдПрдордмреАред

рдЗрдирдкреБрдЯ рдкреНрд░рд╛рд░реВрдк рдЗрдирдкреБрдЯ
рдХреА рдкрд╣рд▓реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдкреВрд░реНрдгрд╛рдВрдХ n (1 тЙд n first 1000) рд╣реЛрддрд╛ рд╣реИред
рджреВрд╕рд░реА рдкрдВрдХреНрддрд┐ рдореЗрдВ n рдЧреИрд░-рдирдХрд╛рд░рд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рд╣реИрдВ (0 non k)i ) 16000), рд░рд┐рдХреНрдд рд╕реНрдерд╛рди рджреНрд╡рд╛рд░рд╛ рдЕрд▓рдЧ рдХрд┐рдпрд╛ рдЧрдпрд╛ред

рдЖрдЙрдЯрдкреБрдЯ рд╕реНрд╡рд░реВрдк
рдЖрдЙрдЯрдкреБрдЯ рд╕реНрдкреЗрд╕-рдЕрд▓рдЧ рдорд╛рди f k 1 , f k 2 , ..., f k n ред

рдлреЗрд╕рд▓рд╛
, . .

, fk f0, f1, ..., fkтАУ1. fk, k = max(k1, k2, ..., kn). , fkтАУ1 fkтАУ3, , , .

O(max(k, n)) O(n) .

n = int(input())
indices = [int(i) for i in input().split()]
results = {i: i if i < 3 else None for i in indices}
k = max(indices)
a, b, c = 0, 1, 2
for i in range(3, k + 1):
    a, b, c = b, c, a + c
    if i in results:
        results[i] = c
print(" ".join(str(results[i]) for i in indices)) 

JOIN рд▓рд╛рдЧреВ рдХрд░реЗрдВ

рджреНрд╡рд╛рд░рд╛ рдкреЛрд╕реНрдЯ: рджрд┐рдорд┐рддреНрд░реА Terrov terrmitред рдХрд╛рд░реНрдп 6% рдкреНрд░рддрд┐рднрд╛рдЧрд┐рдпреЛрдВ рджреНрд╡рд╛рд░рд╛ рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдерд╛ред

рджреЛ рддрд╛рд▓рд┐рдХрд╛рдПрдБ T1 рдФрд░ T2 рджреА рдЧрдИ рд╣реИрдВред рдкреНрд░рддреНрдпреЗрдХ рддрд╛рд▓рд┐рдХрд╛ рдХреЛ рджреЛ рд╕рдВрдЦреНрдпрд╛рддреНрдордХ рдХреНрд╖реЗрддреНрд░реЛрдВ рджреНрд╡рд╛рд░рд╛ рджрд░реНрд╢рд╛рдпрд╛ рдЧрдпрд╛ рд╣реИред рддрд╛рд▓рд┐рдХрд╛ T1 рдореЗрдВ a рдФрд░ b рдлрд╝реАрд▓реНрдб рд╢рд╛рдорд┐рд▓ рд╣реИрдВред рддрд╛рд▓рд┐рдХрд╛ T2 рдореЗрдВ рдлрд╝реАрд▓реНрдб a рдФрд░ c рд╣реИрдВред

рдлрд╝реАрд▓реНрдб рдП рдФрд░ рдлрд╝реЙрд░реНрдо рдЯреЗрдмрд▓ рдЯреА 3 рдореЗрдВ рджреЛ рддрд╛рд▓рд┐рдХрд╛рдУрдВ рдХреЗ рдПрд╕рдХреНрдпреВрдПрд▓ рдЬреЙрдЗрди рдХреЗ рд╕рд░рд▓реАрдХреГрдд рдмрджрд▓рд╛рд╡ рдХреЛ рд▓рд╛рдЧреВ рдХрд░рдирд╛ рдЖрд╡рд╢реНрдпрдХ рд╣реИред

рддрд╛рд▓рд┐рдХрд╛ рдореЗрдВ рдлрд╝реАрд▓реНрдб рдХреЗ рдорд╛рдиреЛрдВ рдХреЛ рдбреБрдкреНрд▓рд┐рдХреЗрдЯ рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИ, рд▓реЗрдХрд┐рди рдкреНрд░рддреНрдпреЗрдХ рдлрд╝реАрд▓реНрдб рдХреЗ рдбреБрдкреНрд▓рд┐рдХреЗрдЯ рдХреА рд╕рдВрдЦреНрдпрд╛ 5. рд╕рдордп рд╕реАрдорд╛ рд╕реЗ рдЕрдзрд┐рдХ рдирд╣реАрдВ рд╣реИ: 1 рдПрд╕, рдореЗрдореЛрд░реА рд╕реАрдорд╛: 64 рдПрдордмреАред

рдЗрдирдкреБрдЯ рдкреНрд░рд╛рд░реВрдк
рдЗрдирдкреБрдЯ рдХреА рдкрд╣рд▓реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдкреВрд░реНрдгрд╛рдВрдХ n1 (1 тЙд n1) 15000) рд╣реЛрддрд╛ рд╣реИ тАФтАУ рддрд╛рд▓рд┐рдХрд╛ 1 рдореЗрдВ рдкрдВрдХреНрддрд┐рдпреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ред рдЕрдЧрд▓рд╛, n1 рд▓рд╛рдЗрдиреЛрдВ рдореЗрдВ, рджреЛ рдкреВрд░реНрдгрд╛рдВрдХ рд░рд┐рдХреНрдд рд╕реНрдерд╛рди рджреНрд╡рд╛рд░рд╛ рдЕрд▓рдЧ-рдЕрд▓рдЧ рд▓рд┐рдЦреЗ рдЧрдП рд╣реИрдВ - рддрд╛рд▓рд┐рдХрд╛ T1 рдХреЗ рдлрд╝реАрд▓реНрдб ai рдФрд░ bi (1 тЙд ai, bi i 1000) рдХреЗ рдорд╛рдиред рдЕрдЧрд▓реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдкреВрд░реНрдгрд╛рдВрдХ n2 (1 тЙд n2) 10000) тАУтАУ рддрд╛рд▓рд┐рдХрд╛ T2 рдореЗрдВ рдкрдВрдХреНрддрд┐рдпреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ред рдЕрдЧрд▓рд╛, n2 рд▓рд╛рдЗрдиреЛрдВ рдореЗрдВ, рджреЛ рдкреВрд░реНрдгрд╛рдВрдХ рдПрдХ рд╕реНрдкреЗрд╕ рдХреЗ рд╕рд╛рде рд▓рд┐рдЦреЗ рдЧрдП рд╣реИрдВ - рдЯреЗрдмрд▓ рдЯреА 2 рдХреЗ рдлрд╝реАрд▓реНрдб aj рдФрд░ cj (1 j aj, cj) 1000) рдХреЗ рдорд╛рдиред рдЕрдВрддрд┐рдо рдкрдВрдХреНрддрд┐ рдСрдкрд░реЗрд╢рди рдХрд╛ рдирд╛рдо рд╣реИ (INNER, LEFT, RIGHT, FULL)ред

рдЖрдЙрдЯрдкреБрдЯ рд╕реНрд╡рд░реВрдк
рдкрд╣рд▓реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рд╕рдВрдЦреНрдпрд╛ N3 - рддрд╛рд▓рд┐рдХрд╛ T3 рдореЗрдВ рдкрдВрдХреНрддрд┐рдпреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рдкреНрд░рд┐рдВрдЯ рдХрд░реЗрдВред рдЕрдЧрд▓реА n3 рд▓рд╛рдЗрдиреЛрдВ рдореЗрдВ рд╕реНрдкреЗрд╕ рдорд╛рди ak, bk рдФрд░ ck рдХреЛ рдЯреЗрдмрд▓ T3 рдХреЗ рд╕реНрдкреЗрд╕ рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ рдкреНрд░рд┐рдВрдЯ рдХрд░реЗрдВред рдпрджрд┐ рддрд╛рд▓рд┐рдХрд╛рдУрдВ рдореЗрдВ рд╢рд╛рдорд┐рд▓ рд╣реЛрдиреЗ рдХреЗ рдкрд░рд┐рдгрд╛рдорд╕реНрд╡рд░реВрдк рдХрд┐рд╕реА рдлрд╝реАрд▓реНрдб рдХрд╛ рдорд╛рди рдЧрд╛рдпрдм рд╣реИ, рддреЛ рдЗрд╕ рдлрд╝реАрд▓реНрдб рдХреЗ рдмрдЬрд╛рдп NULL рдХреЛ рдкреНрд░рд┐рдВрдЯ рдХрд░реЗрдВред рддрд╛рд▓рд┐рдХрд╛ T3 рдореЗрдВ рдкрдВрдХреНрддрд┐рдпреЛрдВ рдХрд╛ рдЖрдЙрдЯрдкреБрдЯ рдСрд░реНрдбрд░ рдорд╣рддреНрд╡рдкреВрд░реНрдг рдирд╣реАрдВ рд╣реИред

рдлреЗрд╕рд▓рд╛
, a . тАФ :

for a1, b in t1:
    for a2, c in t2:
        if a1 == a2:
            t3.append((a1, b, c))

. a. -:

for row in t1:
    t1_map[row[0]] = row

LEFT. , , . тАФ (a, b, c), тАФ (a, b, NULL).

for a, b in t1_map.items():
     if a in t2_map:
         t3.append((a, b, t2[a]))
     else:
         t3.append((a, b, 'NULL'))

RIGHT .

FULL , , :

for a, c in t2_map.items():
    if a not in t1_map:
        t3.append((a, 'NULL', c))

a , hash-map , a. Python itertools.product.

, a , тАФ N x N. , . , .

рдЕрд╢рдХреНрдд рдорд╛рди рд╣рдЯрд╛рдирд╛

рд▓реЗрдЦрдХ: рдорд┐рдЦрд╛рдЗрд▓ рд╢реБрд╖реНрдкрд╛рдиреЛрд╡ 7% рдкреНрд░рддрд┐рднрд╛рдЧрд┐рдпреЛрдВ рдиреЗ рд╕рдорд╕реНрдпрд╛ рдХреЛ рд╣рд▓ рдХрд┐рдпрд╛ред

рдПрдХ рдкреНрд░реЛрдЧреНрд░рд╛рдо рд▓рд┐рдЦреЗрдВ рдЬреЛ JSON рд╕рдВрд░рдЪрдирд╛ рд╕реЗ рдорд╛рди рд╣рдЯрд╛рддрд╛ рд╣реИ рдЬреЛ рдЦрд╛рд▓реА рд╢рдмреНрджрдХреЛрд╖ ({}) рдпрд╛ рдЦрд╛рд▓реА рд╕реВрдЪреА ([]) рд╣реИрдВ, рдЬрдм рддрдХ рдХрд┐ рдРрд╕реЗ рдореВрд▓реНрдп рд╣реИрдВред рдпрджрд┐ рд╢рдмреНрджрдХреЛрд╢ рдореЗрдВ рдореВрд▓реНрдп рд╣рдЯрд╛ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рддреЛ рд╕рдВрдмрдВрдзрд┐рдд рдХреБрдВрдЬреА рднреА рд╣рдЯрд╛ рджреА рдЬрд╛рддреА рд╣реИред рд╕рдордп рд╕реАрдорд╛: 0.2 рдПрд╕, рдореЗрдореЛрд░реА рд╕реАрдорд╛: 6 рдПрдордмреАред

рдЗрдирдкреБрдЯ рдкреНрд░рд╛рд░реВрдк
рдПрдХ рдПрдХрд▓ рдЗрдирдкреБрдЯ рд▓рд╛рдЗрди рдореЗрдВ рд▓рдВрдмрд╛рдИ n (1 тЙд n single 1000) рдХреА рдПрдХ рд╕реНрдЯреНрд░рд┐рдВрдЧ рд╣реЛрддреА рд╣реИред рдпрд╣ рдЧрд╛рд░рдВрдЯреА рд╣реИ рдХрд┐ рдпрд╣ рд╕реНрдЯреНрд░рд┐рдВрдЧ рдПрдХ рд╡реИрдз JSON рд╕реНрдЯреНрд░рд┐рдВрдЧ рд╣реИред

рдЖрдЙрдЯрдкреБрдЯ рд╕реНрд╡рд░реВрдк:
рдЖрдЙрдЯрдкреБрдЯ, рдПрдХ рд╕реНрдерд╛рди рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ, рд╣рдЯрд╛рдП рдЧрдП рдЦрд╛рд▓реА рд╢рдмреНрджрдХреЛрд╢реЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рдФрд░ рд╣рдЯрд╛рдП рдЧрдП рдЦрд╛рд▓реА рд╕реВрдЪрд┐рдпреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ред

рдлреЗрд╕рд▓рд╛
. , -, , JSON. json, isinstance, , Python. JSON {}, [], : , ''{}, []'' .

тАФ , .

import json
dict_counter, list_counter = 0, 0
def clean_struct(struct):
    global dict_counter, list_counter
    if isinstance(struct, dict):
        for key, value in struct.copy().items():
            cleaned_struct = clean_struct(value)
            if cleaned_struct is None:
                del struct[key]
            else:
                struct[key] = cleaned_struct
        if len(struct) == 0:
            dict_counter += 1
            return None
    if isinstance(struct, list):
        i = 0
        while i < len(struct):
            cleaned_struct = clean_struct(struct[i])
            if cleaned_struct is None:
                del struct[i]
            else:
                struct[i] = cleaned_struct
                i += 1
        if len(struct) == 0:
            list_counter += 1
            return None
    return struct
struct = json.loads(input())
clean_struct(struct)
print(dict_counter, list_counter) 

рдЙрдЪреНрдЪ рднрд╛рд░

рд╕рдорд╛рдзрд╛рди рд▓реЗрдЦрдХ: рджрд┐рдорд┐рддреНрд░реА рдЯреЗрд░реЛрд╡ред рд╕рдорд╕реНрдпрд╛ рдХреЛ 14% рдкреНрд░рддрд┐рднрд╛рдЧрд┐рдпреЛрдВ рджреНрд╡рд╛рд░рд╛ рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдерд╛ред

рдЖрдкрдХреЛ рдХреБрдЫ рдХрд╛рд▓реНрдкрдирд┐рдХ рд╕реЗрд╡рд╛ рдкрд░ рд╕рддреНрд░реЛрдВ рдХрд╛ рдЗрддрд┐рд╣рд╛рд╕ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдкреНрд░рддреНрдпреЗрдХ рд╕рддреНрд░ рдХреЛ рд╕реБрд╡рд┐рдзрд╛ рдХреЗ рд▓рд┐рдП рд╢реБрд░реВ рдФрд░ рдЕрдВрдд рд╕рдордп рд╕реА рдФрд░ рдлрд╛рдИ рджреНрд╡рд╛рд░рд╛ рд╡рд┐рд╢реЗрд╖рддрд╛ рд╣реИ, рдпреЗ рд╕рднреА рдореВрд▓реНрдп рдЕрд▓рдЧ-рдЕрд▓рдЧ рд╣реИрдВред

рд╕рдордп рдЯреА рдореЗрдВ рдЙрд╕ рдмрд┐рдВрджреБ рдХреЛ рдЦреЛрдЬреЗрдВ рдЬрдм рд╕рддреНрд░реЛрдВ рдХреА рд╕рдмрд╕реЗ рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛ рд╕рдХреНрд░рд┐рдп рдереАред рдпрджрд┐ рдРрд╕реЗ рдХрдИ рдХреНрд╖рдг рд╣реИрдВ, рддреЛ рдЙрдирдореЗрдВ рд╕реЗ рд╕рдмрд╕реЗ рдкрд╣рд▓реЗ рдкреНрд░рд┐рдВрдЯ рдХрд░реЗрдВред рд╕рдордп рд╕реАрдорд╛: 1 рдПрд╕, рдореЗрдореЛрд░реА рд╕реАрдорд╛: 256 рдПрдордмреАред

рдЗрдирдкреБрдЯ рдкреНрд░рд╛рд░реВрдк рдЗрдирдкреБрдЯ
рдХреА рдкрд╣рд▓реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдкреВрд░реНрдгрд╛рдВрдХ n (1 тЙд n first 1000) рд╣реЛрддрд╛ рд╣реИред рдЗрд╕рдХреЗ рдмрд╛рдж, n рд▓рд╛рдЗрдиреЛрдВ рдореЗрдВ рджреЛ рдЕрдВрддрд░рд┐рдХреНрд╖-рдкреГрдердХ рдкреВрд░реНрдгрд╛рдВрдХ si рдФрд░ Fi (0 fi si <fi lines 1,000,000,000) рд╣реИрдВред

рдЖрдЙрдЯрдкреБрдЯ рд╕реНрд╡рд░реВрдк
рд╡рд╛рдВрдЫрд┐рдд рд╕рдордп рдЯреА рдкреНрд░рд┐рдВрдЯ рдХрд░реЗрдВред

рдлреЗрд╕рд▓рд╛
, тАФ , . тАФ O(N x N).

. тАФ . . , , , тАФ , тАФ . тАФ O(N x log N).

n = int(input())
sessions = []
for _ in range(n):
    x, y = map(int, input().split())
    sessions.append((x, y))

events = []
for start, end in sessions:
    events.append((start, 1))
    events.append((end, -1))
events.sort()

max_number = min_time = cur_number = 0
for cur_time, operation in events:
    cur_number = cur_number + operation
    if cur_number > max_number:
        max_number = cur_number
        min_time = cur_time

print(min_time)

рд╢реНрд░реГрдВрдЦрд▓рд╛ рд▓рдВрдмрд╛рдИ рдХреЛрдбрд┐рдВрдЧ

рдирд┐рд░реНрдгрдп рдХреЗ рд▓реЗрдЦрдХ: рдорд┐рдЦрд╛рдЗрд▓ рд╢реБрд╖реНрдкрд╛рдиреЛрд╡ред рд╕рдорд╕реНрдпрд╛ рдХреЛ рдкреНрд░рддрд┐рднрд╛рдЧрд┐рдпреЛрдВ рдХреЗ 33%

рд╢реНрд░реГрдВрдЦрд▓рд╛ рд▓рдВрдмрд╛рдИ рдХреЛрдбрд┐рдВрдЧ (рдЖрд░рдПрд▓рдИ) рджреНрд╡рд╛рд░рд╛ рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдерд╛ - рдПрдХ рдбреЗрдЯрд╛ рд╕рдВрдкреАрдбрд╝рди рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо рдЬреЛ рдПрдХ рд╡рд░реНрдг рдФрд░ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐рдпреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рдХреЗ рд╕рд╛рде рджреЛрд╣рд░рд╛рдпрд╛ рд╡рд░реНрдгреЛрдВ рдХреЛ рдмрджрд▓рддрд╛ рд╣реИред рдПрдХ рд╢реНрд░реГрдВрдЦрд▓рд╛ рдПрдХ рдЕрдиреБрдХреНрд░рдо рд╣реИ рдЬрд┐рд╕рдореЗрдВ рдХрдИ рд╕рдорд╛рди рдЕрдХреНрд╖рд░ (рдПрдХ рд╕реЗ рдЕрдзрд┐рдХ) рд╣реЛрддреЗ рд╣реИрдВред рдЬрдм рдПрдиреНрдХреЛрдбрд┐рдВрдЧ рд╣реЛрддреА рд╣реИ, рддреЛ рд╢реНрд░реГрдВрдЦрд▓рд╛ рдмрдирд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рдорд╛рди рд╡рд░реНрдгреЛрдВ рдХреА рдПрдХ рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреЛ рдПрдХ рд╕реНрдЯреНрд░рд┐рдВрдЧ рджреНрд╡рд╛рд░рд╛ рдкреНрд░рддрд┐рд╕реНрдерд╛рдкрд┐рдд рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ рдЬрд┐рд╕рдореЗрдВ рджреЛрд╣рд░рд╛рдП рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╡рд░реНрдг рдФрд░ рдЙрд╕рдХреЗ рджреЛрд╣рд░рд╛рд╡ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╣реЛрддреА рд╣реИред

рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, рд╕реНрдЯреНрд░рд┐рдВрдЧ AAAABBB рд╕реНрдЯреНрд░рд┐рдВрдЧ A4B3, рдФрд░ рд╕реНрдЯреНрд░рд┐рдВрдЧ AAAAAAAAAAAAAAAABAAAAA рдХреЛ A15BA5 рд╕реЗ рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХрд┐рдпрд╛ рдЬрд╛рдПрдЧрд╛ред

рдЖрдкрдХреЛ рдПрдХ рд╕рдВрдХреБрдЪрд┐рдд рд╕реНрдЯреНрд░рд┐рдВрдЧ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдореВрд▓ рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреА рд▓рдВрдмрд╛рдИ рдХрд╛ рдкрддрд╛ рд▓рдЧрд╛рдПрдВред рд╕реНрд░реЛрдд рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреА рд▓рдВрдмрд╛рдИ 1000 рд╡рд░реНрдгреЛрдВ рд╕реЗ рдЕрдзрд┐рдХ рдирд╣реАрдВ рд╣реИ, рд╕реНрд░реЛрдд рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреЗ рд╕рднреА рд╡рд░реНрдг рд▓реИрдЯрд┐рди рд╡рд░реНрдгрдорд╛рд▓рд╛ рдХреЗ рдмрдбрд╝реЗ рдЕрдХреНрд╖рд░ рд╣реИрдВред рд╕рдордп рд╕реАрдорд╛: 2 рдПрд╕, рдореЗрдореЛрд░реА рд╕реАрдорд╛: 264 рдПрдордмреАред

рдЗрдирдкреБрдЯ рдкреНрд░рд╛рд░реВрдк
рдЗрдирдкреБрдЯ рдХреА рдПрдХ рд▓рд╛рдЗрди рдореЗрдВ рдПрдХ рдиреЙрди-рдЦрд╛рд▓реА рд▓рд╛рдЗрди рд╣реЛрддреА рд╣реИред рдпрд╣ рдЧрд╛рд░рдВрдЯреА рд╣реИ рдХрд┐ рдпрд╣ рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреБрдЫ рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреЗ рд╕рд╣реА RLE рд╕рдВрдкреАрдбрд╝рди рдХрд╛ рдкрд░рд┐рдгрд╛рдо рд╣реИред

рдЖрдЙрдЯрдкреБрдЯ рд╕реНрд╡рд░реВрдк
рд╕реНрд░реЛрдд рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреА рд▓рдВрдмрд╛рдИ рдкреНрд░рд┐рдВрдЯ рдХрд░реЗрдВред

рдлреЗрд╕рд▓рд╛
.

, . , . тАФ . тАФ . , .

O(n) O(1) (O(n) ).

first_symbol = True
result = 0
number = ''

for c in input():
    if c.isdigit():
        number += c
    elif c.isalpha() and not number:
        if first_symbol:
            first_symbol = False
        else:
            result += 1
    elif c.isalpha() and number:
        result += int(number)
        number = ''
	
if number:
    result += int(number)
else:
    result += 1
print(result)

DDoS рдбрд┐рдЯреЗрдХреНрдЯрд░

рд▓реЗрдЦрдХ: рд╕рд░реНрдЧреЗрдИ рдбреЗрдореБрд░рд┐рди kakty3ред рд╕рдорд╕реНрдпрд╛ рдХреЛ 7% рдкреНрд░рддрд┐рднрд╛рдЧрд┐рдпреЛрдВ рджреНрд╡рд╛рд░рд╛ рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдерд╛ред

рдПрди рдЖрдИрдкреА рдкрддреЛрдВ рдХреА рдПрдХ рд╕реВрдЪреА рджреА рдЧрдИ рдереАред рд╣рдо рдПрдХ рдЖрдИрдкреА рдПрдбреНрд░реЗрд╕ рдХреЛ "рдЦрд░рд╛рдм" рдХрд╣рддреЗ рд╣реИрдВ рдпрджрд┐ M рд▓рдЧрд╛рддрд╛рд░ рд▓рд╛рдЗрдиреЗрдВ рд╣реИрдВ рдЬрд┐рд╕рдореЗрдВ рдпрд╣ IP рдкрддрд╛ рдХрдо рд╕реЗ рдХрдо K рдмрд╛рд░ рд╣реЛрддрд╛ рд╣реИред рд╕рдордп рд╕реАрдорд╛: 10 рдПрд╕, рдореЗрдореЛрд░реА рд╕реАрдорд╛: 10 рдПрдордмреАред

рдЗрдирдкреБрдЯ рдкреНрд░рд╛рд░реВрдк
рдкрд╣рд▓реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдирдВрдмрд░ N (1 тЙд N)10 6 ) рд╣реЛрддрд╛ рд╣реИред
рджреВрд╕рд░реА рдкрдВрдХреНрддрд┐ рдореЗрдВ M (1 line M)10 3 ) рд╕рдВрдЦреНрдпрд╛ рд╣реЛрддреА рд╣реИред
рддреАрд╕рд░реА рдкрдВрдХреНрддрд┐ рдореЗрдВ рдирдВрдмрд░ K (1 line Kред M) рд╣реЛрддрд╛ рд╣реИред
рдЕрдЧрд▓реА N рд▓рд╛рдЗрдиреЛрдВ рдореЗрдВ IP рдкрддреЗ, рдкреНрд░рддрд┐ рдкрдВрдХреНрддрд┐ рдПрдХ рд╣реЛрддреЗ рд╣реИрдВред

рдЖрдЙрдЯрдкреБрдЯ рд╕реНрд╡рд░реВрдк
рд▓реЗрдХреНрд╕рд┐рдХреЛрдЧреНрд░рд╛рдлрд╝рд┐рдХ рдХреНрд░рдо рдореЗрдВ рдЦрд░рд╛рдм рдЖрдИрдкреА рдкрддреЛрдВ рдХреЛ рд╕реВрдЪреАрдмрджреНрдз рдХрд░рддрд╛ рд╣реИред

рдлреЗрд╕рд▓рд╛
: , M , K . , - .

: тАФ M . M. , тЙе K. , , .

, тАФ . :
тАФ ,
тАФ ┬л┬╗ , K.

, IP- . 106. . , , . 103.

O(N) IP- O(M) .

# coding: utf-8
from collections import Counter, deque
import sys

def main():
    #   N, M  K
    n_of_lines = int(sys.stdin.readline().strip())
    window_size = int(sys.stdin.readline().strip())
    threshold = int(sys.stdin.readline().strip())

    #    ┬л┬╗ ,
    #     
    #   
    bad_ips = set()
    last_ips = deque(maxlen=window_size)
    counter = Counter()

    for _ in range(n_of_lines):
        #  IP-
        current_ip = sys.stdin.readline().rstrip()

        # ,   
        if len(last_ips) == window_size:
            #      
            #      
            oldest_ip = last_ips.pop()
            counter[oldest_ip] -= 1

            #      тАФ  
            if not counter[oldest_ip]:
                del counter[oldest_ip]

        #     
        last_ips.appendleft(current_ip)

        #        ┬л┬╗,
        #      
        if current_ip in bad_ips:
            continue

        #     
        counter[current_ip] += 1

        #      K,
        #      ┬л┬╗
        if counter[current_ip] >= threshold:
            bad_ips.add(current_ip)
            #  ┬л┬╗   ,
            #     
            del counter[current_ip]

    #  ┬л┬╗    
    print('\n'.join(current_ip for current_ip in sorted(bad_ips)))

if __name__ == "__main__":
    main()

рдпреЗ рдХрд╛рд░реНрдп рдмреИрдХреЗрдВрдб рдбреЗрд╡рд▓рдкрдореЗрдВрдЯ рд╕реНрдХреВрд▓ рдореЗрдВ рдкрд░рд┐рдЪрдпрд╛рддреНрдордХ рдЕрд╕рд╛рдЗрдирдореЗрдВрдЯ рдХрд╛ рдкрд╣рд▓рд╛ рд╣рд┐рд╕реНрд╕рд╛ рдереЗред рджреВрд╕рд░рд╛ рднрд╛рдЧ (рдХреНрд▓рд╛рдЙрдб рд╕реЗрд╡рд╛) рд╣рдо рдЖрдиреЗ рд╡рд╛рд▓реЗ рд╣рдлреНрддреЛрдВ рдореЗрдВ рдкреНрд░рдХрд╛рд╢рд┐рдд рдФрд░ рд╡рд┐рд╢реНрд▓реЗрд╖рдг рдХрд░реЗрдВрдЧреЗред

рдпрджрд┐ рдЖрдк рдмреИрдХрд░реНрд╕ рдХреЗ рд▓рд┐рдП рдкреНрд░рддрд┐рдпреЛрдЧрд┐рддрд╛рдУрдВ рдореЗрдВ рд░реБрдЪрд┐ рд░рдЦрддреЗ рд╣реИрдВ, рддреЛ рдкрд╣рд▓реА рдФрд░ рджреВрд╕рд░реА рдкреНрд░реЛрдЧреНрд░рд╛рдорд┐рдВрдЧ рдЪреИрдВрдкрд┐рдпрдирд╢рд┐рдк рдХреЗ рдмреИрдХрдПрдВрдб рдЯреНрд░реИрдХ рдХреЗ рд╡рд┐рд╢реНрд▓реЗрд╖рдг рдХреЛ рдкрдврд╝реЗрдВ ред

All Articles