• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Centrala Telefoniczna OIG

VPS Starter Arubacloud
0 głosów
334 wizyt
pytanie zadane 21 kwietnia 2022 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 21 kwietnia 2022 przez pasjonat_algorytmiki

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!

1 odpowiedź

+1 głos
odpowiedź 22 kwietnia 2022 przez Whistleroosh Maniak (56,980 p.)
wybrane 17 lutego 2023 przez pasjonat_algorytmiki
 
Najlepsza
W linii 15 masz zły warunek
komentarz 22 kwietnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No tak głupi błąd. Tak to wszystko okej. Powinno być: return: potrzebny_promien < wielokat.potrzebny_promien.

Dzięki!
komentarz 22 kwietnia 2022 przez Whistleroosh Maniak (56,980 p.)
to jak tam idzie nauka o F&U? :)
komentarz 22 kwietnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Już rozumiem o co chodzi. Dasz jakąś wskazówkę do zastosowania F&U w zadaniu warsztaty? Co ma być findem a co unionem.
komentarz 22 kwietnia 2022 przez Whistleroosh Maniak (56,980 p.)
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
1
komentarz 22 kwietnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@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ć.

komentarz 22 kwietnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@Whistleroosh, A ok

komentarz 22 kwietnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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;
}

 

Podobne pytania

0 głosów
0 odpowiedzi 140 wizyt
pytanie zadane 10 października 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
0 odpowiedzi 506 wizyt
pytanie zadane 16 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
2 odpowiedzi 411 wizyt
pytanie zadane 28 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,830 zapytań

141,771 odpowiedzi

320,817 komentarzy

62,159 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...