Ak máš hocijaké otázky k tejto úlohe, napíš Andrejovi na [email protected]
Vedúci pripravovali úlohy a z toľkého pripravovania poriadne vyhladli. Rozhodli sa teda ísť na obed, ale predtým delegovali svoju robotu veľkým jazykovým modelom.
Keď sa spokojne naobedovali, zistili, že veľké jazykový modely úspešne napísali programy, tie ale obsahovali chyby. S plným bruchom sa im ale nechcelo programy opravovať, a tak to nechali na teba.
Úloha
Dostaneš niekoľko programov, ktoré majú bugy. Tvojou úlohou je kódy opraviť. Aby to ale nebolo také jednoduché, musíš to spraviť s čo najmenej úpravami pôvodného kódu.
Na plný počet bodov budeš pravdepodobne potrebovať uplatniť viacero syntaktických trikov.
Malý hint: v pythone vieš dať viacero príkazov na jeden riadok, pokiaľ ich oddelíš bodkočiarkou.
Bubble sort
Vstup
Na vstupe je \(n\) celých čísiel (\(n \leq 1000\)).
Výstup
Vypíš ich zoradené.
Program
### 1.py
def bubble_sort(arr):
"""Sorts an array using bubble sort algorithm."""
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[i], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(" ".join(bubble_sort(input().split())))Halda
Dostávaš požiadavku + x a -, pri každej
vypíšeš aktuálny najväčší prvok haldy.
Vstup
Na prvom riadku je číslo \(n\) - počet požiadaviek.
Nasleduje \(n\) riadkov, buď
+ x (pridať do haldy prvok \(x\)) alebo - (odstrániť
najväčší prvok).
Výstup
Pri každej operácií vypíš aktuálne najväčší prvok.
Program
### 2.py
class Heap:
"""Alternative heap implementation instead of heapq."""
def __init__(self):
self.data = []
def push(self, what: int):
self.data.append(what)
where = len(self.data)
while where > 0:
parent = (where) // 2
if self.data[where] > self.data[parent]:
self.data[where], self.data[parent] = self.data[parent], self.data[where]
where = parent
else:
break
def pop(self) -> int:
n = len(self.data)
answer = self.data[0]
self.data[0], self.data[-1] = self.data[-1], self.data[0]
self.data.pop()
where = 1
while True:
dest = where
left = 2 * where
right = 2 * where + 1
if left < n and self.data[left] > self.data[dest]:
dest = left
if right < n and self.data[right] > self.data[dest]:
dest = right
if dest != where:
self.data[where], self.data[dest] = self.data[dest], self.data[where]
where = dest
else:
return answer
def top(self) -> int:
return self.data[0]
h = Heap()
for i in range(int(input())):
step = input()
if step[0] == "+":
h.push(int(step[1:]))
elif step[0] == "-":
h.pop()
print(h.top() if h.data else "empty")Fibonacci++
Teraz máš funkčný program, ale je napísaný v C++, nie v Pythone… Treba ho teda prepísať do Pythonu.
Vstup
Na vstupe je jedno celé číslo \(n\) (\(0 \leq n \leq 10000\)).
Výstup
Na výstupe vypíš jedno celé číslo – \(n\)-té Fibonacciho číslo.
Program
### 3.py
#include <iostream>
int main() {
unsigned long long prev = 0, curr = 1, next, n;
std::cin >> n;
if (n <= 1)
curr = n;
else
for (int i = 2; i <= n; ++i) {
next = prev + curr;
prev = curr;
curr = next;
}
std::cout << curr << '\n';
return 0;
}Knapsack
Tentokrát máme typický knapsack.
Vstup
Na prvom riadku vstupu sa nachádzajú dve čísla - \(n\) (počet predmetov) a \(W\) (nosnosť batohu).
Na druhom riadku vstupu sa nachádza \(n\) medzerou oddelených čísiel, ktoré reprezentujú váhy jednotlivých predmetov \(w_i\).
Na treťom riadku vstupu sa nachádza \(n\) medzerou oddelených čisiel, ktoré reprezentujú vzácnosti jednotlivých predmetov \(v_i\).
Výstup
Na jedinom riadku výstupu vypíšte jedno číslo – najväčšiu možnú vzácnosť predmetov, ktorá sa vám zmestí do batohu.
Program
### 4.py
# Dynamické programovanie - knapsack
n, w = map(int, input().split())
ws = list(map(int, input().split()))
vs = list(map(int, input().split()))
D = [[0] * (w + 1)] * n
for i in range(n):
for j in range(w - 1):
if ws[i] > j:
if i == 0:
continue
D[i][j] = D[i - 1][j]
else:
if i == 0:
D[i][j] = vs[i]
elif w - ws[i] < 0:
D[i][j] = D[i - 1][j]
else:
D[i][j] = max(D[i - 1][j] + vs[i], D[i - 1][j - ws[i]])
print(D[-1][-1])Quick select
Nájdi \(k\)-ty najmenší prvok.
Vstup
Na prvom riadku sú čísla \(n\) a \(k\) (\(1 \leq k \leq n \leq 1000000\)).
Na druhom riadku je \(n\) medzerou oddelených čísel, ktoré reprezentujú pole.
Výstup
Na jedinom riadku výstupu vypíš jedno číslo – \(k\)-ty najmenší prvok.
Program
### 5.py
import random
def _quick_select_partition(numbers, l, r):
pivot = random.randrange(l, r)
a = l
for b in range(l, r):
if numbers[b] <= pivot:
numbers[a], numbers[b] = numbers[b], numbers[a]
a += 1
numbers[a], numbers[r] = numbers[r], numbers[a]
return a
def quick_select(numbers, kth, l, r):
"""Selects the kth smallest element using quick select algorithm."""
if l == r:
return numbers[l]
q = _quick_select_partition(numbers, l, r)
i = q - l + 1
if kth == i:
return numbers[i]
if kth < i:
return quick_select(numbers, kth, l, q - 1)
return quick_select(numbers, kth - i, q + 1, r)
n, k = map(int, input().split())
numbers = list(map(int, input().split()))
print(quick_select(numbers, k, 0, n - 1))Bodovanie
Za každý opravený program sa dajú získať 4 body. Tieto body sa prenásobia \(e/x\), kde \(e\) je očakávaný počet zmenených znakov (podľa vzoráku) a \(x\) je počet tebou zmenených znakov.
Počet zmenených znakov sa počíta ako levenshteinova vzdialenosť dvoch stringov.
Pri počítaní ti vie pomôcť tento Python skript:
import sys
def levenshtein(a: str, b: str):
a = a.strip()
b = b.strip()
if len(a) == 0:
return len(b)
if len(b) == 0:
return len(a)
n = len(a)
m = len(b)
lev = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(0, n + 1):
lev[i][0] = i
for i in range(0, m + 1):
lev[0][i] = i
for i in range(1, n + 1):
for j in range(1, m + 1):
insertion = lev[i - 1][j] + 1
deletion = lev[i][j - 1] + 1
substitution = lev[i - 1][j - 1] + (1 if a[i - 1] != b[j - 1] else 0)
lev[i][j] = min(insertion, deletion, substitution)
return lev[n][m]
with open(sys.argv[1], "r") as a, open(sys.argv[2], "r") as b:
print(levenshtein(a.read(), b.read()))Ak chceš porovnať súbory a.py a b.py, stačí
spustiť:
python3 test.py a.py b.py
Odovzdávanie
Odovzdaj upravený nasledovný súbor. K tejto úlohe sa neodovzdáva popis.
### 1.py
def bubble_sort(arr):
"""Sorts an array using bubble sort algorithm."""
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[i], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(" ".join(bubble_sort(input().split())))
### 2.py
class Heap:
"""Alternative heap implementation instead of heapq."""
def __init__(self):
self.data = []
def push(self, what: int):
self.data.append(what)
where = len(self.data)
while where > 0:
parent = (where) // 2
if self.data[where] > self.data[parent]:
self.data[where], self.data[parent] = self.data[parent], self.data[where]
where = parent
else:
break
def pop(self) -> int:
n = len(self.data)
answer = self.data[0]
self.data[0], self.data[-1] = self.data[-1], self.data[0]
self.data.pop()
where = 1
while True:
dest = where
left = 2 * where
right = 2 * where + 1
if left < n and self.data[left] > self.data[dest]:
dest = left
if right < n and self.data[right] > self.data[dest]:
dest = right
if dest != where:
self.data[where], self.data[dest] = self.data[dest], self.data[where]
where = dest
else:
return answer
def top(self) -> int:
return self.data[0]
h = Heap()
for i in range(int(input())):
step = input()
if step[0] == "+":
h.push(int(step[1:]))
elif step[0] == "-":
h.pop()
print(h.top() if h.data else "empty")
### 3.py
#include <iostream>
int main() {
unsigned long long prev = 0, curr = 1, next, n;
std::cin >> n;
if (n <= 1)
curr = n;
else
for (int i = 2; i <= n; ++i) {
next = prev + curr;
prev = curr;
curr = next;
}
std::cout << curr << '\n';
return 0;
}
### 4.py
# Dynamické programovanie - knapsack
n, w = map(int, input().split())
ws = list(map(int, input().split()))
vs = list(map(int, input().split()))
D = [[0] * (w + 1)] * n
for i in range(n):
for j in range(w - 1):
if ws[i] > j:
if i == 0:
continue
D[i][j] = D[i - 1][j]
else:
if i == 0:
D[i][j] = vs[i]
elif w - ws[i] < 0:
D[i][j] = D[i - 1][j]
else:
D[i][j] = max(D[i - 1][j] + vs[i], D[i - 1][j - ws[i]])
print(D[-1][-1])
### 5.py
import random
def _quick_select_partition(numbers, l, r):
pivot = random.randrange(l, r)
a = l
for b in range(l, r):
if numbers[b] <= pivot:
numbers[a], numbers[b] = numbers[b], numbers[a]
a += 1
numbers[a], numbers[r] = numbers[r], numbers[a]
return a
def quick_select(numbers, kth, l, r):
"""Selects the kth smallest element using quick select algorithm."""
if l == r:
return numbers[l]
q = _quick_select_partition(numbers, l, r)
i = q - l + 1
if kth == i:
return numbers[i]
if kth < i:
return quick_select(numbers, kth, l, q - 1)
return quick_select(numbers, kth - i, q + 1, r)
n, k = map(int, input().split())
numbers = list(map(int, input().split()))
print(quick_select(numbers, k, 0, n - 1))Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.