Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.68/40: Рейтинг темы: голосов - 40, средняя оценка - 4.68
26 / 15 / 2
Регистрация: 28.06.2020
Сообщений: 50

Путешествие со свиньями

03.08.2020, 02:03. Показов 9374. Ответов 34

Студворк — интернет-сервис помощи студентам
У свинофермера Васи есть свиноферма рядом с городом М. Он решил навестить своего друга в городе С.-П. По дороге из М. в С.-П. расположено N городов, в которых свинина пользуется стабильным спросом. Вася решил совместить приятное с полезным и заработать немного денег. Он взял с собой N свиней и решил продавать по одной свинье в каждом из городов.

Цены на свиней в разных городах разные. В j-ом городе за один килограмм живого веса платят Pj рублей. Расстояние до j-го города по дороге из М. в С.-П. равно Dj километров.

Васины свиньи имеют разные веса. Перевозка одного килограмма свиньи на один километр обходится в T рублей.

Помогите Васе определить, каких свиней и в каком порядке нужно продавать, чтобы заработать побольше денег.

Входные данные

Первая строка входных данных содержит числа N(1≤N≤1000) и T(1≤T≤109) . Вторая строка содержит N чисел Wi, задающих вес Васиных свиней (1≤Wi≤109) . Третья строка содержит N чисел Di, задающих расстояния до города i от М(1≤Di≤109) . Четвертая строка содержит N чисел Pi, задающих цены в городах (1≤Pi≤109) . Все числа целые.

Выходные данные

Выведите N чисел. j-ое число должно быть номером свиньи, которую следует продать в j-ом городке. Свиньи нумеруются с 1 в том порядке, как они перечислены во входном файле.

Примеры
Ввод
Вывод
3 1
10 20 15
10 20 30
50 70 60
3 2 1
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.08.2020, 02:03
Ответы с готовыми решениями:

Путешествие со свиньями
Путешествие со свиньями У свинофермера Васи есть свиноферма рядом с городом М. Он решил навестить своего друга в городе С.-П. По дороге...

Путешествие
Доброго времени суток! Помогите пожалуйста решить эту задачу: Ваш друг решил отправиться в путешествие по городам страны, которых...

Путешествие по мирам
Путешественник Мориорти любит путешествовать между мирами. Он знает n миров. Массив a описывает n порталов, с помощью которых он может...

34
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
28.08.2020, 12:03
Студворк — интернет-сервис помощи студентам
Gdez, Спасибо, сейчас попробую и отпишусь

Добавлено через 29 минут
Gdez, а если не long long, то какой тип данных тогда? Есть unsigned long long, но он только для больших ПОЛОЖИТЕЛЬНЫХ чисел
0
Эксперт Python
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,320
28.08.2020, 12:59
Из формулы checkprofit убери вес свиньи. На результат сравнения не влияет, так как индексация веса идет по "i", a checkprofit по "М"
Профит начальный тогда = -1e18 - 1
В дабллонг укладывается
Кстати, понял, почему в задачах ограничения часто 10^9 )))

Добавлено через 27 секунд
В питоне можно числа больше 1е300
0
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
28.08.2020, 13:14
Gdez, Вот я сделал так:
C++
1
2
profit = -1e18 - 1;
checkprofit = (cp[M].first) - (cp[M].second * t);
Код также проходит 13 тестов из 20. Я все ещё не понял, на каком основании можно убрать из формулы вес свиньи, он же тут критически важен. Да, у массива cp и pigs разная индексация (и что?).
0
Эксперт Python
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,320
28.08.2020, 13:27
Выбрасывает не по времени?
0
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
28.08.2020, 13:28
Gdez, Wrong answer
0
Эксперт Python
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,320
28.08.2020, 13:45
Тоже исправить на -1е18:
cp[R].first = 0
А после этого оператора вставить:
pigs[n - 1 - i].first = 0
Чтобы уже выбранная(проданная) свинья не попала в следующий выбор

Добавлено через 1 минуту
Потом исправленный код без комментариев выложи
Логику и синтаксис понял

