На олимпиаду по информатике в другой город едут 100 школьников, для которых нужно приобрести билеты на поезд. Все школьники должны приехать одним поездом, при этом олимпиада начинается 20 апреля. Поэтому из всех подходящих поездов нужно выбрать тот, который приезжает как можно позже, но не позднее 20‑го апреля. Если таких поездов несколько, то требуется выбрать тот поезд, на который получится приобрести 100 билетов по минимальной суммарной стоимости.
Для решения этой задачи вам понадобится файл с электронной таблицей, содержащей сведения о поездах и имеющихся в продаже билетах.
Скачать файл в формате Microsoft Excel (xlsx).
Скачать файл в формате Open Document Spreadsheet (ods).
В столбце A содержится номер поезда. В столбце B записана дата прибытия поезда, число n в этом столбце обозначает, что поезд прибывает n‑го апреля. Все поезда прибывают приблизительно в одно и то же время, поэтому имеет значение только дата прибытия, но не точное время. Количество билетов на поезд указано в столбце C, а их цена — в столбце D. Одному поезду в этой таблице может соответствовать несколько строк, поскольку в одном поезде могут быть билеты разной стоимости. В таком случае значения в столбцах A и B этих строк будут совпадать.
Вам нужно выбрать поезд так, чтобы в нём было хотя бы 100 свободных мест (возможно, по разным ценам), и он прибывал не позднее 20 числа. Среди таких поездов нужно выбрать тот, который прибывает как можно позже. Если несколько подходящих поездов прибывают в один день, то среди них необходимо выбрать тот, 100 билетов на который обойдутся дешевле остальных. Гарантируется, что после этого ответ будет однозначным.
Заполните таблицу с характеристиками выбранного вами поезда.
1 Ответ
Для решения этой задачи можно использовать алгоритм сортировки по цене и выбору минимального элемента из списка, если количество мест меньше 100. Вот пример кода на Python:
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
vector <pair<int, int> > a[1005];
int b[1005], c[1005];
pair <int, int> ans = {0, 0};
int main() {
ifstream input(«tickets.txt»);
int train, day, cnt, price;
while (input >> train >> day >> cnt >> price) {
if (day <= 20) {
a[train].push_back({price, cnt});
b[train] += cnt;
c[train] = day;
ans = {1000000, train};
}
}
for (int i = 1; i <= 1000; i++) {
if (b[i] >= 100) {
sort(a[i].begin(), a[i].end());
int res = 0;
cnt = 0;
for (auto j : a[i]) {
if (cnt + j.second <= 100) {
cnt += j.second;
res += j.first * j.second;
} else {
res += j.first * (100 — cnt);
break;
}
}
if (c[ans.second] < c[i] || (c[ans.second] == c[i] && res < ans.first)) {
ans.first = res;
ans.second = i;
}
}
}
cout << c[ans.second] << » » << ans.second << » » << ans.first << endl;
}