Konkurs pseudomatematyczny - spoj zadanie

Question

Cześć!

Od paru godzin próbuję rozwiąć to zadanie -> https://pl.spoj.com/problems/MWPZ06H/

Problem polega na tym, że program zwraca wyniki poprawnie, ale na końcu tuż przed zakończeniem programu wypisuje się jakaś około 10 cyfrowa ujemna liczba, domyślam się, że problemem może być sformułowanie kodu między 89 a 99 linijką. Może jeszcze wytłumaczę mój kod bo jest dość dziwnie napisany(tak mi się wydaje).

Program działa mniej więcej w taki sposób(pominę te oczywiste instrukcje): Funkcja sortowanie_babelkowe sortuje w taki sposob liczby, że znajduje pierwszą największą i ustawia ją w szufladce zerowej, a reszte liczb sortuje porządku rosnącym(8-40 linia kodu), następnie sprawdza czy są jeszcze jakieś liczby równej tej w zerowej szufladce i zamienia miejscami tą kolejną liczbę największą z pierwszą szufladką z liczbą inną niż ta największa(85-95 linia kodu), następnie funkca kolejne_sortowanie_babelkowe sortuje wszystkie liczby które nie są tymi największymi(43-58 linia)

Oto kod

#include <iostream>
using namespace std;

int ile;
int k = 1;
int p;

void sortowanie_babelkowe(int *tab, int ile)
{
    for(int i = 0; i < ile; i ++)
    {
        if(i==(ile-1))
        {
            for(int j = ile - 1; j >= 1; j--)
            {
                if(tab[j] > tab[j-1])
                {
                    int bufor;
                    bufor = tab[j-1];
                    tab[j-1] = tab[j];
                    tab[j] = bufor;
                }
            }
        }

        else
        {
            for(int j = ile - 1; j >= 2; j --)
            {
                if(tab[j] < tab[j-1])
                {
                    int bufor;
                    bufor = tab[j-1];
                    tab[j-1] = tab[j];
                    tab[j] = bufor;
                }
            }
        }
    }
}


void kolejne_sortowanie_babelkowe(int *tab, int ile)
{
    for(int i = 1; i < ile; i ++)
    {
        for(int j = ile - 1; j >= k+1; j --)
        {
            if(tab[j] < tab[j-1])
            {
                int bufor;
                bufor = tab[j-1];
                tab[j-1] = tab[j];
                tab[j] = bufor;
            }
        }
    }
}


int main()
{
    cin >> p;

    for(int a = 0; a < p; a ++)
    {
        cin >> ile;

        int * tablica = new int [ile];

        for(int i = 0; i < ile; i ++)
        {
            cin >> tablica[i];
        }

        sortowanie_babelkowe(tablica, ile);

        /*
        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i] << " ";
        }
        */

        for(int i = 1; i < ile; i ++)
        {
            if(tablica[0]==tablica[i])
            {
                int m;
                m = tablica[i];
                tablica[i] = tablica[k];
                tablica[k] = m;
                k++;
            }
        }

        //cout << endl;

        /*
        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i] << " ";
        }
        */

        kolejne_sortowanie_babelkowe(tablica, ile);

        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i] << " ";
        }

        cout << endl;

        delete [] tablica;
    }

    return 0;
}

Z góry dzięki za pomoc!

Answer 1

Gdzieś wyjeżdżasz poza zakres tablicy, program się nie wiesza jak masz tabele większa od 2. Ale jest jeszcze jeden problem przy wejściu:

4
1 2 3 3

dostaje wynik:
3 1 3 2

Ja bym proponował użyć:

1. Sortowanie tablicy liczb (znaków).

#include<algorithm>

sort([nazwa_tablicy], [nazwa_tabilcy] + [liczba_elementów_do_posortowania]);

Wtedy masz posortowana tablice od najmniejszej do największej wartości. Potem od tylu sprawdzić ile jest takich samych cyferek i przerzucić je do przodu tablicy.

