Zadanie Kupiec z II etapu IV OIG

Archimondei

2014-03-15T19:33:26+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 50

0

Cześć. Potrzebuję pomocy z jednym zadaniem z OIG. Jego treść znajduje się tutaj: http://main.edu.pl/pl/archive/oig/4/kup
Mój problem polega generalnie na tym, że nie mam pojęcia jak rozwiązać te zadanie.

Shalom

2014-03-15T20:56:43+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Space: the final frontier
Postów: 26433

0

Tak to bywa z konkursami że nie każdy potrafi rozwiązać. Odpuść to zadanie i rób inne a do tego wróć jak trochę przyskillujesz.

bartek19121995

2014-03-17T14:05:06+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 68

0

Musisz ich dużo zrobić, żeby zaczeły jakoś iść. Co do zadania to bardzo przypomina problem podciągu spójnego o maksymalnej sumie (gdzieś mi zniknęła opcja wstawiania linku: http://main.edu.pl/pl/user.phtml?op=lesson&n=29&page=algorytmika). Przeczytaj to i zastanów się nad tym jeszcze raz. Jeśli nie masz pomysłu na wzorcówkę, zrób najpierw bruta - rozpatrz każdy możliwy początek i koniec o(n^2).

Tacet

2014-03-28T21:35:47+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 45

1

bartek19121995 napisał(a):

Co do zadania to bardzo przypomina problem podciągu spójnego o maksymalnej sumie

Te zadana nawet koło siebie nie leżały. Tutaj możemy kupić dokładnie raz i tyleż samo razy sprzedać.
Rozwiązanie zadania jest dość proste (choć niemiło mi się je pisało). Najpierw trzeba napisać sobie funkcję, która będzie nam zwracała w czasie stałym koszt przejazdu pomiędzy miastem p i q. Możemy to zrobić w czasie liniowym (przygotowanie jej), robiąc tablice sum prefiksowych (i wstawiając na jej początek zero, bo z pierwszego miasta do niego samego koszt to zero). Potem tylko:

Kopiuj

  (unsigned p, unsigned q){return abs(koszty[q]-koszty[p])} //Obliczanie kosztu przejazdu między miastami p i q

Teraz trzeba zauważyć, że rozpatrujemy osobno podróże "w lewo" i "w prawo". Zacznijmy od rozpatrzenia podróży "w lewo". Jest to już w zasadzie prawie dynamik. Trzeba tylko zauważyć, że jeśli wyruszamy z pewnego miasta w lewo to albo opłaca się nam iść z tego miasta do miasta, do którego opłacało się iść z poprzedniego (o jeden w lewo), albo w ogóle z niego nie wychodzić. Nie opłaca nam się z niego wychodzić, jeśli koszt zakupu i podróży jest większy od ceny sprzedaży.
Dodatkowy fakt, na który trzeba zwrócić uwagę to ten, że z miasta pierwszego nie wyjdziemy (bo dalej nic nie ma), więc początkowo najlepsze miasto to właśnie ono.

Kopiuj

   for(auto i = 0U, najlepsze = i; i != n; ++i) { //najlepszy - miasto do którego opłaca się iść
    if(cena_produktu[najlepsze] < cena_produktu[i] + cena_podrozy(najlepsze, i))
     najlepsze = i; //Nie opłaca się wychodzić w tą stronę
    wynik.push_back(najlepsze);
   }

Teraz jak już wiemy dokąd opłaca nam się iść z każdego miasta, wystarczy przeiterować tablice i wybrać miasto, które daje największy zysk.

Kopiuj

 for(unsigned i = 0; i < n; ++i) {
     najwiekszy_zysk = max(najwiekszy_zysk, cena_produktu[w_lewo[i]] - (cena_produktu[i] + cena_podrozy(i,w_lewo[i])));
   }

Problem "w prawo" rozwiązujemy analogicznie, możemy nawet tymi samymi funkcjami jeśli rozsądnie poodwracamy tablice.Na koniec wybieramy max z dwóch wartości, największego zysku jeśli zdecydujemy się iść w prawo oraz największego zysku, jeśli zdecydujemy się iść w lewo.
Może kiedyś tu wrócę i udowodnię poprawność tego rozwiązania, tymczasem musi starczyć to, że jak się je tak rozwiąże i zadba o parę niuansów to uzyskuje się maksymalną liczbę punków.

Edit:
Jeśli ktoś by chciał to umieszczam kod, który pisałem ostatnio na czas:

Kopiuj

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
 
using namespace std;
 
unsigned wylicz(const vector<unsigned>& towary, const vector<unsigned>& przejazdy);
 
int main() {
        ios_base::sync_with_stdio(false);
        unsigned n;
        cin >> n;
        vector<unsigned> towary(n);
        for(auto& x : towary) // Stare gcc
                cin >> x;
        vector<unsigned> przejazdy = {0}, przejazdy_sum;
        przejazdy.reserve(n+1); przejazdy_sum.reserve(n+1);
        copy_n(istream_iterator<unsigned>(cin), n-1, back_inserter(przejazdy));
        partial_sum(begin(przejazdy), end(przejazdy), back_inserter(przejazdy_sum));
        auto wynik = wylicz(towary, przejazdy_sum);
        reverse(begin(towary), end(towary));
        reverse(begin(przejazdy) + 1, end(przejazdy));
        partial_sum(begin(przejazdy), end(przejazdy), begin(przejazdy_sum));
        wynik = max(wynik, wylicz(towary, przejazdy_sum));
        cout << wynik << '\n';
}
 
unsigned wylicz(const vector<unsigned>& towary, const vector<unsigned>& przejazdy) {
    auto koszt_f = [&przejazdy](unsigned i, unsigned j){return przejazdy[j] - przejazdy[i];};
        unsigned wynik = 0, optymalne = 0;
        for(unsigned i = 0; i < towary.size(); ++i) {
                const auto koszt = towary[optymalne] + koszt_f(optymalne, i);
                if(wynik +  koszt < towary[i]  ) {
                        wynik = towary[i] -  koszt;
                }
                if(towary[i] < towary[optymalne] + koszt_f(optymalne, i)) {
                        optymalne = i;
                }
        }
        return wynik;
}

Maksymilian Polikowski

2026-01-09T21:54:28+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 2

0

Archimondei napisał(a):

Cześć. Potrzebuję pomocy z jednym zadaniem z OIG. Jego treść znajduje się tutaj: http://main.edu.pl/pl/archive/oig/4/kup
Mój problem polega generalnie na tym, że nie mam pojęcia jak rozwiązać te zadanie.

@Archimondei:Dobra wiem że trochę dużo czasu minęło od tego pytania , ale wrzucę tu , moim zdaniem najczytejniejszy kod ze wszystkich poprzednich :

Kopiuj

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> cen(n + 7) , pod(n + 7);
    for(int i = 1; i <= n; i++)cin >> cen[i];
    for(int i = 1; i < n; i++)cin >> pod[i];
    int ma = 1e18 + 7 , ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans = max(ans , cen[i] - ma);
        if(i < n)
        {
            ma = min(ma + pod[i] , cen[i] + pod[i]);
        }
    }
    ma = 1e18 + 7;
    for(int i = n; i >= 1; i--)
    {
        ans = max(ans , cen[i] - ma);
        if(i > 0)
        {
            ma = min(ma + pod[i - 1] , cen[i] + pod[i - 1]);
        }
    }
    cout << ans;
    return 0;
}

Maksymilian Polikowski

2026-01-09T21:56:06+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 2

0

Dobra , wiem że trochę czasu minęło , ale jakby miało to kiedyś pomóc to wrzucam moim zdaniem najczyteniejszy kod ze wszytkich się tu znajdujących
(76 > 3)

Kopiuj

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> cen(n + 7) , pod(n + 7);
    for(int i = 1; i <= n; i++)cin >> cen[i];
    for(int i = 1; i < n; i++)cin >> pod[i];
    int ma = 1e18 + 7 , ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans = max(ans , cen[i] - ma);
        if(i < n)
        {
            ma = min(ma + pod[i] , cen[i] + pod[i]);
        }
    }
    ma = 1e18 + 7;
    for(int i = n; i >= 1; i--)
    {
        ans = max(ans , cen[i] - ma);
        if(i > 0)
        {
            ma = min(ma + pod[i - 1] , cen[i] + pod[i - 1]);
        }
    }
    cout << ans;
    return 0;
}