CINXE.COM

<!DOCTYPE html> <html lang="ru"> <head> <meta charset="utf-8"> <link rel="stylesheet" href="/pyplanet_tmpl/css/style.css"> <link rel="stylesheet" href="/pyplanet_tmpl/css/pygments.css"> <link rel="stylesheet" href="/pyplanet_tmpl/fonts/stylesheet.css"> <title>Открытый вариант КИМ ЕГЭ по информатике 2024. Задание 27 решение Python с нуля до бесконечности</title> <meta name="description" content='Решение задачи 27 открытого варианта КИМ ЕГЭ по информатике 2024 на языке программирования Python'> <meta name="viewport" content="width=device-width, initial-scale=1"> <link rel="apple-touch-icon" sizes="76x76" href="/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png"> <link rel="manifest" href="/site.webmanifest"> <link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5"> <meta name="msapplication-TileColor" content="#da532c"> <meta name="theme-color" content="#ffffff"> <script type="text/javascript" > (function(m,e,t,r,i,k,a){m[i]=m[i]||function(){(m[i].a=m[i].a||[]).push(arguments)}; m[i].l=1*new Date(); for (var j = 0; j < document.scripts.length; j++) {if (document.scripts[j].src === r) { return; }} k=e.createElement(t),a=e.getElementsByTagName(t)[0],k.async=1,k.src=r,a.parentNode.insertBefore(k,a)}) (window, document, "script", "https://mc.yandex.ru/metrika/tag.js", "ym"); ym(97429815, "init", { clickmap:true, trackLinks:true, accurateTrackBounce:true, webvisor:true }); </script> <noscript><div><img src="https://mc.yandex.ru/watch/97429815" style="position:absolute; left:-9999px;" alt="" /></div></noscript> <script>window.yaContextCb=window.yaContextCb||[]</script> <script src="https://yandex.ru/ads/system/context.js" async></script> </head> <body> <nav class="header-menu"> <ul> <li><a href="/"><img class="text-image" src="/pyplanet_tmpl/img/homepage.png" alt="На главную"></a></li> <li>Категории ↓ <ul> <li><a href="/category/osnovy.html">Основы</a></li> <li><a href="/category/enhanced.html">Продвинутый</a></li> <li><a href="/category/guidebook.html">Справочник</a></li> <li><a href="/category/ege.html">Разборы ЕГЭ</a></li> <li><a href="/category/tasks.html">Решение разных задач</a></li> </ul> <li><a href="/pages/books.html">Книги</a></li> <li><a href="/pages/courses-free.html">Бесплатные курсы</a></li> <li><a target="_blank" href="https://www.tinkoff.ru/cf/6xIycbvJQF9">Поддержать</a></li> </ul> </nav> <div id="main-page"> <article> <header> <h1>Открытый вариант КИМ ЕГЭ по информатике 2024. Задание 27 решение</h1> </header> <div> <div class="section" id="section-2"> <h2>Условие задачи</h2> Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N километров. Нулевой и N-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна. Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе. <div class="section" id="section-3"> <h3>Входные данные</h3> Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов питания на кольцевой трассе. В каждой из следующих N строк находится число – количество комплектов питания на пункте (все числа натуральные, количество комплектов питания на каждом пункте не превышает 1000). Числа указаны в порядке расположения пунктов питания спортсменов на трассе, начиная с первого километра. В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B. Типовой пример организации данных во входном файле: <pre class="code text literal-block"> 6 8 20 5 13 7 19 </pre> При таких исходных данных, если пункты питания установлены на каждом километре трассы, необходимо открыть мобильный цех подготовки комплектов питания для спортсменов в пункте 6. В этом случае сумма транспортных затрат составит: 1 * 7 + 0 * 19 + 1 * 8 + 2 * 20 + 3 * 5 + 2 * 13 = 96. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго. Скачать вариант и файлы к нему можно на <a class="reference external" href="https://doc.fipi.ru/ege/otkrytyy-bank-zadaniy-ege/otkrytyye-varianty-kim-ege/2024/Inf_1_ege2024.zip">сайте ФИПИ</a>. Скачаем файлы и увидим <tt class="docutils literal">1_27_A.txt</tt> и <tt class="docutils literal">1_27_B.txt</tt>. В первом трасса 110км, во втором - 1 200 000. </div> </div> <div class="section" id="section-4"> <h2>Решение перебором</h2> Сразу же напрашивается решение перебором, напишем его и подробно разберём. <div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16</pre></div></td><td class="code"><div><pre>with open("A.txt", "r") as f: N = int(f.readline().strip()) supplies = [int(f.readline().strip()) for line in range(N)] min_cost = float('inf') for mobile_point_idx in range(N): current_cost = 0 for destination_idx in range(N): distance_if_straight = abs(mobile_point_idx - destination_idx) distance_if_reversed = N - distance_if_straight # Если идём сквозь начало трассы distance = min(distance_if_straight, distance_if_reversed) current_cost += distance * supplies[destination_idx] if current_cost < min_cost: min_cost = current_cost print(min_cost) </pre></div></td></tr></table></div> <ol class="arabic simple"> <li>Открываем файл с помощью инструкции <a class="reference external" href="/article/with-as.html">менеджера контекста with</a></li> <li>Считываем количество километров <tt class="docutils literal">N</tt></li> <li>Считываем количество необходимых продуктов питания на каждом километре с помощью <a class="reference external" href="/article/set-dict-list-comprehension.html">генератора списков</a></li> </ol> <ol class="arabic simple" start="5"> <li>Инициализируем нашу минимальную стоимость (которую мы будем каждую итерацию по возможности обновлять) очень большим числом (а именно бесконечностью)</li> <li>Цикл по местоположению мобильного пункта питания (для каждого возможного положения пункта будем рассчитывать стоимость доставок)</li> <li>Инициализируем стоимость доставки из этого пункта (на <tt class="docutils literal">mobile_point_idx</tt> километре) нулём</li> <li>Цикл по пункту назначения (вычисляем стоимость доставки необходимых продуктов для пункта <tt class="docutils literal">destination_idx</tt> из пункта мобильного питания, находящегося на <tt class="docutils literal">mobile_point_idx</tt> километре)</li> <li><tt class="docutils literal">distance_if_straight</tt> - это расстояние, на которое нам нужно доставить, если мы будем двигаться в прямом направлении (не пересекая начало трассы)</li> <li><tt class="docutils literal">distance_if_reversed</tt> - это расстояние, на которое нам нужно доставить, если мы будем двигаться в обратном направлении (через начало трассы)</li> <li>Соответственно, то расстояние, которое проедет электрокар к этой точке, есть минимум этих двух расстояний</li> <li>Стоимость доставки всех продуктов увеличиваем на стоимость доставки из пункта <tt class="docutils literal">mobile_point_idx</tt> в пункт <tt class="docutils literal">destination_idx</tt></li> <li>Цикл по пункту назначения закончился. Получили общую стоимость доставки. Если она меньше нашего текущего минимума,</li> <li>то мы нашли новый минимум и записываем его в переменную</li> </ol> <ol class="arabic simple" start="16"> <li>Перебрав все возможные значения пункта мобильного питания, печатаем минимальную стоимость. Это и есть наш ответ</li> </ol> </div> <div class="section" id="section-5"> <h2>Как проверять решение</h2> Всегда когда вы написали какое-либо решение, проверяйте его. В этой задаче есть написанный пример с шестикилометровой трассой. Создадим файл, например, <tt class="docutils literal">D.txt</tt> с содержимым из примера, и запустим нашу программу (не забыв исправить в строке 1 <tt class="docutils literal">A.txt</tt> на <tt class="docutils literal">D.txt</tt>). Ответ будет <tt class="docutils literal">96</tt>, как и объяснено в условии. Это значит, что скорее всего, решение верное. Если сомневаетесь в своём решении, напишите вручную ещё несколько небольших примеров на задачу. Для файла <tt class="docutils literal">A.txt</tt> ответ будет <tt class="docutils literal">141530</tt>. Файл <tt class="docutils literal">B.txt</tt> вычислить не получится: слишком долго. </div> <div class="section" id="section-6"> <h2>Оптимизация решения</h2> Что происходит при смещении точки мобильного питания? Какие-то точки становятся на километр дальше, какие-то - на километр ближе. А значит, можно быстро пересчитывать итоговую стоимость при сдвиге мобильного пункта. Напишем такое решение и подробно его разберём. <div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22</pre></div></td><td class="code"><div><pre>with open("A.txt", "r") as f: N = int(f.readline().strip()) supplies = [int(f.readline().strip()) for line in range(N)] half_n = N // 2 current_cost = right_direction_sum = left_direction_sum = 0 for i in range(1, half_n + 1): current_cost += supplies[i] * i right_direction_sum += supplies[i] for i in range(N - 1, half_n, -1): current_cost += supplies[i] * (N - i) left_direction_sum += supplies[i] left_direction_sum += supplies[0] total_costs = [current_cost] for mobile_point_idx in range(1, N): total_costs.append(total_costs[-1] - right_direction_sum * 1 + left_direction_sum * 1) right_direction_sum = right_direction_sum - supplies[mobile_point_idx] + supplies[(mobile_point_idx + half_n) % N] left_direction_sum = left_direction_sum + supplies[mobile_point_idx] - supplies[(mobile_point_idx + half_n) % N] print(min(total_costs)) </pre></div></td></tr></table></div> <ol class="arabic simple" start="6"> <li>Инициализируем переменные. <tt class="docutils literal">current_cost</tt> - суммарная стоимость доставки для какого-то определённого положения мобильного пункта питания. <tt class="docutils literal">right_direction_sum</tt> - суммарное количество обедов, которые электрокару выгоднее доставить, поехав в "правую" сторону (от километра с меньшим номером к километру с большим) <tt class="docutils literal">left_direction_sum</tt> - суммарное количество обедов, которые электрокару выгоднее доставить, поехав в "левую" сторону</li> <li>Теперь посчитаем эти переменные для случая, если мобильный пункт питания установлен на нулевом километре</li> <li>Все километры с 1 по <tt class="docutils literal">N // 2</tt> включительно электрокару выгоднее доставить "направо"</li> <li>Стоимость доставки в этот пункт <tt class="docutils literal">supplies[i] * i</tt> (<tt class="docutils literal">supplies[i]</tt> - количество комплектов питания, <tt class="docutils literal">i</tt> - расстояние от 0 до точки доставки). Увеличиваем текущую стоимость</li> <li>И увеличиваем <tt class="docutils literal">right_direction_sum</tt> на количество обедов в этом пункте</li> <li>Все километры с последнего по <tt class="docutils literal">N // 2</tt> электрокару выгоднее доставить "налево" (так как трасса кольцевая, то это маршрут <tt class="docutils literal">0</tt> → <tt class="docutils literal">N-1</tt> → <tt class="docutils literal">N-2</tt> и т.д.)</li> <li>Как и 9 строка, только расстояние равно <tt class="docutils literal">N - i</tt></li> <li>И увеличиваем <tt class="docutils literal">left_direction_sum</tt> на количество обедов в этом пункте</li> <li>Условимся, что в сам пункт мобильного питания (сейчас это пункт 0) электрокар доставляет "налево" (пусть и проезжает нулевое расстояние). Увеличим <tt class="docutils literal">left_direction_sum</tt>, а на стоимость доставки эта точка не влияет</li> </ol> <ol class="arabic simple" start="16"> <li>Теперь создадим массив <tt class="docutils literal">total_costs</tt> - это стоимость доставки, если пункт питания будет в точке, равной индексу массива. В точке 0, как мы посчитали, стоимость равна <tt class="docutils literal">current_cost</tt></li> <li>Цикл по всем возможным позициям мобильного пункта</li> <li>Считаем новую стоимость доставки. Она равна <tt class="docutils literal">total_costs[-1]</tt> - стоимость доставки, если пункт питания находится на километр левее в сторону старта; <tt class="docutils literal">- right_direction_sum * 1</tt> - все обеды, которые выгодно доставлять направо, стали на 1 километр ближе (поскольку пункт питания сместился направо); <tt class="docutils literal">+ left_direction_sum * 1</tt> - все обеды, которые выгодно доставлять налево, стали на 1 километр дальше</li> <li>Но после перемещения пункта питания часть обедов стало выгоднее возить в другую сторону. Пункт <tt class="docutils literal">mobile_point_idx</tt> мы доставляли "направо", теперь же и далее его будет выгодно доставлять "налево". А пункт <tt class="docutils literal">(mobile_point_idx + half_n) % N</tt> мы доставляли "налево", теперь же и далее его будет выгодно доставлять "направо". Практический смысл пункта <tt class="docutils literal">(mobile_point_idx + half_n) % N</tt> таков: это наиболее удалённая от пункта питания точка доставки. И при перемещении мобильного пункта правее, именно эта точка оказывается более выгодной для доставки "направо", чем "налево"</li> <li>Соответственно, прибавляем и вычитаем количество обедов в соответствии с пунктом 19</li> </ol> <ol class="arabic simple" start="22"> <li>В конце у нас получился массив со стоимостью доставок для каждого положения мобильного пункта. А ответом служит минимум из всех стоимостей</li> </ol> </div> <div class="section" id="section-7"> <h2>"Проверка" решения</h2> У нас уже есть известные ответы для <tt class="docutils literal">A.txt</tt> и <tt class="docutils literal">D.txt</tt>. Запустим (не забыв поменять в строке 1 название файла) и проверим. <tt class="docutils literal">A.txt</tt> - 141530, <tt class="docutils literal">D.txt</tt> - 96. Значит, скорее всего, решение верное. <div class="note docutils container"> <ul class="simple"> <li>Всегда проверяйте каждое решение на данных из примера. Это уменьшит количество ошибок</li> <li>Всегда пишите сначала простое решение, а затем оптимизированное. Оптимизированное можно будет проверить на правильность с помощью простого решения</li> <li>Поскольку у нас есть написанное решение перебором, можно сравнить ответы перебором и ответы оптимизированным решением на любых небольших входных данных</li> </ul> </div> Теперь запустим это решение на файле <tt class="docutils literal">B.txt</tt> и получим ответ <tt class="docutils literal">18192010182272</tt>. </div> <div class="section" id="section-8"> <h2>Вместо заключения</h2> На самом деле, иногда эта программа выдаёт неправильный ответ. Приглашаю в нашу Telegram-группу обсудить, когда это решение выдаёт неправильный ответ, и как это решение исправить. Заметка: на файлах <tt class="docutils literal">A.txt</tt>, <tt class="docutils literal">B.txt</tt>, <tt class="docutils literal">D.txt</tt> решение и ответы правильные. </div> </div> </article> <nav class="nav-below"> <div class="nav-previous"> </div> <div class="nav-cat"> <a href="/category/ege.html">В категорию "ЕГЭ по информатике на Python"</a> </div> <div class="nav-next"> </div> </nav> <nav class="nav-below" style="padding-top:2rem"> <div> <a target="_blank" href="https://t.me/pyplanet"><button class="telegram-button">✈ Telegram</button></a> </div> <div> <a target="_blank" href="https://www.tinkoff.ru/cf/6xIycbvJQF9"><button class="tinkoff-button">Поддержать ₽</button></a> </div> </nav> <nav class="nav-below"> <div id="yandex_rtb_R-A-9079088-1"></div> <script> window.yaContextCb.push(()=>{ Ya.Context.AdvManager.render({ "blockId": "R-A-9079088-1", "renderTo": "yandex_rtb_R-A-9079088-1" }) }) </script> </nav> </div> <footer> <div>(c) 2024 <a href="/">pyplanet - Python с нуля до бесконечности</a></div> </footer> </body> </html>