SPOJ- GLUTTON - Obżartuchy

Question

Witam, jesli ma ktos chwilke czasu, to prosilbym o przeanalizowanie mojego programu z zadania "Obżarciuchy" i o odpowiedzenie mi dla czego wyskakuje blędna odpowiedź w SPOJu, zdaje sobie sprawe, że kod pewnie mógłby być o wiele lepszy, ale dopiero sie ucze. Pozdrawiam :)

Tutaj jeszcze link do zadania: http://pl.spoj.com/problems/GLUTTON/

 

#include <iostream>
#include <cmath>

using namespace std;
short int n;
int m,t;  //t= proby m=ilosc w pudelku
double wynik; 
int main()
{
cin>>t;
{
    for(int i=1;i<=t;i++)
    {
        cin>>n>>m;
        int nm[n],wnm[n+1]; //nm Pierwszy czas, wnm kolejne czasy
        for(int u=1;u<=n;u++)
        {
            cin>>nm[u];
            if(u==1)wnm[u]=86400/nm[u];
            else if (u==n)
                {
                    wnm[u]=86400/nm[u]+wnm[u-1];
                    wynik=ceil(double(wnm[u])/m);
                }
             else wnm[u]=86400/nm[u]+wnm[u-1];
        }
    cout<<wynik<<endl;
   }

}
    return 0;
}

 

Answer 1

Cześć, może nie jestem ekspertem, ponieważ sam się ciągle uczę ale widzę to następująco:

1. Nie ma potrzeby deklarowania zmiennych typu double - typ int spokojnie pomieści maksymalną zadaną liczbę w tym zadaniu (tu było to 1 000 000 000), tym bardziej zmienna wynik, ponieważ wynik musi być typu całkowitego (nie możemy mieć 2,5 pudełka, tylko 3).

2. Przy testowaniu swojego programu nie ograniczaj się jedynie do wartości zadanych w przykładzie. Testuj również w oparciu o analizję wartości brzegowych (czyli zapodaj minimum oraz maksium możliwe w danym przykładzie).

I tutaj właśnie Twój kod się wykrzaczy. Ponieważ deklarując maksymalną ilość ciastek w pudełku, tzn 1 000 000 000 oraz maksymalny czas jedzenia jednego ciastka przez obżartucha (czyli 100 000) widać od razu, że obżartuch nie zdąży zjeść choćby jednego ciastka, a skończy mu się czas.

Więc ilośc zjedzonych przez niego ciastek w całości, wyniesie 0, na co Twój program zareaguje, że potrzeba 0 pudełek.

 

3. Twoje warunki mogą się nie sprawdzić również ilości obżartuchów n=1 (wartość brzegowa minimalna dla ilości obżartuchów), ponieważ wtedy spełni się warunek z if, więc automatycznie program ominie else if oraz else i zakończy się pętla, a pokazane na ekranie zostanie 0 (czyli domyślna wartość początkowa dla zmiennej wynik).

 

4. Nie ma potrzeby tworzenia aż dwóch tablic. Tzn można to zrobić ale muszą one mieć dokładnie taki sam rozmiar (czyli obydwie w rozmiarze n, a nie n oraz n+1).

 

Moja podpowiedź -> Zadeklaruj tablicę, do której poślesz już dla elementu 0 czas trwania dnia w sekundach podzielony przez długość jedzenia jednego ciastka, które zadasz chwile wczesniej w petli. Nastepnie ilosc zjedzonych ciastek sumuj i na koncu podziel ilość ciastek w pudełku przez tą sumę. Pamiętaj, że jeżeli reszta z dzielenia będzie różna od 0, będziesz musiał zwiększyć ilość potrzebnych pudełek o 1 <- ja tak zrobiłem i jest OK. Może znajdzie się ktoś z jeszcze "czystszym" kodem. Pozdrawiam.

Comments

OK tak zrobie, nie moge jednak zgodzić się z 2 pkt, ponieważ jesli obżarciuch nie zdąży zjesc ciastka przez cały dzien, to go wgl nie zacznie, więc zje 0 ciastek przy czasie 100000 sek.Chyba że coś źle zrozumialem.

---

Przy czasie 100000sek ruszy pierwsze ciastko ale go nie zje całego. Tak wiec zeby mógł je ruszyć w ogóle musi mieć choćby jedno pudełko z tymi ciastkami. Tak więc trzeba założyć, że minimalna ilość potrzebnych pudełek bez względu na to ile zjedzonych zostanie liczb całkowitych ciastek, wyniesie 1.

---

Zadanie rozwiązałem pozytywnie :) Wystarczylo dodać wyjątek, o ktorym mowiles w punkcie 3. Pozdrawiam i bardzo dziękuję za pomoc.