Инженерный тур. 2 этап

Выплата за лот складывается из второй ставки (следующей за выигрышной), к которой прибавляется 10%. Если эта сумма больше истинной ценности, лот выставляется повторно.

Оптимальное решение не требует итерационно моделировать аукцион второй цены. Достаточно отсортировать ставки по убыванию и определить первую ставку, которая будет меньше истинной ценности с наценкой 10%. Участник со ставкой выше этой и будет итоговым владельцем лота.

Авторское решение задачи приведено на языке Python 3.12.

from dataclasses import dataclass

@dataclass
class Item:
    bet: float
    participant: int

N, C = input().split()
N = int(N)
C = float(C)

items = []

for i in range(N):
    elem = float(input())
    items.append(Item(bet=elem, participant=i))

items.sort(key=lambda x: x.bet, reverse=True)

winner = -1
for i in range(1, len(items)):
    cost = items[i].bet + items[i].bet * 0.1

    if cost < C:
        winner = items[i-1].participant
        break

print(winner)

Это продолжение первой подзадачи. Имея отсортированный список ставок, достаточно просуммировать 10% комиссии от всех ставок, начиная со второй максимальной и заканчивая следующей за номером итогового владельца (который определяется в первой подзадаче).

Авторское решение задачи приведено на языке Python 3.12.

from dataclasses import dataclass

@dataclass
class Item:
    bet: float
    participant: int

N, C = input().split()
N = int(N)
C = float(C)

items = []

for i in range(N):
    elem = float(input())
    items.append(Item(bet=elem, participant=i))

items.sort(key=lambda x: x.bet, reverse=True)

winner = -1
profit = 0.0
for i in range(1, len(items)):
    profit += items[i].bet * 0.1
    cost = items[i].bet + items[i].bet * 0.1

    if cost < C:
        winner = items[i-1].participant
        break

# print(winner)
print(f"{profit:.4f}")

Решение строится по принципу динамического программирования. Строим матрицу вероятностей для случая \(N = 0\) (какова вероятность, что конь следующим ходом придет в начальное положение?), после чего последовательно пересчитываем матрицу для случая на ход больше, пока не придем к \(N\). Для большей точности предлагается использовать библиотеку fractions. Чтобы решение уложилось в ограничение по времени выполнения, следует обратить внимание, что матрица вероятностей симметрична относительно начальной точки по линиям вдоль и поперек ленты. Таким образом, достаточно считать лишь четверть поля.

Авторское решение задачи приведено на языке Python 3.12.

# используем Fraction для большей точности
from fractions import Fraction as frac

L, N = map(int, input().split())
# оптимизация: число ходов должно быть нечётным
if N % 2 == 0:
    print(0.0)
    from sys import exit
    exit()

W = 5
WM, L2 = W // 2, L * 2 
WX, LX = WM + 1, L + 1 # размеры матрицы
s_col, s_row = WM, 0 # начальное положение

# матрицы для расчёта вероятностей
probs = [[frac(0) for _ in range(WX)] 
          for _ in range(LX)]
new_probs = [[frac(0) for _ in range(WX)] 
              for _ in range(LX)]
# смещения для хода коня
deltas = [
    (-2, -1), (-2, +1), (+2, -1), (+2, +1),
    (-1, -2), (-1, +2), (+1, -2), (+1, +2),
]

def wr(col, row, value): # запись в матрицу
    if not 0 <= col < W: return
    # оптимизация: симметрия вдоль ленты
    if col > WM: col = W-1-col
    # учитываем бесконечность ленты
    row = row % L2
    # оптимизация: симметрия от начальной точки
    if row > L: row = 2*L-row
    probs[row][col] = value

def get(col, row): # чтение из матрицы
    if not 0 <= col < W: return frac(0), 0
    if col > WM: col = W-1-col
    row = row % L2
    if row > L: row = 2*L-row
    return probs[row][col], 1

# заполняем конечное положение
for dc, dr in deltas:
    wr(s_col + dc, s_row + dr, frac(1))
# производим обратный расчёт
for mv in range(N):
    for row in range(LX):
        for col in range(WX):
            a, b = map(sum, zip(
                get(col+2, row+1), get(col+2, row-1),
                get(col-2, row+1), get(col-2, row-1),
                get(col+1, row+2), get(col+1, row-2),
                get(col-1, row+2), get(col-1, row-2)
            ))
            new_probs[row][col] = a / b
    new_probs, probs = probs, new_probs
