f=open('26.txt') K=int(f.readline()) N=int(f.readline()) g=sorted([list(map(int, j.split())) for j in f]) a=[[0,0]]*K mas=[] k=0 for i in range(len(g)): for j in range(len(a)): if g[i][0]>a[j][-1]: a[j]=g[i] k+=1 mas.append(j+1) break print(k, mas[-1])
Как решать задачи на нахождение оптимального результата по типу этой, если бы в условии этой было требование найти максимальное количество? Я так понимаю, что такие задачи решаются динамическим программированием, но не решал пока таких. Есть какие - нибудь обобщающие советы или алгоритмы для подобных задач?
Какой же это затратный по времени алгоритм со всеми этими pop'ами и постоянным полным прохождением списка. У нас же массив отсортирован, почему бы бинарный поиск не использовать? А вместо того, чтобы постоянно удалять элементы, что занимает кучу времени, можно просто менять их значения на 0, например. Когда я сдавал ЕГЭ, в последнем задании были жесткие условия по сложности алгоритма, они уже убрали это или что?
Так я и говорю, что он косой-кривой, и что отсортировано. Но по-барабану. Это не 27, это 26. Там сложность не особо влияет. И в видео не инструкция, типа "смотрите, какой крутой код". В видео как раз "смотрите, какой дерьмовый код я использовал на ЕГЭ")) Там главное было понять задачу.
@@infbu ого, так это не последнее задание. Что-то они перемудрили с этим, раньше задание на программирование делалось в уме за пару минут и чисто механически рукой на бумажку переписывалось, а здесь я даже призадумался.
Так 27 было ерундой на досроке) закрутили предпоследнюю) И сейчас нет бумажки, сейчас нужен ответ. Берутся данные из файла. В 27 файл размером в 30Мб, там неэффективно не прокатит. А в 26 пофиг:) Главное - ответ. Поэтому и такое решение, и поэтому такой подход.
f = open('266.txt') k = int(f.readline()) n = int(f.readline()) s = [] for w in range(0, n): s.append(list(map(int, f.readline().split()))) s = sorted(s) maxx = 0 fl = True for x in range(k): t = [s[0]] s.remove(s[0]) for i in range(len(s)): try: if t[-1][1] < s[i][0]: t.append(s[i]) s.remove(s[i]) except: continue if t[-1][0] == 999: if fl: fl = False maxx = x + 1 print(maxx, n - len(s)) вариант с немного более простым кодом. для начала (как и у вас в видео) считываем все значения в один список. далее проходимся по каждой ячейке через переменную t. далее проходимся по всем элементам списка, используем try и except, чтобы обойти ошибки из-за удаления элементов. проверяем, будет ли время захода багажа больше, чем время окончания прошлого багажа, если да - добавляем в список t, удаляем из s. далее сначала используем переменную maxx и для каждого t записываем строку maxx = max(maxx, t[-1][0]). выводим в конце программы maxx, узнаём чему равно значение захода последнего пассажира. в моей задаче нужно было написать номер минимальной ячейки. поэтому, узнав maxx (он здесь будет равен 999), немного переписываем концовку цикла. проверяем, если t[-1][0] == 999, то записываем в maxx номер нашей ячейки +1, т.к. начинали с нуля. и т.к. нам нужен номер именно первой ячейки, сразу же после найденной ячейки роняем fl и делаем его равным False, чтобы при дальнейших поисках нам ничего не выдавало как-то так)
Почему код не работает? with open('1_26.txt') as f: k = int(f.readline()) n = int(f.readline()) timeline = [0] * 24 * 60 missed_luggage_num = 0 max_missed_luggage = 0 a = list() for i in f: a.append(list(map(int, i.split()))) a.sort() for i in a: for j in range(i[0] - 1, i[1]): if timeline[i[0]] >= k: max_missed_luggage = timeline[i[0] - 1] missed_luggage_num += 1 break else: timeline[j] += 1 print(timeline) print(missed_luggage_num) print(max_missed_luggage)
a = open('26_7626(1).txt').readlines() a = [list(map(int,i.split())) for i in a] a.pop(0) a.pop(0) a.sort() cklad = [0] * 210 g = 0 l = 0 for i in range(1000): for j in range(210): if a[i][0]>cklad[j]: cklad[j] = a[i][1] g+=1 l =j+1 break print(g,l)
Хорошее и КРАСИВОЕ решение. Правда, ошибочное. Не учитывает то, что могут быть варианты пар чисел, больших чем 1440. Тогда число багажей вырастет, да и номер ячейки не останется нужным номером. Одно ветвление (или даже условие в единственное ветвление) добавить и всё точно будет правильно.
Условие задачи оказалось сложнее решения. Все стало понятно .Большое спасибо за разбор
Спасибо за разбор! У АР в онлайне в целом понял, но тут все дошло до кристального понимания
Не додумался до вашего решения, выбрал более сложный путь. Спасибо за разбор, очень интересно)
А есть ваше решение?) Со сложным путём?
@@infbu Пока не писал, но попробую
Спасибо, сама решила чутка по-другому, но Вы подсказали идею.
спасибо за разбор!!
f=open('26.txt')
K=int(f.readline())
N=int(f.readline())
g=sorted([list(map(int, j.split())) for j in f])
a=[[0,0]]*K
mas=[]
k=0
for i in range(len(g)):
for j in range(len(a)):
if g[i][0]>a[j][-1]:
a[j]=g[i]
k+=1
mas.append(j+1)
break
print(k, mas[-1])
Как решать задачи на нахождение оптимального результата по типу этой, если бы в условии этой было требование найти максимальное количество? Я так понимаю, что такие задачи решаются динамическим программированием, но не решал пока таких. Есть какие - нибудь обобщающие советы или алгоритмы для подобных задач?
спасибо большое ❤❤❤
17:00 сортируется по 0 индексу получается?
27:15 что делаем? Карас?
Не совсем понятно про 'mn', к чему оно?
Привет. Когда будет решение обучение решению 26 заданий?
Какой же это затратный по времени алгоритм со всеми этими pop'ами и постоянным полным прохождением списка. У нас же массив отсортирован, почему бы бинарный поиск не использовать? А вместо того, чтобы постоянно удалять элементы, что занимает кучу времени, можно просто менять их значения на 0, например. Когда я сдавал ЕГЭ, в последнем задании были жесткие условия по сложности алгоритма, они уже убрали это или что?
Так я и говорю, что он косой-кривой, и что отсортировано. Но по-барабану. Это не 27, это 26. Там сложность не особо влияет. И в видео не инструкция, типа "смотрите, какой крутой код". В видео как раз "смотрите, какой дерьмовый код я использовал на ЕГЭ")) Там главное было понять задачу.
@@infbu ого, так это не последнее задание. Что-то они перемудрили с этим, раньше задание на программирование делалось в уме за пару минут и чисто механически рукой на бумажку переписывалось, а здесь я даже призадумался.
Так 27 было ерундой на досроке) закрутили предпоследнюю) И сейчас нет бумажки, сейчас нужен ответ. Берутся данные из файла. В 27 файл размером в 30Мб, там неэффективно не прокатит. А в 26 пофиг:) Главное - ответ. Поэтому и такое решение, и поэтому такой подход.
Есть в открытом доступе варианты с досрока?
Пока нет, к концу апреля выложат
@@infbu так уже же есть, вчера ещё посмотрел
@@gggforce официальный ким будет позже. Вчера было то, что собрали те, кто сдавал ЕГЭ.
@@infbu понял, спасибо
хотелось бы попробовать решить в экселе можно пожалуйста файл с заданием ?
Добавил в описание к видео
@@infbu спасибо
Боже, как вы додумались до этого, вы гений....
курс кабанова курит в сторонке
Поздним вечерком перед егэ….., как полагается)
что значит бу?
БУ значит вендетта!
понял, время на 26 можно не тратить
Сложно
Однострочный комментарий на питоне - #
да привычка удалять
f = open('266.txt')
k = int(f.readline())
n = int(f.readline())
s = []
for w in range(0, n):
s.append(list(map(int, f.readline().split())))
s = sorted(s)
maxx = 0
fl = True
for x in range(k):
t = [s[0]]
s.remove(s[0])
for i in range(len(s)):
try:
if t[-1][1] < s[i][0]:
t.append(s[i])
s.remove(s[i])
except:
continue
if t[-1][0] == 999:
if fl:
fl = False
maxx = x + 1
print(maxx, n - len(s))
вариант с немного более простым кодом. для начала (как и у вас в видео) считываем все значения в один список. далее проходимся по каждой ячейке через переменную t. далее проходимся по всем элементам списка, используем try и except, чтобы обойти ошибки из-за удаления элементов. проверяем, будет ли время захода багажа больше, чем время окончания прошлого багажа, если да - добавляем в список t, удаляем из s. далее сначала используем переменную maxx и для каждого t записываем строку maxx = max(maxx, t[-1][0]). выводим в конце программы maxx, узнаём чему равно значение захода последнего пассажира. в моей задаче нужно было написать номер минимальной ячейки. поэтому, узнав maxx (он здесь будет равен 999), немного переписываем концовку цикла. проверяем, если t[-1][0] == 999, то записываем в maxx номер нашей ячейки +1, т.к. начинали с нуля. и т.к. нам нужен номер именно первой ячейки, сразу же после найденной ячейки роняем fl и делаем его равным False, чтобы при дальнейших поисках нам ничего не выдавало
как-то так)
Почему код не работает?
with open('1_26.txt') as f:
k = int(f.readline())
n = int(f.readline())
timeline = [0] * 24 * 60
missed_luggage_num = 0
max_missed_luggage = 0
a = list()
for i in f:
a.append(list(map(int, i.split())))
a.sort()
for i in a:
for j in range(i[0] - 1, i[1]):
if timeline[i[0]] >= k:
max_missed_luggage = timeline[i[0] - 1]
missed_luggage_num += 1
break
else:
timeline[j] += 1
print(timeline)
print(missed_luggage_num)
print(max_missed_luggage)
a = open('26_7626(1).txt').readlines()
a = [list(map(int,i.split())) for i in a]
a.pop(0)
a.pop(0)
a.sort()
cklad = [0] * 210
g = 0
l = 0
for i in range(1000):
for j in range(210):
if a[i][0]>cklad[j]:
cklad[j] = a[i][1]
g+=1
l =j+1
break
print(g,l)
Хорошее и КРАСИВОЕ решение. Правда, ошибочное. Не учитывает то, что могут быть варианты пар чисел, больших чем 1440. Тогда число багажей вырастет, да и номер ячейки не останется нужным номером. Одно ветвление (или даже условие в единственное ветвление) добавить и всё точно будет правильно.