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

Zadanie C++ - algorytmika

VPS Starter Arubacloud
0 głosów
755 wizyt
pytanie zadane 17 marca 2017 w Algorytmy przez Patryk Raźny Nowicjusz (120 p.)

Cześć, robię testowe zadania z OIG i mam problem z rozwiązaniem zadania: http://www.gla.eu.pn/dane/wydarzenie.pdf

Program poprawnie działa dla danych testowych, jednak przy sprawdzaniu w systemie OIG poprawną odpowiedź daje jedynie dla tych trzech przykładów. 

Mój kod:

#include <iostream>
using namespace std;
bool *visited;
short **tab;
int w,k=0;
int liczba;
void DFS(int v)
{
    visited[v] = true;

    liczba=v;
    for(int i=0;i<k;i++)
    if(tab[v][i]==1)
    for(int j=0;j<w;j++)
    if(tab[j][i]==-1 && visited[j]==false) DFS(j);
}

int main()
{
    cin>>w;
    visited = new bool[w];

    tab = new short*[w];
    for(int i=0;i<w;i++) tab[i] = new short[k];
    k=w;
    for(int i=0;i<w;i++)
        for(int j=0;j<k;j++)tab[i][j]=0;
    int a,b;
    for(int i=0;i<w;i++)
    {

        cin>>a;
        if(a!=0)
        {
            tab[a-1][i]=-1;
            tab[i][i]=1;
        }
    }
    int wersje[w];
    for(int i=0;i<w;i++) wersje[i]=-1;
    int licznik=0;
    bool is;
    cin>>a;
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<w;j++) visited[j]=0;
        cin>>b;
        b-=1;
        DFS(b);


        is=false;


        for(int j=0;j<=licznik;j++)
            if(wersje[j]==liczba) is=true;
        if(is==false)
        {
            licznik++;
            wersje[licznik-1]=liczba;
        }

    }

    cout<<licznik;



}

 

1 odpowiedź

+1 głos
odpowiedź 14 kwietnia 2017 przez d0n Mądrala (6,440 p.)
edycja 15 kwietnia 2017 przez d0n

Cześć,

 Nie zagłębiałem się za mocno w kod. Możliwe, że masz dobry pomysł na rozwiązanie (na pewno jest ciekawy), ale proponuję ci pewną alternatywę. To zadanie można łatwiej zrobić używając zbiorów rozłącznych (finding union). Jest to łatwy algorytm, ale jeśli będziesz mieć problem z jego zrozumieniem napisz do mnie, z chęcią pomogę.

EDIT: Jest prostsze rozwiązanie wykorzystujące tylko algorytm DFS, sorry za mieszanie w głowie. 

 Mam jeszcze jedną małą podpowiedź. Znacznie za dużo używasz dynamicznego alokowania pamięci. Nie wiem jak jest z OIG'iem, ale na OI'u i innych konkursach programistycznych w celu posiadania tablicy o nieznanej przed wykonaniem programu wielkości używa się klasy vector z STL'a. Polecam ci się z STL'em  zapoznać, bo upraszcza wiele spraw i trudniej jest popełnić błąd. Jeżeli odstrasza cię trochę składnia używana przy STL'u, to też z chęcią pomogę, bo jest to naprawdę proste i tylko na pierwszy rzut oka może wydawać się nie do ogarnięcia.

 Bardzo ważną rzeczą, której brakuje w twoim kodzie, są dwie funkcje, które zmniejszają czas operacji in/out i są podstawą do zadań algorytmicznych. Zawsze przy używaniu iostream'a jako dwie pierwsze instrukcje funkcji main pisz:
 

ios_base::sync_with_stdio( 0 );
cin.tie( 0 );

 

Sprawdzarka wyrzuci przekroczenie limitu czasu, nawet dla poprawnych rozwiązań, bez tych dwóch linijek. Zresztą w ogóle OIG'owe sprawdzarki ponoć są mocno wyśrubowane pod względem czasu i lepiej używać cstdio.
 

1
komentarz 14 kwietnia 2017 przez mokrowski Mędrzec (155,460 p.)
Poprawne sygnatury ios_base::sync_with_stdio(false) i cin.tie(nullptr) . W drugim przypadku może być inny wskaźnik równoważny nullptr (np. przed C++11 po prostu NULL).
komentarz 15 kwietnia 2017 przez d0n Mądrala (6,440 p.)
Użycie w cin.tie zera nie jest najgorszym pomysłem, na starym Mingw, już obsługujących c++11, nullptr nie działa, a z tego co mi się wydaje preprocessing zamieni literał 0 na nullptr albo NULL w zależności co jest obsługiwane. Pozwala się to pozbyć głupiego błędu, a sam program nie ucierpi. Oczywiście zgadzam się, że wypada uczyć się używać sygnatury poprawnie.
komentarz 15 kwietnia 2017 przez mokrowski Mędrzec (155,460 p.)
Tu nie chodzi o "hiperpoprawność". Nie na każdej platformie systemowej NULL == 0. Natomiast tylko dla NULL lub nullptr kompilator wykonuje odpowiednie operacje (np. związane z obsługą pamięci). Po prostu jeśli będą tam "wbite zera", robisz wyprawę do krainy "ciekawe czy będę miał szczęście i będzie działało" :-) W większości przypadków oczywiście trafisz (GNU/Linux, MS Windows)... ale już przy mikrokontrolerach może być spore zdziwienie.Dobra.. to i tak szczegół ale czasem ważny :-)

Podobne pytania

0 głosów
1 odpowiedź 373 wizyt
pytanie zadane 25 lipca 2017 w Algorytmy przez Krzysztof Sękowski Nowicjusz (200 p.)
0 głosów
2 odpowiedzi 430 wizyt
pytanie zadane 22 lipca 2017 w Algorytmy przez Krzysztof Sękowski Nowicjusz (200 p.)
0 głosów
1 odpowiedź 295 wizyt
pytanie zadane 14 stycznia 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 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

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...