Jeszcze lepiej jakbyś się uczył używać vectora, jest łatwiejszy w obsłudze niż tablice i ma dużo przydatnych funkcji jak np. size() która zwraca długość tablicy przez co nie wychodzi się poza zakres jak w twoim przypadku.

Comments

Dzięki za pomoc, poprawiłem kod i wydaje mi się, że wszystko jest już w porządku, ale spoj nadal twierdzi, że odpowiedzi są błędne

Kod

#include <iostream>

using namespace std;

int ile;
int k = 1;
int p;

void sortowanie1(int *tab, int ile)
{
    for(int i = 1; i < ile; i ++)
    {
        for(int j = ile - 1; j >= 1; j --)
        {
            if (tab[j] > tab[j-1])
            {
                int bufor;
                bufor = tab[j-1];
                tab[j-1] = tab[j];
                tab[j] = bufor;
            }
        }
    }
}

void sortowanie2(int *tab, int ile)
{
    for(int i = 1; i < ile; i ++)
    {
        for(int j = ile - 1; j > k; j --)
        {
            if (tab[j] < tab[j-1])
            {
                int bufor;
                bufor = tab[j-1];
                tab[j-1] = tab[j];
                tab[j] = bufor;
            }
        }
    }
}

int main()
{
    cin >> p;

    for(int a = 0; a < p; a ++)
    {
        cin >> ile;

        int *tablica = new int [ile];

        for(int i = 0; i < ile; i ++)
        {
            cin >> tablica[i];
        }

        /*
        wypisanie nieposortowanych wynikow
        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i] << " ";
        }
        */

        sortowanie1(tablica, ile);

        /*
        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i] << " ";
        }
        */

        for(int i = 1; i < ile; i ++)
        {
            if(tablica[i] == tablica [0])
            {
                k++;
            }
        }

        sortowanie2(tablica, ile);

        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i];
        }

        cout << endl;

        delete [] tablica;
    }

    return 0;
}

 

---

Zauważyłem, że ten poprawiony kod też zwracał błędną odpowiedź przy kombinacji

3

5

12345

5

45235

6

452355 (tu zwracał 555423, a powinno byc 555234)

Więć poprawiłem go

#include <iostream>

using namespace std;

int ile;
int k;
int p;

void sortowanie1(int *tab, int ile)
{
    for(int i = 1; i < ile; i ++)
    {
        for(int j = ile - 1; j >= 1; j --)
        {
            if (tab[j] > tab[j-1])
            {
                int bufor;
                bufor = tab[j-1];
                tab[j-1] = tab[j];
                tab[j] = bufor;
            }
        }
    }
}

void sortowanie2(int *tab, int ile)
{
    for(int i = 1; i < ile; i ++)
    {
        for(int j = ile - 1; j > k; j --)
        {
            if (tab[j] < tab[j-1])
            {
                int bufor;
                bufor = tab[j-1];
                tab[j-1] = tab[j];
                tab[j] = bufor;
            }
        }
    }
}

int main()
{
    cin >> p;

    for(int a = 0; a < p; a ++)
    {
        cin >> ile;

        int *tablica = new int [ile];

        //int *tablica = new int [ile];

        for(int i = 0; i < ile; i ++)
        {
            cin >> tablica[i];
        }

        /*
        wypisanie nieposortowanych wynikow
        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i] << " ";
        }
        */

        sortowanie1(tablica, ile);

        /*
        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i] << " ";
        }
        */

        k = 1;
        for(int i = 1; i < ile; i ++)
        {
            if(tablica[i] == tablica [0])
            {
                k++;
            }
        }

        sortowanie2(tablica, ile);

        for(int i = 0; i < ile; i ++)
        {
            cout << tablica[i];
        }

        cout << endl;

        delete [] tablica;
    }


    return 0;
}