"Przeprowadzka" SPOJ - Błędna Odpowiedź

Question

Witam, napisałem taki oto kod: 

#include <iostream>

int main()
{
    short t;
    int n;
    short k;
    short a;
    long int b=0;
    long int c=1;
    long int d=0;
    std::cin>>t;
    for(int i=0;i<t;i++)
    {
        b=0;
        c=1;
        std::cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            std::cin>>a;
            b+=a;
        }
        d=k;
        if (b>d)
        {
            while (b>d)
            {
                d+=k;
                c++;
            }
        }
        else if (b==d)
        {
            std::cout<<c<<std::endl;
            continue;
        }
        else if (b==0)
        {
            std::cout<<0<<std::endl;
            continue;
        }
        std::cout<<c<<std::endl;
    }
    return 0;
}

Treść zadania: http://pl.spoj.com/problems/AL_02_05/

Wydaje mi się, że kod napisałem poprawnie, wiem, że mogę usunąć z jeden warunek porównujący i jedną pętle, ale na razie niech będą, bo nie zakłócają algorytmu, który napisałem. Wydaje mi się, że jest dobrze wszystko a mimo to dalej otrzymuje błędną odpowiedź. Czy ktoś mógłby rzucić okiem i dać mi jakąś wskazówkę gdzie może leżeć przyczyna problemu?

Pozdrawiam

Comments

Sam nie jestem zawansowany i jeszcze do tego zadania nie doszedłem  ale mam dla ciebie kilka rad jak na przyszłość bardziej zachecic innych by ci pomogli :

-  często cieżko wyczytać się z cudzego kodu wiec polecam pisać komentarze

- po drogie pamiętaj ze sędzia w spoju to jednak algorytm i problem czemu ci nie zalicza może być blachy , np brak endl w jakimś miejscu . Postaraj się jeszcze raz przeczytać uważnie treść zadania bo być może coś nie dopatrzyłes . Usuń tez te nie potrzebne  fragmenty kodu bo one tez mogą przeszkadzać w analizie zadanie przed sędziego ( często po refaktoryzacji okazuje się ze problem znika)

---

Racja, endliny mam chyba wszędzie, ciężko mi się dopatrzeć co jest nie tak. 

#include <iostream>
 
int main()
{
    short t;
    int n;
    short k;
    short a;
    long int b=0;
    long int c=1;
    long int d=0;
    std::cin>>t;
    for(int i=0;i<t;i++)
    {
        b=0;
        c=1;
        std::cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            std::cin>>a;
            b+=a;
        }
        d=k;
        while (b>d)
        {
            d+=k;
            c++;
        }
        if (b==0)
        {
            std::cout<<0<<std::endl;
            continue;
        }
        std::cout<<c<<std::endl;
    }
    return 0;
} 

Skróciłem kod do takiej formy, wiem, że bez komentarzy, ale późno już jest.

Answer 1

Twój algorytm jest niepoprawny. Zakładasz w nim, że jeden z przedmiotów może się znajdować w części w jednym pudełku, w części drugim. Przedmiotów nie możemy dzielić, poza tym mogą być  tylko dwa przedmioty w jednym pudle. Zwracam też uwagę, że linijki od 23 do 31 zawierają pętle, która jest tak naprawdę dzieleniem, zaokrąglonym do góry jeśli została reszta, lepiej użyć dzielenia zamiast powoli dodawac do d wartosc k. Oczywiscie nadal nie sprawi to ze algorytm bedzie poprawny

Podpowiedz do rozwiazania: trzeba wczytac przedmioty do tablicy, posortowac ja i pomyslec jaki jest najbardziej optymalny sposob wkladania przedmiotow do pudelek ( przydadza sie dwa wskazniki - jednym idziemy od konca, drugim od poczatku ).

Comments

Dobra, już zrozumiałem mój błąd i jest nawet bardziej poważniejszy niż mi rozpisałeś. Po prostu myślałem, że zmienna k oznacza pojemność jaką może przechować maksymalnie pudełko, zapomniałem o tym, że osobna informacja, że 2 przedmioty mogą być w pudełku też jest istotna.Czyli jak np. było 9 przedmiotów, pojemność pudełka wynosiła 30 a suma wagi tych dziewięciu przedmiotów wynosiła 29 to myślałem, że zmieszczę to do 1 pudełka... Czytanie ze zrozumieniem się kłania

Dzięki!