26.04 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Дано число ,
натуральных чисел первого массива и
натуральных чисел второго массива. Оба массива
изначально отсортированы по возрастанию.
Напишите программу, которая выводит отсортированный массив из чисел в виде «1, 2, 3». Используйте два
массива и два указателя.
Ответ запишите для = 5 и чисел 1, 3, 5, 7, 9, 2, 4, 6, 8, 10.
first_array = [0] * n
second_array = [0] * n
result_array = [0] * (2 * n)
for i in range(n):
first_array[i] = int(input())
for i in range(n):
second_array[i] = int(input())
i = 0
j = 0
while i < n and j < n:
if first_array[i] < second_array[j]:
result_array[i + j] = first_array[i]
i += 1
else:
result_array[i + j] = second_array[j]
j += 1
# Сработает только один из while так как один из индексов к этому времени будет равен n
while i < n:
result_array[i + j] = first_array[i]
i += 1
while j < n:
result_array[i + j] = second_array[j]
j += 1
print(*result_array, sep=", ")
Ошибка.
Попробуйте повторить позже
Во многих компьютерных системах текущее время хранится в формате «UNIX-время» – количестве секунд от начала суток 1 января 1970 года. В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1633046400 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.
Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на неделе, начавшейся в момент UNIX-времени 1633305600, и в течение какого суммарного времени (в секундах) выполнялось такое наибольшее количество процессов.
Входные данные
Первая строка входного файла содержит целое число N – общее количество процессов за весь период наблюдения. Каждая из следующих N строк содержит 2 целых числа: время старта и время завершения одного процесса в виде UNIX-времени. Все данные в строках входного файла отделены одним пробелом.
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно на неделе, начиная с момента UNIX-времени 1633305600, затем суммарное количество секунд, в течение которых на этой неделе выполнялось такое максимальное количество процессов.
finish = start + 7 * 24 * 60 * 60
file = open("26_2.txt", "r")
lines = file.readlines()
n = int(lines[0])
# Перебираем каждую стоку кроме первой (в которой N) и берем по одному числу из каждой
start_array = [int(line.split()[0]) for line in lines[1:]]
finish_array = [int(line.split()[1]) for line in lines[1:]]
for i in range(len(finish_array)):
if finish_array[i] == 0:
finish_array[i] = start + 20000000000000000000000000
start_array = sorted(start_array)
finish_array = sorted(finish_array)
i = 0
j = 0
maxim = 0
k = 0
while i < n and j < n:
if start_array[i] < finish_array[j]:
k += 1
if k > maxim and start_array[i] >= start and start_array[i] < finish:
maxim = k
i += 1
else:
k -= 1
j += 1
while j < n:
k -= 1
j += 1
i = 0
j = 0
k = 0
ans_count = 0
for sec in range(start, finish):
while i < len(start_array) and start_array[i] <= sec:
k += 1
i += 1
while j < len(finish_array) and finish_array[j] <= sec:
k -= 1
j += 1
if k == maxim:
ans_count += 1
print(maxim, ans_count)
Ошибка.
Попробуйте повторить позже
Во многих компьютерных системах текущее время хранится в формате «UNIX-время» – количестве секунд от начала суток 1 января 1970 года. В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1632930743 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.
Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на двух неделях, начавшихся в момент UNIX-времени 1632932743, и в течение какого суммарного времени (в секундах) выполнялось такое наибольшее количество процессов.
Входные данные
Первая строка входного файла содержит целое число N – общее количество процессов за весь период наблюдения. Каждая из следующих N строк содержит 2 целых числа: время старта и время завершения одного процесса в виде UNIX-времени. Все данные в строках входного файла отделены одним пробелом.
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно на двух неделях, начиная с момента UNIX-времени 1632932743, затем суммарное количество секунд, в течение которых на этих неделях выполнялось такое максимальное количество процессов.
finish = start + 2 * 7 * 24 * 60 * 60
file = open("26_3.txt", "r")
lines = file.readlines()
n = int(lines[0])
# Перебираем каждую стоку кроме первой (в которой N) и берем по одному числу из каждой
start_array = [int(line.split()[0]) for line in lines[1:]]
finish_array = [int(line.split()[1]) for line in lines[1:]]
for i in range(len(finish_array)):
if finish_array[i] == 0:
finish_array[i] = start + 20000000000000000000000000
start_array = sorted(start_array)
finish_array = sorted(finish_array)
i = 0
j = 0
maxim = 0
k = 0
while i < n and j < n:
if start_array[i] < finish_array[j]:
k += 1
if k > maxim and start_array[i] >= start and start_array[i] < finish:
maxim = k
i += 1
else:
k -= 1
j += 1
while j < n:
k -= 1
j += 1
i = 0
j = 0
k = 0
ans_count = 0
for sec in range(start, finish):
while i < len(start_array) and start_array[i] <= sec:
k += 1
i += 1
while j < len(finish_array) and finish_array[j] <= sec:
k -= 1
j += 1
if k == maxim:
ans_count += 1
print(maxim, ans_count)
Ошибка.
Попробуйте повторить позже
Во многих компьютерных системах текущее время хранится в формате «UNIX-время» – количестве секунд от начала суток 1 января 1970 года. В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1633907387 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.
Вам необходимо определить, какое наименьшее количество процессов выполнялось в системе одновременно на двух неделях, начавшихся в момент UNIX-времени 1633947387, и в течение какого суммарного времени (в секундах) выполнялось такое наименьшее количество процессов.
Входные данные
Первая строка входного файла содержит целое число N – общее количество процессов за весь период наблюдения. Каждая из следующих N строк содержит 2 целых числа: время старта и время завершения одного процесса в виде UNIX-времени. Все данные в строках входного файла отделены одним пробелом.
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала наименьшее количество процессов, которые выполнялись одновременно на двух неделях, начиная с момента UNIX-времени 1633947387, затем суммарное количество секунд, в течение которых на этих неделях выполнялось такое наименьшее количество процессов.
finish = start + 2 * 7 * 24 * 60 * 60
file = open("26_4.txt", "r")
lines = file.readlines()
n = int(lines[0])
# Перебираем каждую стоку кроме первой (в которой N) и берем по одному числу из каждой
start_array = [int(line.split()[0]) for line in lines[1:]]
finish_array = [int(line.split()[1]) for line in lines[1:]]
for i in range(len(finish_array)):
if finish_array[i] == 0:
finish_array[i] = start + 20000000000000000000000000
start_array = sorted(start_array)
finish_array = sorted(finish_array)
i = 0
j = 0
minim = 10000000000000000000000000
k = 0
while i < n and j < n:
if start_array[i] <= finish_array[j]:
if k < minim and start_array[i] > start and start_array[i] < finish:
minim = k
k += 1
i += 1
else:
k -= 1
if k < minim and finish_array[j] >= start and finish_array[j] < finish:
minim = k
j += 1
while j < n:
k -= 1
if k < minim and finish_array[j] >= start and finish_array[j] < finish:
minim = k
j += 1
i = 0
j = 0
k = 0
ans_count = 0
for sec in range(start, finish):
while i < len(start_array) and start_array[i] <= sec:
k += 1
i += 1
while j < len(finish_array) and finish_array[j] <= sec:
k -= 1
j += 1
if k == minim:
ans_count += 1
print(minim, ans_count)
Ошибка.
Попробуйте повторить позже
Во многих компьютерных системах текущее время хранится в формате «UNIX-время» – количестве секунд от начала суток 1 января 1970 года. В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1633463028 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.
Вам необходимо определить, какое наименьшее количество процессов выполнялось в системе одновременно на двух неделях, начавшихся в момент UNIX-времени 1633483028, и в течение какого максимального времени (в секундах) выполнялось такое наименьшее количество процессов без изменения их количества.
Входные данные
Первая строка входного файла содержит целое число N – общее количество процессов за весь период наблюдения. Каждая из следующих N строк содержит 2 целых числа: время старта и время завершения одного процесса в виде UNIX-времени. Все данные в строках входного файла отделены одним пробелом.
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала наименьшее количество процессов, которые выполнялись одновременно на двух неделях, начиная с момента UNIX-времени 1633483028, затем максимальное количество подряд идущих секунд, в течение которых на этих неделях выполнялось такое наименьшее количество процессов.
finish = start + 2 * 7 * 24 * 60 * 60
file = open("26_5.txt", "r")
lines = file.readlines()
n = int(lines[0])
# Перебираем каждую стоку кроме первой (в которой N) и берем по одному числу из каждой
start_array = [int(line.split()[0]) for line in lines[1:]]
finish_array = [int(line.split()[1]) for line in lines[1:]]
for i in range(len(finish_array)):
if finish_array[i] == 0:
finish_array[i] = start + 20000000000000000000000000
start_array = sorted(start_array)
finish_array = sorted(finish_array)
i = 0
j = 0
minim = 10000000000000000000000000
k = 0
while i < n and j < n:
if start_array[i] <= finish_array[j]:
if k < minim and start_array[i] > start and start_array[i] < finish:
minim = k
k += 1
i += 1
else:
k -= 1
if k < minim and finish_array[j] >= start and finish_array[j] < finish:
minim = k
j += 1
while j < n:
k -= 1
if k < minim and finish_array[j] >= start and finish_array[j] < finish:
minim = k
j += 1
i = 0
j = 0
k = 0
ans_count = 0
curr_count = 0
for sec in range(start, finish):
while i < len(start_array) and start_array[i] <= sec:
k += 1
i += 1
while j < len(finish_array) and finish_array[j] <= sec:
k -= 1
j += 1
if k == minim:
curr_count += 1
else:
ans_count = max(ans_count, curr_count)
curr_count = 0
print(minim, ans_count)
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих Гарантируется, что все числа различны.
Необходимо определить, сколько в наборе таких пар чисел, что числа в паре имеют разную чётность, а их сумма тоже
присутствует в файле, и чему равна наименьшая из сумм таких пар.
Входные данные.
Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. В ответе запишите два целых числа: сначала количество пар, затем наименьшую сумму.
Под парой подразумевается любые два различные элемента последовательности.
Пример входных данных:
6
4
8
13
19
23
21
В данном случае есть две подходящие пары: 8 и 13 (сумма 21), 4 и 19 (сумма 23).
В ответе надо записать числа 2 и 21.
f = open(’Задание_26__k3bw.txt’) n = int(f.readline()) a = [] odd = [] even = [] for i in range(n): a.append(int(f.readline())) if a[i] % 2 == 0: even.append(a[i]) else: odd.append(a[i]) b = set(a) counter = 0 minim = 100000000000 for x in odd: for y in even: if x+y in b: counter += 1 minim = min(x+y, minim) print(counter, minim)
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
Компания по разработке игр открыла набор на работу в офис. На просторах сайта (сайт не уточняется) расположены
резюме по поиску работы в сфере разработки игр. Среди них HR-менеджер Петров Влад обязан отобрать только
высококвалифицированных и продуктивных программистов, которые смогут справиться со всеми задачами в их компании.
При отборе Влад смотрит на КПД (сводка по образованию, опыту работы в данной сфере, качество портфолио). КПД
должен составлять более %. Известен КПД каждого соискателя.
По заданной информации о КПД соискателя и о количестве вакантных мест в компании определите
максимальное количество потенциальных работников, КПД которых выше %, а также максимальное КПД
работника, найденного в таблице при условии, что найдено максимальное количество высококвалифицированных
программистов.
Входные данные
В первой строке входного файла находятся два числа: — количество вакантных мест (натуральное число, не
превышающее
) и
— количество соискателей (натуральное число, не превышающее
). В следующих
строках находятся значения о КПД каждого соискателя (все числа натуральные, удовлетворяющие условию:
), каждое в отдельной строке
Выходные данные
Запишите в ответе два числа: сначала максимальное количество потенциальных работников, КПД которых выше %,
а также максимальное КПД работника, найденного в таблице при условии, что найдено максимальное количество
высококвалифицированных программистов.
Пример входного файла:
При таких исходных данных можно заполнить только вакантных места. Эти люди со следующим КПД:
,
,
,
. А максимальное КПД соискателя равно
%. Таким образом, ответ для вышеприведенного примера будет:
.
Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения количества вакантных мест и количества соискателей, где они нам не помешают. Сортируем
числа по возрастанию. Выделяем 500 элементов, начиная с первого, числовое значение которого больше 79. Мы
получили, что количество вакантных мест больше, чем количество подходящих нам соискателей. Запишем
полученное количество подходящих соискателей и элемент, имеющий максимальное числовое значение, в ответ.
Решение 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] > 79: ans.append(a[i]) print(len(ans), a[0])
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих Необходимо определить, сколько в наборе
таких пар нечётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наименьшее из
средних арифметических таких пар.
Входные данные:
Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.
Пример входных данных:
6
16
3
21
12
9
6
В данном случае есть две подходящие пары: 3 и 21 (среднее арифметическое 12), 3 и 9 (среднее арифметическое 6). В ответе надо записать числа 2 и 6.
В ответе через пробел запишите два целых числа: сначала количество пар, затем наименьшее среднее арифметическое.
Менее эффективное решение через бин. поиск
def bin_search(a, x): n = len(a) left = -1 right = n while right - left > 1: middle = (left + right) // 2 if a[middle] >= x: right = middle else: left = middle if right != n and a[right] == x: return True else: return False f = open(’1.txt’) n = int(f.readline()) a = [] b = set() for i in range(n): x = int(f.readline()) if x % 2 != 0: a.append(x) b.add(x) b = sorted(list(b)) k = 0 q = 0 minim = 1000000000000000 for i in range(len(a)): q += 1 for j in range(i + 1, len(a)): t = (a[i] + a[j]) // 2 if bin_search(b, t): k += 1 if t < minim: minim = t if q % 100 == 0: print(q) print(k, minim)
Эффективное решение через проход по множеству (поиск в среднем происходит за 1 операцию).
f = open(’Задание_26.txt’) n = int(f.readline()) a = [] b = set() for i in range(n): x = int(f.readline()) if x % 2 != 0: a.append(x) b.add(x) k = 0 minim = 1000000000000000 for i in range(len(a)): for j in range(i + 1, len(a)): t = (a[i] + a[j]) // 2 if t in b: k += 1 if t < minim: minim = t print(k, minim)
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих Гарантируется, что все числа различны.
Необходимо определить, сколько в наборе таких пар чисел, что числа в паре имеют разную чётность, а их сумма тоже
присутствует в файле, и чему равна наименьшая из сумм таких пар.
Входные данные.
Первая строка входного файла содержит целое число — общее количество чисел в наборе. Каждая из следующих
строк содержит одно число. В ответе запишите два целых числа: сначала количество пар, затем наименьшую
сумму.
Под парой подразумевается любые два различные элемента последовательности.
Пример входных данных:
В данном случае есть две подходящие пары: и
(сумма
),
и
(сумма
).
В ответе надо записать числа и
.
Неэффективное решение (в рамках этого задания), через бин. поиск
def bin_search(a, x): n = len(a) left = -1 right = n while right - left > 1: middle = (left + right) // 2 if a[middle] >= x: right = middle else: left = middle if right != n and a[right] == x: return True else: return False f = open(’1.txt’) n = int(f.readline()) a, odd, even = [], [], [] counter = 0 min_summ = 10 ** 10 for i in range(n): x = int(f.readline()) if x % 2 == 0: even.append(x) else: odd.append(x) a.append(x) a = sorted(list(set(a))) # Уменьшаем количество элементов до уникальных for i in odd: for j in even: if bin_search(a, i + j): counter += 1 min_summ = min(min_summ, i + j) print(counter, min_summ)
Эффективное решение через проход по множеству (поиск в среднем происходит за 1 операцию).
f = open(’task 5.txt’) n = int(f.readline()) a, odd, even = [], [], [] counter = 0 min_summ = 10 ** 10 for i in range(n): x = int(f.readline()) if x % 2 == 0: even.append(x) else: odd.append(x) a.append(x) a = set(a) # Перебор (in) идет за O(n) for i in odd: for j in even: if (i + j) in a: counter += 1 min_summ = min(min_summ, i + j) print(counter, min_summ)
Ошибка.
Попробуйте повторить позже
Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и кусков оптоволокна, из
которых попросили получить цельные куски по
метров. С целью снижения затухания сигнала в полученном кабеле
нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько всего
сварок будет в цельных кусках и сколько останется кусков, из которых не варить цельный кусок требуемой
длины. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался
исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего
использования.
Входные данные:
В первой строке входного файла записаны значения (количество кусков оптоволокна) и
(длина
необходимого цельного куска). Каждая из следующих
строк содержит одно целое число — длину очередного
куска.
Выходные данные:
Два числа: количество сварок в цельных кусках и количество кусков, из которых не сварить цельный кусок требуемой длины.
Пример входного файла:
Сперва взяли и
, обрез
обратно в кучу
— одна сварка. Затем взяли
,
и
, обрез длиной
обратно в кучу
— две сварки. И затем взяли
,
,
и
, ровно
, без обреза — три сварки. Итого:
сварок и
оставшихся куска оптоволокна. Ответ:
file = open("Задание_26__ra53.txt") n, m = [int(i) for i in file.readline().split()] a = [int(file.readline()) for j in range(n)] for i in range(100): a.append(0) a.sort(reverse=True) svarki = 0 while a[0] > 0: s = 0 i = 0 while s < m: if i >= len(a): print(svarki, len(a) - a.count(0)) exit() s = s + a[i] i += 1 for j in range(i - 1): a[j] = 0 last = a[i - 1] svarki += i - 1 last_ind = i - 1 s -= last while i < len(a): if s + a[i] >= m: last = a[i] last_ind = i i += 1 a[last_ind] = s + last - m a.sort(reverse=True)
Ошибка.
Попробуйте повторить позже
Во многих компьютерных системах текущее время хранится в формате «UNIX-время» –— количестве секунд от начала
суток января
года.
В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента
UNIX-времени фиксировали и заносили в базу данных моменты старта и финиша всех процессов,
действовавших в этой системе.
Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на неделе,
начавшейся в момент UNIX-времени , и в течение какого суммарного времени (в секундах) выполнялось такое
наибольшее количество процессов.
Входные и выходные данные:
Первая строка входного файла 6.txt содержит целое число N –— общее количество процессов за весь период
наблюдения. Каждая из следующих N строк содержит целых числа: время старта и время завершения одного процесса в
виде UNIX-времени. Все данные в строках входного файла отделены одним пробелом.
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно
на неделе, начиная с момента UNIX-времени , затем суммарное количество секунд, в течение которых на этих
неделях выполнялось такое максимальное количество процессов.
Решение 1
f = open(r"C:\\Users\\Тимофей\Desktop\\n3.txt") start_week = 1_634_515_200 finish_week = start_week + 7 * 24 * 60 * 60 start_month = 1_633_046_400 finish_month = start_month + 31 * 24 * 60 * 60 n = int(f.readline()) st, fn = [], [] # st - массив стартов, fn - массив финишей k, maxim = 0, 0 # k - число сейчас активных процессов, maxim - максимальное число активных процессов на неделе for i in range(n): a, b = map(int, f.readline().split()) # a, b - время начала и конца i-го процесса if a == 0: # Если процесс начался до исследования a = start_month st.append(a) if b == 0: # Если процесс кончился после исследования b = finish_month fn.append(b) st.sort() fn.sort() # 2 указателя: i - для стартов, j - для финишей i, j = 0, 0 while i < len(st): if st[i] < fn[j]: k += 1 # if для случая, когда ни один процесс не начинается на неделе if (i < len(st) - 1) and st[i] < start_week and st[i + 1] > finish_week: maxim = max(maxim, k) if k > maxim and st[i] >= start_week and st[i] < finish_week: maxim = k i += 1 else: k -= 1 j += 1 i, j = 0, 0 k, ans = 0, 0 for sec in range(start_month, finish_month): # считаем число начатых и кончившихся процессов в каждую секунду sec while i < len(st) and st[i] == sec: k += 1 i += 1 while j < len(fn) and fn[j] == sec: k -= 1 j += 1 if k == maxim: ans += 1 # промежуток [sec; sec + 1) print(maxim, ans)
Решение 2
f = open(r"C:\\Users\\Тимофей\Desktop\\n3.txt") n = int(f.readline()) start_month = 1_633_046_400 finish_month = start_month + 31 * 24 * 60 * 60 start_week = 1_634_515_200 finish_week = start_week + 7 * 24 * 60 * 60 k = 0 borders = [] for sec in range(n): x, y = map(int, f.readline().split()) if x == 0: x = start_month if y == 0: y = finish_month borders.append([x, 1]) borders.append([y, -1]) borders.append([start_week + 1, 0]) borders.sort() maxim = -1000000000000 time = sorted(set(x[0] for x in borders)) t = 0 ans = 0 for sec in time: while t < len(borders) and borders[t][0] == sec: k += borders[t][1] t += 1 if k > maxim and sec >= start_week and sec < finish_week: maxim = k if sec > finish_week: break t = 0 k = 0 for sec in range(start_month, finish_month): while t < len(borders) and borders[t][0] == sec: k += borders[t][1] t += 1 if k == maxim: ans += 1 print(maxim, ans)
Ошибка.
Попробуйте повторить позже
Для уменьшения аварий на центральной дороге в городе X дорожная служба решила выровнять ямы. Размер объем (в литрах) новой ямы вычисляется как наименьшее значение среди объёмов самой этой ямы и двух соседних перед выравниванием. При этом размеры первой и последней ямы решили не менять.
Ночью перед ремонтом дороги в городе X прошел проливной дождь, поэтому все ямы до краев заполнены водой. Сколько литров воды выльется обратно на дорогу после проведения ремонта?
Входные данные.
В первой строке входного файла 8.txt находится число – количество ям на дороге (натуральное число, не
превышающее
). В следующих
строках находятся значения объемов ям (все числа натуральные, не
превышающие
), каждое в отдельной строке.
Запишите в ответе два числа: количество ям с наименьшим объемом и общий объем воды, вылившейся из ям обратно на дорогу.
Пример входного файла:
При таких исходных данных после ремонта объем ям будет выглядеть следующим образом ,
,
,
,
,
,
,
. В ответе необходимо указать два числа –
и
.
file = open("8.txt") n = int(file.readline()) a = [int(file.readline()) for _ in range(n)] a_new = [] for i in range(1, len(a) - 1): a_new.append(min(a[i - 1], a[i], a[i + 1])) a = a[1:len(a) - 1] print(a_new.count(min(a_new)), sum(a) - sum(a_new))
Ошибка.
Попробуйте повторить позже
Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и кусков оптоволокна, из
которых попросили получить цельные куски по
метров. С целью снижения затухания сигнала в полученном кабеле
нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько цельных кусков
получится и какова длина оставшейся части. Ваня выбирал куски строго по уменьшению длины, за исключением
последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для
следующего использования.
Входные данные
В первой строке входного файла записаны значения (количество кусков оптоволокна) и
(длина
необходимого цельного куска). Каждая из следующих
строк содержит одно целое число – длину очередного
куска.
Выходные данные
Два числа: количество сварок в цельных кусках и количество кусков, из которых не сварить цельный кусок требуемой длины.
Пример входного файла:
Сперва взяли и
, обрез
обратно в кучу
– один кусок и 1 сварка. Затем взяли
,
и
, обрез длиной
обратно в кучу
– еще один цельный кусок и 2 сварки. И затем взяли
,
,
и
, ровно
, без обреза – еще кусок и 3 сварки. Осталось
Итого:
сварок и
- количество оставшихся кусков,
из которых не сварить цельный кусок нужной длины.
f = open(r"C:\\Users\\Тимофей\Desktop\\n2.txt") n, dl = map(int, f.readline().split()) a = [int(x) for x in f.readlines()] a.sort(reverse=True) kolvo_svarok = 0 k = 0 while sum(a) >= dl: s = 0 # собираем максимальные куски, кроме последнего while s + a[0] < dl: s += a[0] a.pop(0) kolvo_svarok += 1 kolvo_svarok -= 1 # первый элемент мы не привариваем, а просто "берем в руки" # начинаем искать кусок, который дает минимальный обрезок ind = 0 while ind < len(a) and s + a[ind] >= dl: ind += 1 ind -= 1 # уменьшаем на один, потому что после while ind указывал на # предмаксимальный элемент, который можно добавить if s + a[ind] > dl: a.append(s + a[ind] - dl) # добавляем обрезок kolvo_svarok += 1 a.pop(ind) k += 1 a.sort(reverse=True) # в массиве a остались только куски, из которых не собрать цельный кусок (т.к. sum(a) < dl) print(kolvo_svarok, len(a))
Ошибка.
Попробуйте повторить позже
У Креветкоеда большая коллекция креветок разных размеров. Каждая креветка имеет размер равный целому числу от
до
(не более
) включительно. У него есть
(каждое не более
) креветок размера
. Две креветки
могут образовать пару, если абсолютное значение разности их размеров составляет не более
. Креветкоед
хочет создать максимальное количество пар из своих креветок при условии, что ни одна креветка не должна
использоваться в нескольких парах. Найдите максимальное количество пар, которые он может создать и
съесть.
В первой строке файла вам дано число
, а в следующих
строках того же файла
целых чисел
Во-первых, предположим, что не существует такого , чтобы
. В этом случае мы можем доказать, что ответ всегда
, где
— общее количество креветок.
Доказательство заключается в следующем. Очевидно, что мы не можем сделать больше, чем пары. С другой
стороны, мы можем в явном виде построить
пары следующим алгоритмом: Пусть
— все креветки,
отсортированные в порядке неубывания. Тогда для каждого
:
(в противном случае нет креветки с целым
числом
, что является противоречием). Таким образом, мы можем построить
пары
.
Таким образом, мы можем сделать
пары.
Когда для некоторого
, вы не можете использовать карты с целым числом
, поэтому вы можете разделить
последовательность на
, и для каждой части вы можете решить задачу независимо (ответ — сумма этих независимых
задач).
На самом деле можно даже не делать сплит по . Достаточно лишь посмотреть при рассмотрении креветок размера
,
не осталась ли у вас ровно
креветка размера
. Следовательно, вы можете разделить последовательность
, по
, и для каждой части вычислить половину (с округлением дробной части в меньшую сторону) суммы, и ответом будет
сумма этих чисел. Асимптотика решения
.
Решение на 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
def solve_python(n, a): ans = 0 for i in range(n - 1): ans += a[i] // 2 if a[i] % 2 and a[i + 1] != 0: ans += 1 a[i + 1] -= 1 ans += a[n - 1] // 2 return ans f = open(’26.txt’) n = int(f.readline()) a = [int(i) for i in f] print(solve_python(n, a))
Ошибка.
Попробуйте повторить позже
У вас есть кастрюля и (не более
) ингредиентов. Каждый ингредиент имеет параметр вещественного числа,
называемый значением, а значение
-го ингредиента
равно
(каждое не более
). Когда вы положите
в кастрюлю два ингредиента, они исчезнут и в результате образуется новый ингредиент. Значение нового ингредиента
будет равно
, где
и
- значения потребленных ингредиентов, и вы можете снова положить этот ингредиент в
кастрюлю. После того, как вы составите ингредиенты таким образом
раз, у вас получится один ингредиент. В
ответе запишите максимально возможную ценность этого ингредиента с точностью до сотых. В первой строке
файла
находится одно число
. В следующих
строках файла находится массив целых чисел
длины
(длина массива это есть количество содержащихся в нем элементов) по одному элементу в
строке.
Для получения ответа работает следующий жадный алгоритм: давайте делать каждый следующий новый
ингредиент из двух наименьших по значению ингредиентов. Проделаем эту операцию раз и получим
ответ
Почему это работает? Рассмотрим ситуацию, в которой мы кладем два ингредиента, которые образовались
из двух различных наборов ингредиентов: и
со значениями
и
соответственно, и для определенности
. Тогда ценность объединения
. Тогда если
и
,
тогда утверждается, что можно поменять последовательность ходов и собрать новый элемент состоящий из
объединения наборов, который будет иметь большую (строго говоря конечно неменьшую) ценность. Давайте
просто напросто посмотрим на последнюю операцию из которой получился первый набор
и не будем
её делать, получим два каких то элемента. Пусть значения этих элементов
и
, и
. Тогда мы
знаем, что
. Теперь у нас есть три элемента со значениями
. Отсортируем их. Так как
, а
значит
. Теперь соединим элементы с ценностью
и
, а потом
получившийся с элементом со значением
. Итого ценность нового элемента составит
вместо
.
Очевидно, что разница в значениях есть . Руководствуясь такой логикой можем получить, что каждый ход, это
соединение унарного(то есть данного изначально по условию) ингредиента и того, который собран из множества
ингредиентов. Тогда чем позже изначальный элемент был смешан, тем на меньшую степень
будет поделена его
ценность, поэтому чем больше ценность элемента тем позже его следует добавлять
Решение на 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)
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих Гарантируется, что все числа различны.
Необходимо определить, сколько в наборе таких пар чисел, что их сумма тоже присутствует в файле, и чему равна
наибольшая из сумм таких пар.
Входные данные.
Первая строка входного файла содержит целое число — общее количество чисел в наборе. Каждая из следующих
строк содержит одно число. В ответе запишите два целых числа: сначала количество пар, затем наибольшую
сумму.
Под парой подразумевается любые два различные элемента последовательности.
Пример входных данных:
В данном случае есть одна подходящая пара: и
(сумма
).
В ответе надо записать числа и
.
Решение через бин. поиск
def bin_search(a, x): n = len(a) left = -1 right = n while right - left > 1: middle = (left + right) // 2 if a[middle] >= x: right = middle else: left = middle if right != n and a[right] == x: return True else: return False f = open(’1.txt’) n = int(f.readline()) a = [] counter = 0 max_summ = 0 for i in range(n): a.append(int(f.readline())) a = sorted(a) for i in range(len(a)): for j in range(i+1, len(a)): if bin_search(a, a[i] + a[j]): counter += 1 max_summ = max(max_summ, a[i] + a[j]) print(counter, max_summ)
Решение через поиск по множеству
f = open(’1.txt’) n = int(f.readline()) a = [] counter = 0 max_summ = 0 for i in range(n): a.append(int(f.readline())) for i in range(len(a)): for j in range(i+1, len(a)): if (a[i] + a[j]) in a: counter += 1 max_summ = max(max_summ, a[i] + a[j]) print(counter, max_summ)
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих Гарантируется, что все числа различны.
Необходимо определить, сколько в наборе таких пар чисел, где оба числа являются полными квадратами, их сумма тоже
присутствует в файле, и чему равна наибольшая из сумм таких пар.
Входные данные.
Первая строка входного файла содержит целое число — общее количество чисел в наборе. Каждая из следующих
строк содержит одно число. В ответе запишите два целых числа: сначала количество пар, затем наибольшую
сумму.
Под парой подразумевается любые два различные элемента последовательности.
Пример входных данных:
В данном случае есть одна подходящая пара: и
(сумма
).
В ответе надо записать числа и
.
Решение через бин. поиск
def bin_search(a, x): n = len(a) left = -1 right = n while right - left > 1: middle = (left + right) // 2 if a[middle] >= x: right = middle else: left = middle if right != n and a[right] == x: return True else: return False f = open(’1.txt’) n = int(f.readline()) a = [] counter = 0 max_summ = 0 for i in range(n): a.append(int(f.readline())) a = sorted(list(set(a))) # Уменьшаем количество элементов до уникальных for i in range(len(a)): for j in range(i+1, len(a)): if a[i] ** 0.5 == int(a[i] ** 0.5) and a[j] ** 0.5 == int(a[j] ** 0.5): if bin_search(a, a[i] + a[j]): counter += 1 max_summ = max(max_summ, a[i] + a[j]) print(counter, max_summ)
Решение через поиск по множеству
f = open(’1.txt’) n = int(f.readline()) a = [] counter = 0 max_summ = 0 for i in range(n): a.append(int(f.readline())) b = set(a) # Уменьшаем количество элементов до уникальных for i in range(len(a)): for j in range(i+1, len(a)): if a[i]**0.5 == int(a[i]**0.5) and a[j]**0.5 == int(a[j]**0.5): if (a[i] + a[j]) in b: counter += 1 max_summ = max(max_summ, a[i] + a[j]) print(counter, max_summ)
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
В текстовом файле записан набор натуральных чисел, не превышающих Гарантируется, что все числа различны.
Необходимо определить, сколько в наборе таких пар чисел, где сумма их квадратов присутствует в файле и также является
полным квадратом, и чему равна наименьшая из сумм квадратов таких пар.
Входные данные.
Первая строка входного файла содержит целое число — общее количество чисел в наборе. Каждая из следующих
строк содержит одно число. В ответе запишите два целых числа: сначала количество пар, затем наименьшую
сумму.
Под парой подразумевается любые два различные элемента последовательности.
Пример входных данных:
В данном случае есть одна подходящая пара: и
(сумма квадратов
).
В ответе надо записать числа и
.
Решение через бин. поиск
def bin_search(a, x): n = len(a) left = -1 right = n while right - left > 1: middle = (left + right) // 2 if a[middle] >= x: right = middle else: left = middle if right != n and a[right] == x: return True else: return False f = open(’1.txt’) n = int(f.readline()) a = [] counter = 0 min_summ = 10**12 for i in range(n): a.append(int(f.readline())) a = sorted(list(set(a))) # Уменьшаем количество элементов до уникальных for i in range(len(a)): for j in range(i+1, len(a)): if (a[i]**2 + a[j]**2)**0.5 == int((a[i]**2 + a[j]**2)**0.5): if bin_search(a, a[i]**2 + a[j]**2): counter += 1 min_summ = min(min_summ, a[i]**2 + a[j]**2) print(counter, min_summ)
Решение через поиск по множеству
f = open(’1.txt’) n = int(f.readline()) a = [] counter = 0 min_summ = 10**12 for i in range(n): a.append(int(f.readline())) b = set(a) # Уменьшаем количество элементов до уникальных for i in range(len(a)): for j in range(i+1, len(a)): if (a[i]**2 + a[j]**2)**0.5 == int((a[i]**2 + a[j]**2)**0.5): if (a[i]**2 + a[j]**2) in b: counter += 1 min_summ = min(min_summ, (a[i]**2 + a[j]**2)) print(counter, min_summ)
Ошибка.
Попробуйте повторить позже
Дано число , затем
строк. В каждой из строк находится одна десятичная цифра. Составьте наибольшее и
наименьшее число из всех этих цифр. В ответе укажите остаток разности наибольшего и наименьшего из этих чисел при
делении на
.
f = open(’26.txt’) n = int(f.readline()) a = [] for i in range(n): a.append(int(f.readline())) a = sorted(a) maxim = ’’ minim = ’’ for i in range(n): minim += str(a[i]) maxim += str(a[n - 1 - i]) print((int(maxim) - int(minim)) % 10000)
Ошибка.
Попробуйте повторить позже
Для уменьшения аварий на центральной дороге в городе X дорожная служба решила выровнять ямы. Размер объем (в литрах) новой ямы вычисляется как наименьшее значение среди объёмов самой этой ямы и двух соседних перед выравниванием. При этом размеры первой и последней ямы решили не менять.
Ночью перед ремонтом дороги в городе X прошел проливной дождь, поэтому все ямы до краев заполнены водой. Сколько литров воды выльется обратно на дорогу после проведения ремонта?
Входные данные.
В первой строке входного файла находится число – количество ям на дороге (натуральное число, не превышающее
). В следующих
строках находятся значения объемов ям (все числа натуральные, не превышающие
),
каждое в отдельной строке.
Запишите в ответе два числа: количество ям с наименьшим объемом и общий объем воды, вылившейся из ям обратно на дорогу.
Пример входного файла:
При таких исходных данных после ремонта объем ям будет выглядеть следующим образом ,
,
,
,
,
,
,
. В ответе необходимо указать два числа –
и
.
file = open("26.txt") n = int(file.readline()) a = [int(file.readline()) for _ in range(n)] a_new = [] for i in range(1, len(a) - 1): a_new.append(min(a[i - 1], a[i], a[i + 1])) a = a[1:len(a) - 1] print(a_new.count(min(a_new)), sum(a) - sum(a_new))