26.04 Прочие прототипы

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Посчитаем корзины с определенным количеством монет, для этого заполним ячейки столбца цифрами от 1 до 99, и воспользуемся функцией СЧЁТЕСЛИ. Запишем в ячейку следующую формулу =СЧЁТЕСЛИ(A1:A10000;B1), скопируем её на свободные клеточки столбца. Для удобства перенесем получившуюся таблицу на новый лист. Разделим данные таблицы на два столбца, перенесем значения : во второй столбец и воспользуемся настраиваемой сортировкой по убыванию. Посчитаем количество ящиков, которое можно сформировать. Для этого выберем минимум из количества корзин, в которых содержится 1 и 99 монет или 2 и 98 монет и тд. Заметим, что корзина с 50 монетами встречается четное количество раз, значит можно сформировать в два раза меньше ящиков, чем общее количество корзин. Общее количество получившихся ящиков равно 4653.

Решение 2 (Python)

f = open("26.txt")
n=int(f.readline())
array=[int(n) for n in f.readlines()]
array.sort()
counter = 0
for i in range(0, n - 1):
    for j in range(n - 1, i, -1):
        if (array[i] + array[j] == 100 and array[i] != 0 and array[j] != 0):
            counter += 1
            array[j] = 0
            break
print(counter)

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Посчитаем корзины с определенным количеством монет, для этого заполним ячейки столбца цифрами от 1 до 99, и воспользуемся функцией СЧЁТЕСЛИ. Запишем в ячейку следующую формулу =СЧЁТЕСЛИ(A1:A10000;B1), скопируем её на свободные клеточки столбца. Для удобства перенесем получившуюся таблицу на новый лист. Разделим данные таблицы на два столбца, перенесем значения : во второй столбец и воспользуемся настраиваемой сортировкой по убыванию. Посчитаем количество ящиков, которое можно сформировать. Для этого выберем минимум из количества корзин, в которых содержится 1 и 99 монет или 2 и 98 монет и тд. Заметим, что корзина с 50 монетами встречается четное количество раз, значит можно сформировать в два раза меньше ящиков, чем общее количество корзин. Общее количество получившихся ящиков равно 3845.

Решение 2 (Python)

f = open("26.txt")
n=int(f.readline())
array=[int(n) for n in f.readlines()]
array.sort()
counter = 0
for i in range(0, n - 1):
    for j in range(n - 1, i, -1):
        if (array[i] + array[j] == 100 and array[i] != 0 and array[j] != 0):
            counter += 1
            array[j] = 0
            break
print(counter)

Для получения ответа работает следующий жадный алгоритм: давайте делать каждый следующий новый ингредиент из двух наименьших по значению ингредиентов. Проделаем эту операцию раз и получим ответ

Почему это работает? Рассмотрим ситуацию, в которой мы кладем два ингредиента, которые образовались из двух различных наборов ингредиентов: и со значениями и соответственно, и для определенности . Тогда ценность объединения . Тогда если и , тогда утверждается, что можно поменять последовательность ходов и собрать новый элемент состоящий из объединения наборов, который будет иметь большую (строго говоря конечно неменьшую) ценность. Давайте просто напросто посмотрим на последнюю операцию из которой получился первый набор и не будем её делать, получим два каких то элемента. Пусть значения этих элементов и , и . Тогда мы знаем, что . Теперь у нас есть три элемента со значениями . Отсортируем их. Так как , а значит . Теперь соединим элементы с ценностью и , а потом получившийся с элементом со значением . Итого ценность нового элемента составит вместо .

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

Решение на Python:

f = open(’26.txt’)
n = int(f.readline())
a = [int(x) for x in f]
a.sort()
ans = a[0]
for i in range(1, n):
    ans = (ans + a[i]) / 2
print(ans)

 

Во-первых, предположим, что не существует такого , чтобы . В этом случае мы можем доказать, что ответ всегда , где — общее количество креветок.

