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

question-closed Najwiekszy Wspolny Dzielnik - SPOJ metoda rozkladu na czynniki

0 głosów
149 wizyt
pytanie zadane 16 lutego 2017 w C i C++ przez unbearable Początkujący (450 p.)
zamknięte 17 lutego 2017 przez unbearable

Witam!
Szukam chochlika, który powoduje zwracanie błędnej odpowiedzi przez spoj. Czas ok 0.4 sekundy czyli troche czasu do 1.0 s zostaje i komunikat spoj: "błedna odpowiedz"

http://pl.spoj.com/problems/PP0501A/

Funkcja  decay_a(int a,int b) rozklada liczbe a na czyniki pierwsze i wpisuje kolejne wartosci do tabeli int b od najmiejszej do najwiekszej.
Wszystkie przykłady z SPOJ program zwraca z poprawnymi wynikami, wszystki losowe wartosci porownywane z stroną internetową http://www.kalkmat.pl/?cnt=NWD&m=nwd&showcalc=true&type=factor&arg1=36&arg2=48 również zwraca identycznie. Gdzieś jednak siedzi chochlik czy ktoś z Was ma jakiś pomysł gdzie może być ?

int NWD = 1; // NWD = 1 bo mnożenie przez 0 = 0

int decay_one[12] = {0,0,0,0,0,0,0,0,0,0,0,0}; // tabela rozkladu na czyniki pierwszej liczby maks 12 bo 1*10^6(maks wynika z zadania) na czyniki = 12 cyfr
int decay_two[12] = {0,0,0,0,0,0,0,0,0,0,0,0}; // tabela rozkladu na czyniki pierwszej liczby maks 12 bo 1*10^6(maks wynika z zadania) na czyniki = 12 cyfr

   

decay_a(one,decay_one); // wpisanie rozkladu na czyniki pierwszej liczby do tabeli pierwszej
decay_a(two,decay_two); // wpisanie rozkladu na czyniki drugiej liczby do tabeli drugiej.

   

for(int i=0;i<12;i++) // szukanie czesci wspolnej w tabeli decay_one i decay_two...
    {
        for(int b=0;b<12;b++)
        {
            if(decay_one[i]==0 && decay_two[b]==0)
            {
                break;
            }
            if(decay_one[i]==decay_two[b])
            {
            NWD *=decay_one[i]; // mnożenie przez częśc wspolna
            decay_two[b] = 0; // wyzerowanie zeby nie pobierał kolejny raz tej wartosci.
            break;
            }
        }
    }


    cout << NWD << endl;

komentarz zamknięcia: Problem rozwiązany

2 odpowiedzi

0 głosów
odpowiedź 16 lutego 2017 przez playerony Pasjonat (15,220 p.)
Problem polaga prawdopodobnie na tym, że wszystko wykonujesz dla liczby testów równej jeden, a liczba ta powinna zostac podana przez użytkownika.
komentarz 16 lutego 2017 przez unbearable Początkujący (450 p.)
nie napisałem w sumie tego to jest wnetrze funkcji nwd która wykonuje się t razy.
0 głosów
odpowiedź 17 lutego 2017 przez unbearable Początkujący (450 p.)
Problem rozwiązany
Błędnie założyłem że rozkład miliona na czynniki odpowie na pytanie o wielkość tabeli. Najwięcej czyników ma natomiast liczba 2^19 która nadal jest mniejsza od miliona czyli mieści się w przedziale wynikajacym z zadania. Zmiana wielkości tabeli, oraz dostosowanie do tego forów naprawiło problem.

Podobne pytania

0 głosów
2 odpowiedzi 429 wizyt
pytanie zadane 16 listopada 2017 w C i C++ przez maciek45 Nowicjusz (120 p.)
0 głosów
1 odpowiedź 727 wizyt
pytanie zadane 6 marca 2017 w C i C++ przez styrczu Obywatel (1,050 p.)
0 głosów
3 odpowiedzi 657 wizyt
pytanie zadane 28 marca 2017 w C i C++ przez Kenzy Obywatel (1,160 p.)

89,082 zapytań

137,670 odpowiedzi

307,610 komentarzy

59,140 pasjonatów

Motyw:

Akcja Pajacyk

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

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...