# выводим ответ
print(float(probs[s_row][s_col]))

В задаче рассматривается произвольный граф, для которого необходимо рассчитать наименее проходимую вершину. Аналитическое решение имеет слишком высокую вычислительную сложность (для каждой вершины необходимо провести перебор на большую глубину). По этой причине предлагается использование метода Монте-Карло: моделирование достаточно большого числа блужданий, чтобы получить статистику по посещаемости всех вершин графа, после определения наиболее редкой вершины.

Авторское решение задачи приведено на языке Python 3.12.

import random
import sys
from typing import List, Tuple, DefaultDict, Dict
from dataclasses import dataclass
from collections import defaultdict

N = 25000

@dataclass
class Transition:
    """
    Однонаправленный переход из одного узла в другой.
    Двунаправленный переход состоит из двух однонаправленных.
    """
    from_node: int  # Откуда
    to_node: int  # Куда
    weigth: int  # Вес
    probabilty: Tuple[float, float] = tuple([0., 0.])  # Вероятность пойти

class Node:
    transitions: List[Transition]

    def __init__(self):
        # Каждый узел характеризуется списком исходящих переходов
        self.transitions = []

    def set_probabilities(self) -> None:
        # Сумма всех весов исходящих переходов
        weigth_sum = sum(transition.weigth for transition in self.transitions)
        # Выставляем вероятности пойти по переходу в виде интервалов
        # (например, [0.0, 0.15], [0.16, 1.0])
        min_value = 0.0
        for transition in self.transitions:
            high_value = min_value + transition.weigth / weigth_sum
            transition.probabilty = [min_value, high_value]
            min_value = high_value

    def get_transition(self) -> Transition:
        # Получить случайный переход
        prob = random.random()
        for transition in self.transitions:
            min_value, max_value = transition.probabilty

            if prob > min_value and prob <= max_value:
                return transition

        raise Exception('No transitions!')

def walk(nodes: Dict[str, Node], N: int):
    # По умолчанию для всех узлов количество переходов равно нулю
    count: DefaultDict[str, int] = defaultdict(lambda: 0)

    def get_random_node() -> Node:
        nonlocal nodes
        node = random.choice(list(nodes.values()))

        return node

    for i in range(N):
        # начинаем в случайном узле
        current_node = get_random_node()
        for _ in range(100):
            transition = current_node.get_transition()
            count[transition.to_node] += 1
            # Добавляем в счетчик, что мы посетили узел
            current_node = nodes[transition.to_node]

    return count

data = sys.stdin.readlines()[1:]

nodes: DefaultDict[str, Node] = defaultdict(lambda: Node())
# Считывание исходных данных
for unprocessed_transition in data:
    from_node, to_node, weigth = map(int, unprocessed_transition.split())
    # Так как переход двухнаправленный, добавляем
    # переход в оба узла
    nodes[from_node].transitions.append(
        Transition(from_node, to_node, weigth))
    nodes[to_node].transitions.append(
        Transition(to_node, from_node, weigth))

# Приводим вероятности в виде интервалов для всех узлов
for node in nodes.values():
    node.set_probabilities()

statistic = walk(nodes, N)
# Сортируем узлы по количеству переходов в них
sorted_nodes = sorted(statistic.keys(), key=lambda key: statistic[key])

print(sorted_nodes[0], flush=True)

В авторском решении сначала производится по пять выходов на минтая и тунца, и рассчитывается статистика успешности каждого выхода. Цель следующих выходов выбирается, исходя из наибольшего математического ожидания прибыли (произведение текущей вероятности успеха и дохода за улов), и также дополняет статистику, влияя на дальнейший выбор.

Авторское решение задачи приведено на языке Python 3.12.

N = 50
REWARD_PO, REWARD_TU = 15, 30
CH_PO, CH_TU = 0, 1
WARMUP = 5

class Thinker:
    def __init__(self):
        self.time = 0
        self.po_found = self.po_fail = 0
        self.tu_found = self.tu_fail = 0
        
    def think(self):
        # пробные заходы
        if self.time < WARMUP: return CH_TU
        if self.time < WARMUP * 2: return CH_PO
        # считаем вероятности успеха 
        po = self.po_found / (self.po_found + self.po_fail)
        tu = self.tu_found / (self.tu_found + self.tu_fail)
        # оцениваем выгоду и принимаем решение
        is_pollock = po * REWARD_PO > tu * REWARD_TU
        choice = CH_PO if is_pollock else CH_TU
        return choice

    def update(self, choice, result):
        # обновление статистики
        self.time += 1
        if choice == CH_PO:
            if result:
                self.po_found += 1
            else:
                self.po_fail += 1
        elif choice == CH_TU:
            if result:
                self.tu_found += 1
            else:
                self.tu_fail += 1

t = Thinker()
for _ in range(N):
    # принятие и отправка решения
    choice = t.think()
    msg = "POLLOCK" if choice == CH_PO else "TUNA"
    print(msg, flush=True)
    # получение и обработка обратной связи
    answer = input()
    answer = 1 if answer == "YES" else 0
    t.update(choice, answer)

Первая попытка состоит из случайного набора жестов. Результат этой попытки записывается как наилучший. Дальше производятся попытки улучшить результат путем замены случайного подотрезка другим набором жестов (по сути, максимизация результата по обратной связи). Когда остается последняя попытка, повторно отсылается наилучшее найденное решение.

Авторское решение задачи приведено на языке Python 3.12.

from random import randint

N, SEG_N = 300, 10

def encode(xs): # для формирования вывода
    return ' '.join(['ROCK', 'PAPER', 'SCISSORS'][x] for x in xs)

# делаем случайное решение
base = [randint(0, 2) for _ in range(N)]
print(encode(base), flush=True)
# записываем его результат как лучший
r, _ = input().split()
best_res = int(r)

while True:
    # улучшаем решение заменой случайного подотрезка
    new = base.copy()
    salt_i = randint(0, N-SEG_N-1)
    new[salt_i:salt_i+SEG_N] = [randint(0, 2) for _ in range(SEG_N)]
    print(encode(new), flush=True)
    r, t = input().split()
    # проверяем, улучшилось ли решение
    res = int(r)
    if res > best_res:
        best_res, base = res, new
    # прерываемся, если осталась одна попытка
    if t == "1": break

# отправляем наилучшее решение
print(encode(base), flush=True)
_ = input()
 

1. По типу многогранника и длине грани вычисляем площадь поверхности \(S\).
2. По количеству новых тел \(m\) определяем площадь поверхности малого тела \(S_m\) (через объем или с помощью пропорции).
3. Вычисляем площадь разрушенного слоя воды. Он составит половину разницы площадей, так как на две новые грани приходится один разрушенный слой: \[\vartriangle S = \frac{S - (S_m \cdot m)}{ 2}.\]
4. Представим занимаемую молекулой воды площадь как круг диаметром 0,28 нм. Тогда количество расплавленных молекул составит отношение площади слоя к площади этого круга.
5. Умножаем число молекул на массу молекулы воды и умножаем на удельную теплоту его плавления.

Таким образом получаем теплоту, выделенную при разделении многогранника на \(m\) подобных многогранников.

Авторское решение задачи приведено на языке Python 3.12.

from math import sqrt, pi
S_C = {
    'tetrahedron': sqrt(3),
    'hexahedron': 6,
    'octahedron': 2 * sqrt(3),
    'dodecahedron': 3 * sqrt(25 + 10 * sqrt(5)),
    'icosahedron': 5 * sqrt(3),
}
lam = 330 # Дж/г
d_h2o = 0.28 # нм
S_h2o = ((d_h2o / 2) ** 2) * pi # нм2
m_h2o = 2.99e-23 # г (10^-23)

# подготавливаем входные данные
b, a, m = input.split()
a = float(a) * 1000 # um -> nm
m = int(m)
# считаем изменение площади поверхности
S = S_C[b] * a**2 # nm2
S_m = S / (m ** (2/3)) # nm2
dS = (S_m * m - S) / 2 # nm2
# пересчитываем в молекулы
n_h2o = dS / S_h2o # unit
# рассчитываем итоговую теплоту
p = n_h2o * m_h2o * lam / 1e-9 # nJ
print(p)

