Красивый город

from random import randint
from typing import Iterable
 
 
def sort_attractions_by_score(attractions: list[list[str, int, int]]) -> Iterable[list[str, int, int]]:
    for _ in range(len(attractions)):
        mx = max(attractions, key=lambda x: x[1])
        attractions.remove(mx)
        yield mx
 
 
def __generate_attractions() -> list[list[str, int, int]]:
    return [[f'a{i + 1}', score := (randint(1, 5000)), (cst := score * randint(1, 10)) + (50 - cst % 50)]
            for i in range(randint(1, 9999))]
 
 
def __generate_money() -> int:
    return randint(1, 99999)
 
 
def main() -> None:
    # from sys import stdin
    #
    # data = stdin.readlines()
    # money = int(data.pop(0))
    # attractions = list(map(lambda x: x.split()[:1] + list(map(int, x.split()[1:])), data))
 
    money = __generate_money()
    attractions = sort_attractions_by_score(__generate_attractions())
    to_visit = []
 
    for i in range(32):  # 16 дней по 2 аттракциона
        try:
            attraction = next(attractions)  # название, баллы, цена
        except StopIteration:
            break
        if money < attraction[2]:
            continue
        to_visit.append(attraction[0])
    print(to_visit)
 
 
if __name__ == '__main__':
    main()

def optimal_places(money, places):
    n = len(places)
    dp = [[0] * (n + 1) for _ in range(money // 50 + 1)]
    chosen = [[False] * (n + 1) for _ in range(money // 50 + 1)]
 
    for i in range(1, n + 1):
        for j in range(money // 50 + 1):
            dp[j][i] = dp[j][i-1]  
 
            remaining_money = j * 50 - places[i-1][1] 
            if remaining_money >= 0 and dp[remaining_money // 50][i-1] + places[i-1][0] > dp[j][i]:
                dp[j][i] = dp[remaining_money // 50][i-1] + places[i-1][0]
                chosen[j][i] = True
 
    results = []
    i = money // 50
    for j in range(n, 0, -1):
        if chosen[i][j]:
            results.append(places[j-1][2])
            i -= places[j-1][1] // 50
 
    return results[::-1]
 
money = int(input())
n = int(input())
 
places = []
for _ in range(n):
    interest, cost, name = input().split(";")
    interest = int(interest)
    cost = int(cost)
    places.append((interest, cost, name))
 
result = optimal_places(money, places)
 
if not result:
    print("Нет достопримечательностей, которые можно посетить.")
else:
    print(";".join(result))