Aitu Icode 2 тур

Информатика
1

image
image693×608 70 KB

image
image717×612 57.5 KB

image
image716×729 93.4 KB

Долго голову ломал как это решить, можете плиз помочь?

3 лайка
2023: годовой обзор
2

Какие были попытки решения?

3

К сожелению код не сохранился!
Задача В
Тут просто два цикла на номинал для 500 и 1000, где внутри ифом проверяем 500*cnt >= 500/1000
{
сups++;
cnt = 0;
}
Но думаю там все сложнее так как в олимпиаде этот код тесты не проходил.
У меня есть код, который правильный, но проблема в том, что я не понимаю для чего и как использовались некоторые его части. Сам код:

a, b, x = map(int, input().split())
cups = 0
money = a*500 + b*1000

if x <= 500:
    print(a + b)
elif x <= 1000:
    print(b + a//2)
else:
    price = x//500*500 + 500*(1 if x % 500 else 0)
    # print('price:', price)
    # print(money)

    while money > 0:
        to_pay = price
        b1 = price // 1000

        if b1 > b:
            to_pay -= b*1000
            money -= b*1000
            b=0
        else:
            to_pay -= b1*1000
            money -= b1*1000
            b -= b1

        a1 = to_pay / 500

        if a1 > a:
            to_pay -= a*500
            money -= a*500
            a=0
        else:
            to_pay -= a1*500
            money -= a1*500
            a -= a1
        
        if to_pay > 0 <= 1000: 
            if b > 0:
                cups += 1
                b -= 1
                money -= 1000
            
            elif b == 0 and a == 0:
                break
        elif to_pay == 0:
            cups += 1
        else:
            break

    print(cups)

Задача D
Тут тоже просто 3 цикла, но выходит на тайм лимит. Пытался сделать что-то вроде формулы, но все равно безуспешно. Как можно оптимизировать код для более быстрой работы?

Задача E
Тут я не понял само задание. То есть по моему пониманию необходимо найти в столбце самую большую цифру, то есть самого сильного проффесионала в этой сфере. Но, меня смущает то, что во 2 столбце выбрали число 18 а не число 21, и по факту 21 > 18, но почему то выбрали 18!!! Я в замешательстве!

4

Подсказки к задаче D

Подсказка 1

Если
\displaystyle{a_i \ast a_j = \sum_{k \neq i, j} a_k \iff a_i + a_j + a_i \ast a_j = \sum_{k = 1}^n a_k} \displaystyle {\iff 1 + a_i + a_j + a_i \ast a_j = S + 1 \iff (1+a_i) \ast (1 + a_j) = S + 1}

Подсказка 2

Пусть b_i = 1 + a_i
Нужно понять, есть ли b_i, b_j: b_i*b_j = S + 1
Попробуй разбить их на группы b_i < \sqrt{S + 1}, b_i > \sqrt{S+1} и отсортировать обе

Подсказка 3

Для каждого b_i из первой группы, определи бинарным поиском, есть ли подходящий b_j из второй группы сложность такого решения O(n * log(n))

7 лайков
5

Замешательство, связанное с этим, наверное прошло уже, но мало ли

Если взять 21 во втором столбце, нельзя взять 23 в третьем, а по условию нельзя брать числа, стоящие в одной строке. Если не взять 23 в третьем, придется брать второе максимальное число, т.е. 20. Но тогда на позицию дизайнера придется брать чела с уровнем 17, тогда сумма выбранных элементов будет 21 + 20 + 17 = 58, тогда как 18 + 23 + 20 = 61.

Недостаточно найти просто максимальное значение в столбце и просуммировать, это сработает только в частном случае, когда самый высокий уровень каждого навыка будет у разных людей, т.е. максимумы столбцов не лежат в одной строке.

2 лайка
6

Задачи где-то сдать можно?

7

Думаю нет

8

Здравствуйте! Вы решили задачу Е?

Решение задачи В
from math import ceil

a, b, x = map(int, input().split())

mn, mx = min(a, b), max(a, b)
i1 = ceil(x / 500)
i2 = ceil(x / 1000)
i3 = ceil(x / 1500)

if x < 1000:
print(int(a / i1 + b / i2))
elif x >= 1500:
print((a * 500 + b * 1000) // x)
else:
print(mn // i3 + (mx - mn) // (i1 if a == mx else i2))

А задачу Е не могу решить

9

@Damir_Ryskulbek