Добавлено через 9 минут
Вообще то ошибся - вес обнулять не обязательно(((
0
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
28.08.2020, 13:55
Gdez, вы волшебник! Программа прошла все тесты, спасибо большое!!! Я все ещё не понял, на каком основании можно убрать из формулы вес свиньи, он же тут критически важен. Да, у массива cp и pigs разная индексация (и что?).

И да, вес обнулять не обязательно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    long long n, t, pig, city, price, R, profit, checkprofit;
    cin >> n >> t;
 
    vector <pair<long long, long long>> pigs;
    vector <long long> cities;
    vector <long long> prices;
    vector <pair<long long, long long>> cp;
    vector <long long> ans(n);
 
 
    for (long long i = 0; i < n; ++i){
        cin >> pig;
        pigs.push_back(make_pair(pig, i));
    }
 
    for (long long i = 0; i < n; ++i){
        cin >> city;
        cities.push_back(city);
    }
 
    for (long long i = 0; i < n; ++i){
        cin >> price;
        prices.push_back(price);
    }
 
    for (long long i = 0; i < n; ++i){
        cp.push_back(make_pair(prices[i], cities[i]));
    }
 
    sort(begin(pigs), end(pigs));
 
    for (long long i = 0; i < n; ++i){
        profit = -1e18 - 1;
        for (long long M = 0; M < n; ++M){
            checkprofit = (cp[M].first) - (cp[M].second * t);
            if (checkprofit > profit){
                profit = checkprofit;
                R = M;
            }
        }
        ans[R] = pigs[n - 1 - i].second;
        cp[R].first = -1e18 - 1;
    }
 
    for (auto i : ans){
        cout << i + 1 << " ";
    }
 
    return 0;
}
Добавлено через 3 минуты
Gdez, до меня дошло почему вес свиньи можно убрать. Чтобы до этого додуматься, нужны знания математики 6 класса (facepalm)

Добавлено через 5 минут
Gdez, мне кажется наше с вами решение самое простое и понятное. Решения выше опираются на внутренние особенности и функции языка Python. А в данном решении сложнее цикла и массива пар нет ничего. Ещё раз вам спасибо!
0
Эксперт Python
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,320
28.08.2020, 13:57
Я все ещё не понял, на каком основании можно убрать из формулы вес свиньи, он же тут критически важен.
Потому что важна себестоимость.
И выгоднее продавать самую большую при самой высокой себестоимости.
У тебя вес отсортирован. Внешний цикл по весу (от максимума к минимуму).
Внутренний ищет самую большую себестоимость и "продает "i"-ую (самую выгодную) свинью - присваивает ее индекс индексу города.
Вес нужен ТОЛЬКО для организации порядка внешнего цикла.
0
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
28.08.2020, 14:00
Gdez, да-да, я понял. Я написал об этом ниже кода. Но спасибо, что ещё раз объяснили
0
Эксперт Python
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,320
28.08.2020, 14:03
Рад, что помог
Обращайтесь )))
0
Эксперт PythonЭксперт Java
19530 / 11067 / 2931
Регистрация: 21.10.2017
Сообщений: 23,294
28.08.2020, 18:07
Blabla7, Gdez, ребят, мож вам тут решение и на джаве подкинуть?
То, что ветка Python, это ничего.
0
5 / 5 / 0
Регистрация: 14.05.2019
Сообщений: 29
28.08.2020, 18:12
iSmokeJC, если хотите - давайте, интересно будет взглянуть на решение на Java. А то плюсы, да змейка, а вот жабку давно не видел))
0
Эксперт PythonЭксперт Java
19530 / 11067 / 2931
Регистрация: 21.10.2017
Сообщений: 23,294
28.08.2020, 18:13
Цитата Сообщение от BeginHelloWorld Посмотреть сообщение
жабку давно не видел
Целый раздел есть. Смотреть - не пересмотреть. А намек как бы на другое был...
0
5 / 5 / 0
Регистрация: 14.05.2019
Сообщений: 29
28.08.2020, 19:51
iSmokeJC, намек-то был самый прозрачный, я бы даже сказал, это был не намек, а ирония. С такой же иронией я и ответил
1
0 / 0 / 0
Регистрация: 29.03.2018
Сообщений: 1
31.08.2020, 14:35
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <deque>
#include <random>
#include <string>
 
using namespace std;
 
typedef long long ll;
 
int main() {
    ll n, k; cin >> n >> k;
    vector<pair<ll,ll>>a(n);
    for (int i = 0; i < n; i++) 
        cin >> a[i].first, a[i].second = i;
    vector<ll>d(n), p(n);
    vector<pair<ll,ll>>prof(n);
    for (int i = 0; i < n; i++) 
        cin >> d[i];
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        prof[i].first = p[i] - k * d[i];
        prof[i].second = i;
    }
    sort(prof.begin(), prof.end());
    reverse(prof.begin(), prof.end());
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
 
    vector<ll>res(n);
    for (int i = 0; i < n; i++) 
        res[prof[i].second] = a[i].second;
    for (auto to: res ) 
        cout << to + 1 << " ";
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
31.08.2020, 14:35

Путешествие по таблице
Путешествие по таблице В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается...

Путешествие по матрице
Еще задача: Вам дана нижнетреугольная матрица из n строк (i-й ряд состоит ровно из i элементов, располо- женных в столбцах с...

Путешествие в прошлое
Вот такая тема: Представте что вам предоставился один единсвенный шанс в жизни побывать в прошлом. Вопрос: в какое время бы вы...

Путешествие продавца
Ограничение по времени: 1 секунда Ограничение по памяти: 64 мегабайта Как обычно, кому-то надо продать что-то во многих городах....

Путешествие Андрея
Андрей едет из пункта A в пункт B на автомобиле. Расстояние между этими пунктами равно N километров. Известно, что с полным баком...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Новые блоги и статьи
Просветление в 5 секунд
kumehtar 10.07.2026
Андрей Веретенников выдал фразу недавно: "Вам не обязательно кем-то себя считать"
Эксперимент с картинкой-обложкой на CodinGame
Adler 10.07.2026
Решил на днях провести эксперимент. У меня есть аккаунт на CodinGame, ТОП-3 по РФ среди 2200 участников (в разделе соревнования по программированию ИИ-ботов). Там есть обложка, куда можно влепить. . .
GitDOS: Когда я решил скрестить MS-DOS, GitHub и Claude
MaGz GoLd 08.07.2026
Привет, Киберфорум! Хочу поделиться своим проектом, который, надеюсь, вас заинтересует. GitDOS — это веб-приложение, которое позволяет запускать DOS в браузере с тремя крутыми фичами: диски живут в. . .
Учебный мини "цифровой двойник" = (Сервер = Java + Flask_питон )+(3D = Гугловскаая 4T nvideo + google colab) +( WMS = Odoo на Docker)
anaschu 07.07.2026
Увидел в требованиях к вакансии создателя имитационных моделей связку (REst + Api + WMS + Anylogic + питон + 3D Nvideo), и решил посмотреть, что это такое. Из этого всего я работал более менее. . .
Море в объективе
kumehtar 06.07.2026
Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii.
dcc0 05.07.2026
Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .
Установка статуса документа по условию
Maks 05.07.2026
Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв
anaschu 04.07.2026
200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru