Форум » Массивы, сортировка, работа с файлами » №4213 (26.58) общее решение, обсуждение, ошибки в алгоритме и пробелы в условиях » Ответить
№4213 (26.58) общее решение, обсуждение, ошибки в алгоритме и пробелы в условиях
beep: Здравствуйте! Есть те, кто решил задачу в общем виде? В предложенном решении не учитывается, что по определенной цене может быть всего 1 товар, алгоритм рассчитан только на то, что товаров по одной цене хотя бы 2 штуки. Алгоритм на поиск максимальной цены максимально прост: берется последняя учтенная цена и считается, что по ней куплено минимум 2 товара, хотя по условиям задачи там может оказаться всего 1 товар. Более того, никак не проверяется, а можно ли вообще за счет товаров с максимальной ценой попытаться увеличить итоговую максимальную цену, потому что может получиться так, что на последнем шаге мы и купили максимальное количество товаров по одной цене, тогда, если мы заберем оттуда 2 товара, то максимальное количество товаров по одной цене уменьшится, а алгоритм этого не учитывает, и тут мы попадаем в пробелы в условии: неясно, что лучше, случай, где товаров по одной цене больше, или случай, где максимальная цена за товар выше. Ну и конечно же не учитывается, что товаров по большей цене может быть снова 1, тогда нужно купить всего 1 товар, а не 2, чтобы увеличить итоговую максимальную цену за товар. Я написал общее решение, исходя из того, что мы сохраняем максимальное количество одного товара и при этом пытаемся увеличить максимальную итоговую цену за один товар, но оно получилось громоздким, как мне кажется. Есть тут те, кто тоже заинтересовался задачей и общим решением и хочет пообсуждать решение? Ответ сходится, потому что максимальное количество товаров, купленных по одной цене, лежит намного ниже, чем последняя стоимость, по которой получится хоть что-нибудь купить и потому что нет таких цен, по которым был доступен только 1 товар. Еще в алгоритме не совсем правильно считается максимальное количество товаров, которое можно купить. Например, если на предпоследнем шаге мы выкупили все доступные товары, а на последнем оказалось, что нам хватает только на 1 < x < 2 товаров, то можно, если мы купили на предыдущем шаге больше 2 товаров, отнять один товар и тогда может получиться так, что мы сможем купить на последнем шаге 2 товара и итоговое количество товаров будет на 1 больше. Или же на последнем шаге доступен всего 1 товар, и если на предыдущем шаге мы выкупили весь доступный товар, то остатков бюджета может хватить на 1 товар. Решение же работает только для случая, когда на предпоследнем шаге не получается выкупить весь доступный товар, и тогда понятно, что по большей цене не получится купить ни одной штуки нового товара. Но в условиях нигде не оговорено, что именно так и должно быть.
Ответов - 10
beep: Еще раз постараюсь более кратко сформулировать суть проблем: Даже если убрать проблему где по определенной цене доступен только 1 товар, то: 1) алгоритм не учитывает случай, когда на последнем шаге бюджета хватает на 1 < x < 2 товаров, а на предпоследнем шаге куплено более 2 товаров и цена за 1 такой товар покрывает нехватку средств, чтобы купить 2 товара на последнем шаге (тогда итоговое количество товаров будет на 1 больше (-1 с прошлого шага и +2 с последнего)); 2) алгоритм не учитывает случай, когда максимальное количество товаров по одной цене куплено на последнем шаге, тогда при поиске новой максимальной цены уменьшится максимальное количество товаров по одной цене; 3) не ясно, какой случай лучше при одинаковом количестве всего купленных товаров: где максимальная цена за товар выше или где число товаров, купленных по одной цене, больше. Если появляются позиции "1 товар по определенной цене", то все становится еще сложнее.
beep: Может быть еще такой случай и он тоже не учтен алгоритмом, в предложенном решении. Например, вот список товаров по принципу "цена : доступное количество": 30 : 2 31 : 3 32 : 2 33 : 100 34 : 5 А наш бюджет равен 30*2 + 31*3 + 32*2 + 33*10 + 30. Тогда за счет предыдущих товаров мы можем увеличить максимальное количество товаров, купленных по одной цене (1*2 + 2*3 + 3*2 = 14, итого 17 товаров по 33 и остается 30 - 14 = 16 единиц бюджета) или же мы можем увеличить максимальную цену за товар, купив 2 товара по 34, но при этом уменьшим максимальное количество товаров, купленных по одной цене. Из условия нет однозначного ответа, какой случай в приоритете (об этом уже было сказано в 3 пункте), но главное, что предложенный алгоритм в решении не учитывает, такой случай, где за счет предыдущих покупок может быть увеличено количество максимальных товаров, купленных по одной цене.
beep: Раз никому не интересно, выложу свои соображения, вдруг когда-нибудь кто-нибудь заинтересуется этой задачей и ему это поможет. Поскольку условия заданы неоднозначно, будем считать, что в приоритете у нас при максимально возможном количестве купленных товаров купить максимальное количество товаров по одной цене и уже потом попытаться купить товар за максимально возможную цену при сложившихся обстоятельствах. Задача делится на 3 подзадачи: 1) найти максимальное количество товаров, которые можно купить на заданный бюджет; 2) найти максимальное количество товаров, которые можно купить по одной цене (при найденном общем максимальном количестве товаров); 3) найти максимальную цену товара, который можно купить после выполнения первых двух подзадач. Для начала определимся с терминами. Доступные к продаже товары мы представим в виде объекта data, где ключами будут цены товара, а значениями – количество товара, доступного к продаже по соответствующей цене. Если взять все ключи такого объекта и отсортировать их в порядке возрастания, то каждый такой ключ мы будем называть уровнем. На каждом уровне нам может быть доступны к покупке 1 товар, или 2 товара, или > 2 товаров (в условиях задачи нет ограничений на такие вариации, но чтобы облегчить задачу, такие ограничения можно ввести). Пройти условие значит, что на данном уровне мы либо купили весь товар, доступный к продаже, либо минимальное возможное количество из условий. Т.е. на каждом уровне нам нужно купить либо 1 товар (если доступен всего 1 товар), либо минимум 2 товара (если доступно >= 2 товаров). Последний уровень – уровень на котором были сделана последняя покупка. Остаток – это переменная, которая хранит еще непотраченные деньги, т.е. это те деньги, которые остались после прохождения предыдущих уровней. s – доступный бюджет (дано в условии). Уже закупленные товары будем хранить в виде объекта purchases, организованного по примеру data. Закупленные товары на заданный бюджет с помощью алгоритма, предложенного в решении, будем так же хранить в объекте purchasesSolution, организованного по примеру data.
beep: Первая подзадача Пока мы можем выкупать весь уровень, ничего интересного не происходит. Как только мы не смогли выкупить весь уровень, появляется первое ветвление: 1) мы можем пройти условие; 2) мы не можем пройти условие. Если мы проходим условие, то алгоритм заканчивается (на что и рассчитан алгоритм в предложенном решении данной задачи). Если же мы не проходим условие, то начинается самое интересное и появляется новое ветвление, где мы можем купить x товаров: 1) x <= 1; 2) 1 < x < 2; 3) x >= 2. Третий вариант рассмотрен для того, чтобы перекрыть все возможные варианты, но внимательный человек скажет, что при x >= 2 условие будет пройдено и поэтому рассматривать такой вариант не имеет смысла. Первый вариант тоже не имеет смысла дальше рассматривать, если мы не прошли условие, то на этом уровне нужно выкупить минимум 2 товара и пробовать что-то делать с этой ситуацией бессмысленно (подсказка, мы никак не увеличим общее количество купленных товаров). Второй вариант нам говорит о том, что у нас еще есть остаток с которым можно поработать. Второй вариант сам по себе ветвится на 2 случая: 1) попробовать найти выше такой уровень, на котором к продаже доступен только 1 товар; 2) взять с какого-нибудь предыдущего уровня n товаров, так чтобы на данном уровне купить n + 1 товар. Первый вариант очень простой, мы просто смотрим все выше доступные уровни, пока нашего остатка хватает на покупку хотя бы одного товара на таком уровне и проверяем, можно ли на этом уровне купить всего 1 товар (т.е. к продаже доступен только 1 товар). Второй вариант сложнее, потому что нам нужно балансировать между 2 условиями: 1) сколько товаров доступно к продаже на данном уровне; 2) сколько товаров мы можем списать с предыдущего уровня. Напомню, что мы рассматриваем случай, где на данном уровне мы можем купить x товаров, где 1 < x < 2 и мы не прошли условие (не можем выкупить минимально возможное количество товаров, чтобы пройти уровень), т.е. нам нужно купить 2 товара, но нам не хватает. Чтобы пройти данный уровень, нам нужно купить минимум 2 товара, это мы можем сделать, например, если спишем с какого-нибудь предыдущего уровня 1 товар, тогда может получаться так, что если к остатку прибавить цену 1 товара с какого-то прошлого уровня, то нам хватит на 2 товара на данном уровне. Но на предыдущем уровне может оказаться так, что закуплено ровно 2 товара (было доступно к продаже всего 2 товара, см. выше место, где мы определяемся с терминами). Тогда мы не сможем списать 1 товар, поскольку нарушим заданное условие, где требуется приобретать минимум 2 товара, если к продаже доступно более 1 товара. В таком случае мы снова получаем ветвление: 1) списать 2 товара; 2) искать дальше предыдущий уровень, на котором можно списать 1 товар. В первом варианте если мы спишем 2 товара, то для осмысленного действия нам нужно купить 2 + 1 товаров (иначе мы не увеличим максимально возможное количество купленных товаров). Но может получиться так, что на данном уровне к продаже доступно всего 2 товара и мы не сможем купить 3 товара, поэтому и приходится балансировать между 2 условиями (см. выше). Если мы можем купить 3 товара (проходим по бюджету и по доступности товара), то алгоритм закончен. Если нам не хватает бюджета, то остается только второй вариант. Если же нам недоступно к покупке 3 товара, то нужно проверять уровни выше, где 3 товара к покупке доступны. Во втором варианте, как только мы нашли такой уровень, у нас либо получается увеличить максимальное количество купленных товаров на 1, либо нет. В любом случае тут алгоритм заканчивается (дальше мы не сможем списать 1 товар по меньшей цене, т.к. если нам не хватило этой цены за 1 товар, то гарантированно не хватит и меньшей цены). Случаи для проверки алгоритма: [pre2]# случай, когда есть уровень с 1 товаром data = { 30 : 2, 31 : 1, 32 : 3 } s = 30*2 + 31*1 + 32*3 purchases = { 30 : 2, 31 : 1, 32 : 3 } purchasesSolution = {}[/pre2] Предложенный в решении алгоритм просто зависает. [pre2]# случай, когда выше есть уровень с одним товаром data = { 30 : 2, 31 : 2, 32 : 3, 33 : 2, 34 : 1 } s = 30*2 + 31*2 + 32*3 + 34*1 + 1 purchases = { 30 : 2, 31 : 2, 32 : 3, 34 : 1 } purchasesSolution = { 30 : 2, 31 : 2, 32 : 3 }[/pre2] Как видим, предложенный в решении алгоритм не смог найти максимально возможное количество купленных товаров. [pre2]# случай, когда на предыдущем уровне списываем 1 товар data = { 30 : 2, 31 : 2, 32 : 3, 33 : 2 } s = 30*2 + 31*2 + 32*3 + 33*1 + 1 purchases = { 30 : 2, 31 : 2, 32 : 2, 33 : 2 } purchasesSolution = { 30 : 2, 31 : 2, 32 : 3 }[/pre2] Как видим, предложенный в решении алгоритм не смог найти максимально возможное количество купленных товаров. [pre2]# случай, когда на предыдущем уровне списываем 2 товара data = { 30 : 2, 31 : 2, 32 : 2, 33 : 3 } s = 30*2 + 31*2 + 32*2 + 33*1 + 2 purchases = { 30 : 2, 31 : 2, 33 : 3 } purchasesSolution = { 30 : 2, 31 : 2, 32 : 2 }[/pre2] Как видим, предложенный в решении алгоритм не смог найти максимально возможное количество купленных товаров. [pre2]# случай, когда на предыдущем уровне списываем 2 товара и добавляем на уровень выше текущего data = { 30 : 2, 31 : 2, 32 : 3 } s = 30*2 + 31*1 + 10 purchases = { 32 : 3 } purchasesSolution = { 30 : 2 }[/pre2] Как видим, предложенный в решении алгоритм не смог найти максимально возможное количество купленных товаров.
beep: Вторая подзадача Эта подзадача мне показалась самой сложной. В чем загвоздка? В предложенном решении, алгоритм довольно прост, считается, что максимальное число товаров по одной цене было на уровнях ниже последнего, тогда все просто, максимум вы уже нашли и остается только попробовать увеличить цену максимального товара за счет остатков бюджета. Но на самом деле этот максимум может быть где угодно, он может быть как ниже последнего уровня, так и на последнем уровне, и выше последнего уровня. В чем идея? В том, что за счет того, что уменьшая количество товара на предыдущих уровнях, можно попробовать купить больше товаров на уровнях выше, если там возможен новый максимум. Пример для пояснения: [pre2]data = { 30 : 2, 31 : 2, 32 : 2, 33 : 5 } s = 30*2 + 31*2 + 32*2 + 33*0 + 1*2 + 2*2 + 3*2 # 198[/pre2] Очевидно, что если мы купим 4 товара по 33 и 2 товара по 30 (в сумме 192), то мы получим новый максимум товаров, купленных по одной цене, но при этом не проиграем в количестве максимальных товаров. В предложенном решении этот шаг пропущен. В нем либо такой вариант не учтен, либо подразумевается, что максимум лежал ниже последнего уровня. Задача усложняется тем, что уменьшать количества товаров на прошлых уровнях можно многими способами и может получиться так, что например, на уровне n вы списали 2 единицы товара, а на уровне n-1 нужно списать минимально 2 единицы, а к списыванию возможен только 1 товар. Тогда нужно на уровне n списать не 2, а 1 товар, чтобы попробовать списать на уровне n-1 2 товара – в первом случае мы сможем прибавить к уровню с новым максимумом 2 товара, если получится, а во втором 3 товара, если получится. Поэтому просто списывать пока списывается с разных уровней сколько получится товаров не получится. Полным перебором подбирать оптимальный вариант тоже не хочется. Для начала я приведу пару примеров данных, которые могут вызвать проблемы. На них вы можете проверить свой алгоритм. Ниже будет спойлер, в нем я опишу алгоритм, который придумал я – так будет удобно тем, кто хочет вначале попробовать свои силы. [pre2]# случай, когда максимум ниже последнего уровня data = { 30 : 2, 31 : 2, 32 : 5, 33 : 3 } s = 30*2 + 31*2 + 32*5 + 33*2 + 2[/pre2] Тут все понятно, предложенный в решении алгоритм справляется, поскольку максимум 5 лежит ниже последнего уровня. [pre2]# случай, когда максимум на последнем уровне data = { 30 : 2, 31 : 2, 32 : 2, 33 : 5 } s = 30*2 + 31*2 + 32*2 + 33*0 + 1*2 + 2*2 + 3*2[/pre2] Тут предложенный в решении алгоритм дает сбой и в его переменной maxCount оказывается число 2, хотя мы вполне можем купить 4 товара по цене 33. [pre2]# случай, когда максимум на уровень выше последнего data = { 30 : 2, 31 : 2, 32 : 2, 33 : 3, 34 : 4 } s = 30*2 + 31*2 + 32*2 + 33*2 + 32[/pre2] Тут предложенный в решении алгоритм снова дает сбой и в его переменной maxCount опять оказывается число 2, хотя мы вполне можем купить 4 товара по цене 34. [pre2]# случай, когда максимум выше последнего уровня data = { 30 : 2, 31 : 1, 32 : 2, 33 : 3, 34 : 4, 35: 5 } s = 30*2 + 31*1 + 32*2 + 33*2 + 32[/pre2] Тут предложенный в решении алгоритм подвисает, потому что он не умеет покупать товар, доступный в одном экземпляре. Здесь уже становится с одной стороны не интересно придумывать варианты, потому что уже понятно, что алгоритм не справится, с другой стороны довольно сложно, потому что нужно правильно выбирать не только размер бюджета, но и сумму товаров таким образом, чтобы одинаковое количество можно было набрать несколькими способами. На этом шаге вы можете придумать свои примеры и варианты данных и поделиться ими в обсуждении, чтобы каждый проверил свой алгоритм. А теперь опишу свой алгоритм. После решения первой подзадачи у нас есть некоторый максимум. Для начала нам нужно проверить, существует ли такой уровень, на котором можно купить товаров по одной цене больше, чем этот максимум. Если такого уровня нет, то алгоритм закончен. Если же такой уровень есть, нам нужно проверить, можем ли мы купить на этом уровне товара больше, чем уже существующий максимум. Может получиться так, что мы можем выкупить весь уровень, или что бюджета хватит только на часть уровня. Тогда эта часть должна быть все равно больше, чем заданный максимум. На найденном уровне мы смотрим, сколько бы товара мы могли купить на весь бюджет по данной цене. Если у нас получается перебить заданный максимум, то дальше нам нужно посмотреть, сколько максимально товаров мы можем купить на остатки бюджета. А это как раз первая подзадача. Если в итоге количество товаров, которые мы купили не равно максимальному количеству товаров, то мы уменьшаем на 1 возможное количество купленных товаров по цене на уровне нового возможного максимума и производим все операции заново. Продолжаем мы эти попытки, пока возможное количество купленных товаров по цене на уровне нового возможного максимума перебивает заданный максимум или пока у нас не получилось перебить заданный максимум так, чтобы купить в сумме столько же товаров, сколько задано максимальным количеством. Когда мы разобрались с этим уровнем, нужно посмотреть, нет ли выше уровня, где можно получить новый максимум. Это будет продолжаться до тех пор, пока либо не закончатся уровни, либо мы не выйдем на такой уровень, где на весь бюджет по данной цене мы не сможем даже теоретически купить товара больше, чем заданный максимум. Последний удачный вариант и будет лучшим вариантом с новым максимумом. Если ни одного варианта не получилось, то исправлять нечего, и все остается, как на первом шаге.
beep: Третья подзадача Эта подзадача самая легкая. Тут все просто, у нас есть остатки бюджета, с помощью которых мы можем попробовать купить более дорогой товар за счет уменьшения количества товара на предыдущих уровнях. Первая идея, которая бросается в голову, это взять с последнего уровня 2 товара и с учетом остатка бюджета найти максимальную цену, по которой у нас получится купить 2 товара. Но здесь есть подводные камни: 1) выше может найтись такой уровень, где можно купить только 1 товар, если остаток прибавлять к 1 товару, то цена, по которой можно совершить покупку будет выше, чем если бы мы покупали 2 товара (остаток поделится на 2 товара и сумма прибавки к старой цене будет меньше); 2) нужно смотреть, сколько товара может быть «безопасно» списано. Например, если на последнем уровне куплено только 3 товара, то списать 2 товара нельзя. В итоге нужно просто найти 2 уровня и сделать 2 провери: 1) находим максимальный уровень, где может быть списан 1 товар и находим максимальный уровень, где можно купить 1 товар с учетом остатка; 2) находим максимальный уровень, где можно списать 2 товара и находим максимальный уровень, где можно купить 2 товара с учетом остатка; Дальше просто сравниваем цену покупки в обоих случаях и выбираем лучшую. Предложенный в решении алгоритм не учитывает возможность покупки только 1 товара и не проверяет, а можно ли вообще списать 2 товара, он предполагает, что везде куплено не меньше 4 товаров.
beep: Суммируя результаты, хочется сказать, что задача по сложности выбивается из остальных, предложенных для подготовки. Есть вариант толкования условий, где 2 вопроса не взаимосвязаны между собой, но решение не сильно упрощается. В итоге, либо автор не учел всю сложность комбинаторики в данной задаче, либо не до конца четко сформулировал условия и ограничения (предполагал одно, а вышло другое). По решению невозможно понять, то ли оно под частный случай и заданные данные, то ли автор решения не учел всю сложность задачи и не учел различные возможные случаи, где его алгоритмы упустят правильное решение. В итоге не хотелось бы получить подобную задачу на ЕГЭ, потому что если ее решать правильно, то это займет сильно много времени и не факт, что ответ сойдется с ответом, подразумеваемым при проверке ЕГЭ, т.к. автор задачи вот так может не учесть все возможные варианты, а с данными в этот раз не повезет. И потом бегай доказывай по комиссиям, что твое решение правильное. И не понятно, что лучше, решить задачу неправильно (если с данными не повезло), как и автор, или решить правильно, и потом оспаривать результаты. Если вы нашли ошибки, придумали более простое решение, придумали свой частный набор данных с подвохом, то дайте знать, мне будет интересно почитать ваши рассуждения или попробовать пройти ваши наборы данных. Отдельно было бы интересно почитать мнение автора задачи и мнение автора решения (если это разные люди).
beep: Чтобы решение подошло к задаче, нужно гарантировать 2 условия: 1) на каждом уровне товара, доступного к покупке, не меньше 2 единиц (а для прохождения части алгоритма, отвечающей за поиск максимальной цены, в том виде в каком он есть - не должно быть товара в наличии 3 единиц или возможности купить только 3 единицы); 2) при увеличении цены, количество товара, доступного к покупке, не становится больше. Тогда задача сильно упрощается и она будет соответствовать предложенному решению. Иначе, либо решение неправильное, либо оно подогнано под конкретные данные. На всякий случай сама задача: (№ 4213) (А. Комков) Магазин «1000 мелочей» закупает у поставщика продукцию для дальнейшей перепродажи. Известно количество товаров на складе у поставщика и стоимость каждого из них. К сожалению, бюджет магазина ограничен, поэтому принято решение закупить как можно больше товаров на ту сумму, которой располагает магазин, причем товары с одинаковой ценой закупают в количестве не менее двух штук. По заданной информации о цене каждого товара и бюджете магазина, определите 1) максимальную возможную стоимость товара, который можно купить при условии, что закупили максимально возможное количество товаров; 2)наибольшее количество купленных товаров, у которых одинаковая цена. Входные данные представлены в файле 26-58.txt следующим образом. В первой строке входного файла находятся два числа: S – размер бюджет магазина (натуральное число, не превышающее 100 000) и N – количество товаров на складе у поставщика (натуральное число, не превышающее 10000). В следующих N строках находятся значения цена каждого товара у поставщика (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала максимальную стоимость купленного товара, затем максимальное количество купленных товаров с одинаковой ценой. Пример входного файла: 100 9 20 30 20 5 10 15 10 30 10 В данном примере можно закупиться следующим образом: 10 10 10 20 20, либо 10 10 10 30 30. В первом случае максимальная стоимость товара будет 20, а во втором – 30. Наибольшее количество товаров с одинаковой ценой в обоих случаях равно 3. В ответе нужно указать: 30 3. Ответ: 64 159 И предложенное решение: [pre2]with open('26-58.txt') as F: S, N = map( int, F.readline().split() ) data = {} for i in range(N): x = int(F.readline()) data[x] = data.get(x,0) + 1 data = [[x,c] for x, c in data.items()] data.sort() total = 0 maxCount = 0 maxCost = 0 while data and total + 2*data[0][0] <= S: # print(data) if data[0][1] >= 2: k = 2 while k < data[0][1] and total + (k+1)*data[0][0] <= S: k += 1 print( '>', total, data[0], k ) total += k*data[0][0] maxCost = data[0][0] maxCount = max(maxCount, k) if k == data[0][1]: del data[0] print( maxCost, total, S ) total -= maxCost*2 while data and total + 2*data[0][0] <= S: if data[0][1] >= 2: print( total, data[0], 2 ) maxCost = data[0][0] maxCount = max(maxCount, 2) del data[0] print( maxCost, maxCount ) [/pre2]
mskorotkov: У задачи действительно куча проблем как в условии так и в решении. Из предложенного авторского решения следует, что товары, которых меньше 1 шт пропускаются, но в условии об этом ни слова. В конце решения из суммы вычитаются два товара, но если их покупалось 3, тогда вычитая два мы оставляем товар в кол-ве 1 шт, а по 1 шт брать нельзя. В общем караул какой-то.
beep: Из предложенного авторского решения следует, что товары, которых меньше 1 шт пропускаются Что имеется в виду? Если товаров меньше 1, то их нет.
полная версия страницы