Підготовка заздалегідь учня 8 класу до обласної олімпіади через сайт E-Olimp

Дата: сьогодні о 09:34

Автор: Світлана Ф. Н.

3 перегляда

Задача E1: Сума двох чисел

Умова:
Користувач вводить два числа. Вивести їхню суму.

✔ Розв’язок:
a = int(input())
b = int(input())
print(a + b)

Задача E2: Перевірка парності

Умова:
Ввести число і вивести "Even" або "Odd".

✔ Розв’язок:
n = int(input())
print("Even" if n % 2 == 0 else "Odd")

Задача E3: Модуль числа

Умова:
Вивести абсолютне значення введеного числа (без використання abs()).

✔ Розв’язок:
n = int(input())
if n < 0:
    n = -n
print(n)

Рівень M — Medium
Задача M1: Паліндром

Умова:
Перевірити, чи є рядок паліндромом.

✔ Розв’язок:
s = input()
print("Yes" if s == s[::-1] else "No")

Задача M2: Частота елементів

Умова:
За списком чисел вивести словник частот.

✔ Розв’язок:
nums = list(map(int, input().split()))
freq = {}

for n in nums:
    freq[n] = freq.get(n, 0) + 1

print(freq)

Задача M3: Унікальні елементи списку

Умова:
Ввести список чисел та вивести тільки унікальні значення у порядку появи.

✔ Розв’язок:
nums = list(map(int, input().split()))
seen = set()
result = []

for n in nums:
    if n not in seen:
        seen.add(n)
        result.append(n)

print(result)

🟨 Рівень H — Hard
Задача H1: Правильна послідовність дужок

Умова:
Визначити, чи є дужкова послідовність правильною.

✔ Розв’язок:
s = input()
stack = []

pairs = {')':'(', ']':'[', '}':'{'}

ok = True
for ch in s:
    if ch in "([{":
        stack.append(ch)
    else:
        if not stack or stack.pop() != pairs[ch]:
            ok = False
            break

print("YES" if ok and not stack else "NO")

Задача H2: Рекурсивний факторіал

Умова:
Обчислити n! рекурсією.

✔ Розв’язок:
def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

print(fact(int(input())))

Задача H3: Бінарний пошук

Умова:
Знайти елемент x у відсортованому списку.

✔ Розв’язок:
arr = list(map(int, input().split()))
x = int(input())

l, r = 0, len(arr) - 1
found = False

while l <= r:
    mid = (l + r) // 2
    if arr[mid] == x:
        found = True
        break
    elif arr[mid] < x:
        l = mid + 1
    else:
        r = mid - 1

print("Found" if found else "Not found")

🟥 Рівень S — Supreme (дуже складні)
Задача S1: Найдовша зростаюча підпослідовність (LIS)

Умова:
Знайти довжину LIS.

✔ Розв’язок:
import bisect

arr = list(map(int, input().split()))
dp = []

for x in arr:
    pos = bisect.bisect_left(dp, x)
    if pos == len(dp):
        dp.append(x)
    else:
        dp[pos] = x

print(len(dp))

Задача S2: Задача рюкзака (0/1 knapsack)

Умова:
Є ваги w[], цінності v[], місткість W. Макс. цінність.

✔ Розв’язок:
n, W = map(int, input().split())
w = []
v = []
for _ in range(n):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)

dp = [[0]*(W+1) for _ in range(n+1)]

for i in range(1, n+1):
    for cap in range(W+1):
        dp[i][cap] = dp[i-1][cap]
        if cap >= w[i-1]:
            dp[i][cap] = max(dp[i][cap], dp[i-1][cap - w[i-1]] + v[i-1])

print(dp[n][W])

Задача S3: Найкоротший шлях у графі — алгоритм Дейкстри
✔ Розв’язок:
import heapq

n, m = map(int, input().split())
graph = [[] for _ in range(n)]

for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

start = int(input())

dist = [10**18]*n
dist[start] = 0
pq = [(0, start)]

while pq:
    d, node = heapq.heappop(pq)
    if d > dist[node]:
        continue
    for to, w in graph[node]:
        if dist[to] > dist[node] + w:
            dist[to] = dist[node] + w
            heapq.heappush(pq, (dist[to], to))

https://eolymp.com/uk/contests/4usu8j57353kj76bh7mj7dv4jk/rules