Авторское решение укладывается в ограничения задачи и работает путем обхода карты фиксированным циклическим набором команд. Результат каждого сканирования накладывается на считанную карту так, чтобы получить ячейки, на которых может находиться беспилотник. Число ориентиров на такой ячейке будет не меньше, чем обнаружено в ходе сканирования. Имея матрицу для предыдущего и текущего сканирования, а также смещение по матрице (на соседнюю ячейку), можно определить пары соседних ячеек, на которых мог находиться беспилотник, и тем самым отсеять часть вариантов. Таким образом, множество ячеек итерационно сводится к единственному варианту.

Авторское решение задачи на языке Python 3.12.

from copy import deepcopy
INF = float('inf')
MAP_N, MAP_M = 30, 30
N_ORIENT = 3
CMD_LEFT, CMD_RIGHT = "LEFT", "RIGHT"
CMD_UP, CMD_DOWN = "UP", "DOWN"
CMD_SOLVE = "HELPME"
DELTAS = {
    CMD_LEFT: (-1, 0), CMD_RIGHT: (1, 0),
    CMD_UP: (0, -1), CMD_DOWN: (0, 1),
}

def find_coord(f):
    # поиск первого ненулевого элемента
    for j in range(len(f)):
        for i in range(len(f[j])):
            if f[j][i]:
                return (i, j)
    return None

def filter_orient(m, sm):
    # получить бинарную матрицу ячеек, 
    # где число ориентиров не меньше заданного
    return [
        [ all(x >= rx for (x, rx) in zip(c, sm))
          for c in l
        ] for l in m
    ]

def filter_connected(rm1, rm2, delta):
    # наложение бинарных матриц со сдвигом
    dx, dy = delta
    rm = deepcopy(rm2)
    for j in range(len(rm)):
        for i in range(len(rm[j])):
            x = (i - dx) % len(rm[j])
            y = (j - dy) % len(rm)
            if not rm1[y][x]:
                rm[j][i] = False
    return rm

my_map = None
step_log = []
scan_log = []
filters = []

steps = [
    CMD_DOWN,
    CMD_RIGHT,
    CMD_UP,
    CMD_RIGHT,
]
move_idx = 0

def next_move() -> str:
    global move_idx
    move_idx = (move_idx + 1) % len(steps)
    return steps[move_idx]

msg = input()
if msg[:3] == "MAP":
    # чтение карты
    toks = msg.split()
    map_type, MAP_N, MAP_M = int(toks[1]), int(toks[2]), int(toks[3])
    my_map = [[None for _ in range(MAP_N)] for _ in range(MAP_M)]
    if map_type == 1:
        # ориентиры помещаются в ячейку как есть
        for j in range(MAP_M):
            line = input().split()
            for i in range(MAP_N):
                c = line[i].split(";")
                my_map[j][i] = tuple(int(c[k]) for k in range(N_ORIENT))
    else: # map_type == 2
        # сначала считываем карту
        raw_map = [[None for _ in range(MAP_N)] for _ in range(MAP_M)]
        for j in range(MAP_M):
            line = input().split()
            for i in range(MAP_N):
                c = line[i].split("-")
                raw_map[j][i] = tuple(int(k) for k in c)
        # кладём ориентиры во все ячейки, граничащие с соответствующим углом
        my_map = [[[0 for _ in range(N_ORIENT)] for _ in range(MAP_N)] for _ in range(MAP_M)]
        for j in range(MAP_M):
            for i in range(MAP_N):
                for dx in (0, 1): 
                    for dy in (0, 1):
                        cell = raw_map[(j+dy) % MAP_M][(i+dx) % MAP_N]
                        my_map[j][i][cell[0]] += cell[1]
else:
    raise ValueError("Expected MAP")

while True:
    # запрашиваем результат сканирования
    msg = input().split()
    if msg[0] == "YES" or msg[0] == "NO":
        break # штатное завершение
    msg = tuple(map(int, msg))
    scan_log.append(msg)
    # получаем вероятные ячейки
    if filters:
        filters.append(filter_connected(filters[-1], filter_orient(my_map, scan_log[-1]), step_log[-1]))
    else:
        filters.append(filter_orient(my_map, scan_log[-1]))
    # положение определено однозначно?
    if sum(1 for l in filters[-1] for c in l if c) == 1:
        print("HELPME", *find_coord(filters[-1]), flush=True)
        continue
    # делаем следующий ход
    move = next_move()
    step_log.append(DELTAS[move])
    print(move, flush=True)