Доказательство заключается в следующем. Очевидно, что мы не можем сделать больше, чем пары. С другой стороны, мы можем в явном виде построить пары следующим алгоритмом: Пусть — все креветки, отсортированные в порядке неубывания. Тогда для каждого : (в противном случае нет креветки с целым числом , что является противоречием). Таким образом, мы можем построить пары . Таким образом, мы можем сделать пары.

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

На самом деле можно даже не делать сплит по . Достаточно лишь посмотреть при рассмотрении креветок размера , не осталась ли у вас ровно креветка размера . Следовательно, вы можете разделить последовательность , по , и для каждой части вычислить половину (с округлением дробной части в меньшую сторону) суммы, и ответом будет сумма этих чисел. Асимптотика решения .

Решение на C++

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    long long ans = 0;
    ans += a[0] / 2; a[0] -= 2 * ans;
    for(int i = 1; i < n; ++i){
        if(a[i - 1] > 0){
            if(a[i] > 0){
                --a[i];
                ++ans;
            }
        }
        ans += a[i] / 2;
        a[i] -= a[i] / 2 * 2;
    }
    cout << ans << ’\n’;
}

 

Решение на Python

f = open("26.txt")
n = int(f.readline())
a = [int(f.readline()) for _ in range(n)]
ans = 0
for i in range(n - 1):
    if a[i] >= a[i + 1]:
        ans += a[i + 1]
        a[i] -= a[i + 1]
        a[i + 1] = 0
        ans += a[i] // 2
        a[i] = a[i] % 2
    else:
        ans += a[i]
        a[i + 1] -= a[i]
        a[i] = 0
        ans += a[i + 1] // 2
        a[i + 1] = a[i + 1] % 2
print(ans)

Решение 1 ( Excel / LibreOffice):

Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения количества вакантных мест и количества соискателей, где они нам не помешают. Сортируем числа по возрастанию. Выделяем 500 элементов, начиная с первого, числовое значение которого больше 93. Мы получили, что количество вакантных мест больше, чем количество подходящих нам соискателей. Запишем полученное количество подходящих соискателей и элемент, имеющий максимальное числовое значение, в ответ.

Решение 2 (Python):

f = open(’26.txt’)
S, N = map(int, f.readline().split())
a = []
for i in range(N):
    a.append(int(f.readline()))
a.sort(reverse=True)
ans = []
for i in range(S):
    if a[i] > 93:
        ans.append(a[i])
print(len(ans), a[0])

def egyptianFraction(nr, dr):
    print("The Egyptian Fraction " +
          "Representation of {0}/{1} is".
          format(nr, dr), end="\n")

    ef = []

    while nr != 0:
        x = dr // nr + (dr % nr != 0)
        ef.append(x)
        nr = x * nr - dr
        dr = dr * x

    for i in range(len(ef)):
        if i != len(ef) - 1:
            print("1/{0} +".format(ef[i]), end=" ")
        else:
            print("1/{0}".format(ef[i]), end="")

egyptianFraction(15, 23)

f = open(’27b.txt’)
n, begin, end = map(int, f.readline().split())
data = sorted([[int(i) for i in f.readline().split()] for i in range(n)])
diff = 0
maxim = 0
ans = 0
time = 0

# проходим по списку наблюдателей
for i in range(n):
    # если время начала работы наблюдателя меньше или равно времени начала олимпиады
    if data[i][0] <= begin:
        # и если время окончания работы наблюдателя больше времени начала олимпиады
        if data[i][1] > begin:
            # и если разница между временем окончания работы наблюдателя и временем начала олимпиады больше текущей разницы
            if data[i][1] - begin > diff:
                # обновляем разницу и время окончания работы первого наблюдателя
                diff = data[i][1] - begin
                maxim = data[i][1]
    # если время начала работы наблюдателя больше времени начала олимпиады
    else:
        # и если еще не был назначен ни один наблюдатель
        if ans == 0:
            # вычисляем время работы первого наблюдателя
            time = maxim - begin

        # обновляем начало олимпиады, разницу и количество наблюдателей
        begin = maxim
        diff = 0
        ans += 1

        # если олимпиада закончилась, прерываем цикл
        if maxim >= end:
            break

print(ans, time)