Wydawanie reszty – program zwraca prawidłowe wyniki, ale sprawdzarka nie akceptuje kodu

0

Pomocy! :) Pisze program, który wczyta nominały dostępnych monet i sprawdzi, czy używając dowolnej liczby monet podanych nominałów, da się wydać kwotę S. W pierwszej linijce wejścia znajduje się liczba różnych nominałów n (1 ≤ n ≤ 1000). W drugiej linii znajdują się liczby 1 ≤ s[i] ≤ 1000. Liczba s[i] oznacza wartość i-tej monety. W ostatniej linii znajduję się kwota do wydania S (0 ≤ S ≤ 10000). Program ma napisać TAK, jeśli wydanie kwoty S jest możliwe, lub słowo NIE, jeśli wydanie kwoty S nie jest możliwe.
Napisałem taki kod

#include <iostream>

using namespace std;

int main()
{
    int n, S, S1, i,p;


    cin >> n; // liczba dostępnych nominałów
    int *s= new int [n];

    for (i=0; i<n; ++i)
    cin >> s[i]; // wpisuje wartości nominałów

    
    cin >> S; // podaje resztę do wydania


    for (i=0; i<n; ++i)
    {
        if (S ==0) {break;} 
        else if (S >= s[i])  //sprawdzam czy mozna wydac danym nominalem
        {

           p=S / s[i];   //ile razy wydac dany nominal
           S=S-(s[i]*p); //zmniejszam reszte o wydany nominal
        }

    }

   S1 = S;

        if (S1!=0) {

                cout << "NIE"; } // jeśli reszta na koniec różna od zera, nie udało sie wydać reszty

            else {

                cout <<"TAK";} // jeśli reszta na koniec równa zeru reszta została wydana


    delete [] s;
    return 0;
}

program nawet sie kompiluje i dla testowych wyników podaje poprawnie TAK lub NIE, ale w sprawdzaczce kilku testów nie przechodzi, dłubie w tym i nie mam już pomysłu co jest nie tak, macie jakiś pomysł, o czym mogłem zapomnieć lub co w nim jest źle? Z góry dzięki za sugestie :)

0

Przemyśl ten algorytm, załóżmy, że mam monety o nominale 3 i 7, mam wydać 20. Jeśli, u Ciebie pierwsza na liście będzie moneta o nominale 3, to: 20 / 3 = 6, 6 * 3 = 18, 20 - 18 = 2, i w następnym obiegu pętli S < s[i] i dostaję komunikat, że się nie da. A tymczasem, 7 + 7 + 3 + 3 = 20. Ciekawe czy posortowanie listy wystarczy(wydaje mi si, że tak), i jak to się będzie miało do złożoności czasowej?

0

Jak S = 10, a s[I] = 8, to p = 10/8= 1 I S po drugiek linijce zmniejszy sie o 1, a Nie jak powinno o 2. Edit: bez sensu. Moze szybszy sort?

0

Poprxedni post Nie ma sensu. Nominaly posortowane, S=20, non: 6, 4. U Ciebie, 3*6= 18 I fail. Tymczasem 20= 6 +6+4+4, sukces. Czyli potrzebne Jakies dynamic programming: Sprawdzic czy pasuje wypelnic najwieksza, jak Nie to odjac ja raz I od nowa probowac rekurencyjnie.

0
lion137 napisał(a):

Przemyśl ten algorytm, załóżmy, że mam monety o nominale 3 i 7, mam wydać 20. Jeśli, u Ciebie pierwsza na liście będzie moneta o nominale 3, to: 20 / 3 = 6, 6 * 3 = 18, 20 - 18 = 2, i w następnym obiegu pętli S < s[i] i dostaję komunikat, że się nie da. A tymczasem, 7 + 7 + 3 + 3 = 20. Ciekawe czy posortowanie listy wystarczy(wydaje mi si, że tak), i jak to się będzie miało do złożoności czasowej?

Posortowanie nie wystarczy.

Przykład:

Kwota do wydania 9, mamy nominały 7 i 3.

0

Hm, rzeczywiście coraz więcej przykładów potwierdza, ze tym sposobem to nie zadziała. Podjarałem się, że wyszło na kilku testach, a problem jednak bardziej złożony. Znalazłem coś takiego https://pl.wikipedia.org/wiki/Problem_wydawania_reszty#Algorytm_z_wykorzystaniem_programowania_dynamicznego popróbuje wieczorem, może to zahula :)

0

Algorytm programowania dynamicznego z Wikipedii zadziałał idealnie, tak więc zadanie wykonane, dziękuję za wszystkie sugestie i wskazówki :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1