Zadanie Centrala Telefoniczna OIG

Question

Cześc przerabiam właśnie zadanie z 3 etapu OIG-a link szkopul:

https://szkopul.edu.pl/problemset/problem/ocGBMr4-sFMy6iEUQ6cZ6gNW/site/?key=statement

Wydaje mi się to zadanie dość proste, jednak dostaję dla wszystkich testów oprócz tych testowych 0pkt.

Dla każdego wielokąta obliczam pitagorasem maksymalny promień wszystkich wierzchołków(minimalny promień, aby pokryć cały wielokąt) Sortuję ję i sprawdzam cene biorąc pod uwagę elementy składające się z 1 potem 1,2 potem 1,2,3 domów itd i biorę mina. Wiem, że moja aktualna złożonnośc to kwadratowa i mogę przyśpieszyć do O(1) liczenie sumy zysku wszystkich nagród sumami prefiksowymi. Jednak narazie chcę zrobić, żeby algorytm działał.

Mój kod:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Wielokat
{
    long long nagroda;
    long long potrzebny_promien;

    bool operator < (const Wielokat&wielokat) const
    {
        return potrzebny_promien < potrzebny_promien;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n = 0;
    int k = 0;
    int wczytana_nagroda = 0;
    int wczytana_liczba_wierzcholkow = 0;
    long long wczytane_x = 0;
    long long wczytane_y = 0;
    double min_promien = 0;
    double odleglosc = 0;
    long long max_zysk = 0;
    long long zysk = 0;
    long long zasieg = 0;
    vector<Wielokat> wielokaty;

    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba_wierzcholkow >> wczytana_nagroda;
        min_promien = 0;

        for (int j = 0; j < wczytana_liczba_wierzcholkow; ++j)
        {
            cin >> wczytane_x >> wczytane_y;
            odleglosc = sqrt(pow(wczytane_x,2) + pow(wczytane_y,2));
            min_promien = max(min_promien,odleglosc);
        }
        wielokaty.push_back({wczytana_nagroda,ceil(min_promien)});
    }

    sort(wielokaty.begin(),wielokaty.end());

/*
    for (auto i : wielokaty)
    {
        cout << "Nagroda: " << i.nagroda << " potrzebny promien: " << i.potrzebny_promien << endl;
    }
    cout << endl;
    */



    for (int i = 0; i < n; ++i)
    {
        // Najpierw zlozonnosc kwadratowa dla testu czy ok, potem easy do logarytmicznej.
        zysk = 0;
        for (int j = 0; j <= i; ++j)
        {
            zysk += wielokaty[j].nagroda; // Tu mozna sumy prefiksowe.
        }

        if (wielokaty[i].potrzebny_promien % k != 0)
        {
            zasieg = (wielokaty[i].potrzebny_promien / k) * k + k;
        }
        else
        {
            zasieg = wielokaty[i].potrzebny_promien;
        }
        long long ile_razy_zwiekszyc = zasieg / k;
        long long koszt_utrzymania = (0 + ile_razy_zwiekszyc-1) * (ile_razy_zwiekszyc) / 2; // Suma ciagu od 0 do ile_razy_zwiekszyc -1

        zysk -= koszt_utrzymania;
        cout << "Koszt utrzymania: " << koszt_utrzymania << endl;
        cout << "Potrzebny zasieg: " << zasieg << endl;
        cout << "Zysk: " << zysk << endl;
        cout << endl;

        max_zysk = max(max_zysk,zysk);
    }
    cout << max_zysk;
    return 0;
}

Z góry dziękuję za wszystkie odpowiedzi!

Answer 1

W linii 15 masz zły warunek

Comments

No tak głupi błąd. Tak to wszystko okej. Powinno być: return: potrzebny_promien < wielokat.potrzebny_promien.

Dzięki!

---

to jak tam idzie nauka o F&U? :)

---

Już rozumiem o co chodzi. Dasz jakąś wskazówkę do zastosowania F&U w zadaniu warsztaty? Co ma być findem a co unionem.

---

Nie bardzo rozumiem pytanie. F&U pozwala po prostu szybko łaczyć 2 grupy w jedną, więc jak w tym moim pierwszym pomyśle trzymałem auta tego samego koloru w vectorze to teraz wszystkie auta tego samego koloru muszą mieć tego samego lidera

---

@Whistleroosh, 

Tak swoją drogą i tak muszę napisać ten kod z F&U dla poćwiczenia, ale nie uwierzysz, że znalazłem rozwiązanie tamtego zadania w 4 linijkach kodu xD. Wyślę ten kod pod postem z tamtym zadaniem, żeby nie robić śmietniku. Jak byś zrozumiałt to możesz wytłumaczyć.

---

@Whistleroosh, A ok

---

Jak ktoś kiedyś by potrzebował to wrzucam już kod dający 100pkt z sumami prefiksowymi:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Wielokat
{
    long long nagroda;
    long long potrzebny_promien;

    bool operator < (const Wielokat&wielokat) const
    {
        return potrzebny_promien < wielokat.potrzebny_promien;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n = 0;
    int k = 0;
    int wczytana_nagroda = 0;
    int wczytana_liczba_wierzcholkow = 0;
    long long wczytane_x = 0;
    long long wczytane_y = 0;
    double min_promien = 0;
    double odleglosc = 0;
    long long max_zysk = 0;
    long long zysk = 0;
    long long zasieg = 0;
    long long poprzednia_suma = 0;
    vector<Wielokat> wielokaty;

    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba_wierzcholkow >> wczytana_nagroda;
        min_promien = 0;

        for (int j = 0; j < wczytana_liczba_wierzcholkow; ++j)
        {
            cin >> wczytane_x >> wczytane_y;
            odleglosc = sqrt(pow(wczytane_x,2) + pow(wczytane_y,2));
            min_promien = max(min_promien,odleglosc);
        }
        wielokaty.push_back({wczytana_nagroda,ceil(min_promien)});
    }

    sort(wielokaty.begin(),wielokaty.end());

    for (int i = 0; i < n; ++i)
    {
        zysk = poprzednia_suma + wielokaty[i].nagroda;

        if (wielokaty[i].potrzebny_promien % k != 0)
        {
            zasieg = (wielokaty[i].potrzebny_promien / k) * k + k;
        }
        else
        {
            zasieg = wielokaty[i].potrzebny_promien;
        }
        long long ile_razy_zwiekszyc = zasieg / k;
        long long koszt_utrzymania = (ile_razy_zwiekszyc-1) * (ile_razy_zwiekszyc) / 2; // Suma ciagu od 0 do ile_razy_zwiekszyc -1

        zysk -= koszt_utrzymania;

        max_zysk = max(max_zysk,zysk);
        poprzednia_suma += wielokaty[i].nagroda;
    }
    cout << max_zysk;
    return 0;
}