Błąd wykonanie programu.

Błąd wykonanie programu.
pattom
PA
pattom
PA
  • Rejestracja:ponad 6 lat
  • Ostatnio:ponad 5 lat
  • Postów:83
0

Cześć,

mam takie zadanie:
http://solve.edu.pl/contests/download_desc/2096

i taki kod:

Kopiuj
#include <bits/stdc++.h>
using namespace std;

long long int tab2[200005];
int main ()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	
        long long int INF=1e9;
        tab2[0]=0;
        for (int i=1; i<=200005; i++)
        {
                tab2[i]=INF;
        }
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
                long long int a;
                cin>>a;
                for (int j=200005; j>=0; j--)
                {
                        if(tab2[j]!=INF)
                        {
                                tab2[j+a]=min(tab2[j]+1, tab2[j+a]);
                        }
                }
        }
     
        for (int i=0;i<200005;i++){
		if (tab2[i]==INF){
			cout<<i;
			return 0;
		}
	}

}

5 testów przechodzi a potem pokazuje mi błąd wykonania i nie wiem dlaczego :-(
Może ktoś widzi błąd?

edytowany 1x, ostatnio: kq
PA
a co zostało zmienione bo nie widzę ?
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
MarekR22
MarekR22
MarekR22
MarekR22
Moderator C/C++
  • Rejestracja:ponad 17 lat
  • Ostatnio:minuta
1

Bez patrzenia w treść, błędy:

  1. i<=200005
  2. int j=200005
  3. tab2[j+a] gdy tymczasem możesz mieć takie wartości j=200005 a=100000000000
Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 3x, ostatnio: MarekR22
Zobacz pozostałe 3 komentarze
MarekR22
problem jest prosty jak konstrukcja cepa, dlatego nie dam ci gotowca, bo inaczej niczego się nie nauczysz. Hint: Jaki jest dozwolony zakres indeksów tablicy? Jaki jest zakres a (AKA Ti)?
PA
zakres long long int - od -9'223'372'036'854'775'808 do 9'223'372'036'854'775'807
MarekR22
Eeee? Przeczytałeś treść zadania? Co to ma do indeksów tablicy?
MarekR22
a jaki masz zakres tablicy? jakie indeksy możesz tam użyć? od 0 do 200004!!!! Punktach 1 i 2 wskazuje, że używasz indeksu 200005, a w punkcie 3 twój kod używa indeksów daleko daleko poza dozwolonym zakresem.
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
pattom
PA
pattom
PA
  • Rejestracja:ponad 6 lat
  • Ostatnio:ponad 5 lat
  • Postów:83
0

Niestety nie mam pomysłu jak to zmienić:(
Nie wiem jak sobie poradzić z tym, że wychodzę poza tablice:(

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
au7h
au7h
au7h
au7h
  • Rejestracja:ponad 11 lat
  • Ostatnio:około rok
  • Postów:215
0

long long int tab2[200005];

pierwszy element tablicy ma index 0, ostatni 200004

Kopiuj
#include <bits/stdc++.h>
using namespace std;

long long int tab2[200005];
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
        long long int INF=1e9;
        tab2[0]=0;
        for (int i=0; i<200005; i++)
        {
                tab2[i]=INF;
        }
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
                long long int a;
                cin>>a;
                for (int j=200004; j>=0; j--)
                {
                        if(tab2[j]!=INF)
                        {
                                tab2[j+a]=min(tab2[j]+1, tab2[j+a]);
                        }
                }
        }

        for (int i=0;i<200005;i++){
        if (tab2[i]==INF){
            cout<<i;
            return 0;
        }
    }

}
edytowany 1x, ostatnio: au7h
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
pattom
PA
pattom
PA
  • Rejestracja:ponad 6 lat
  • Ostatnio:ponad 5 lat
  • Postów:83
0

Mam takie monety 2 1 1 10 9 sortuję żeby mieć 1 1 2 9 10. Zatem program rozpatruje monety po kolei 1 1 2 9 10.

Monety: 1 1 mogę wydać nimi kwoty 0, 1, 2. Ale 3 jeszcze nie umiem wydać (może będzie się dało po rozpatrzeniu kolejnych monet).
Rozpatruję zatem kolejną monetę, czyli 2.
Jeśli do tej pory umiałem wydać 0, 1, 2, to teraz umiem wydać 0, 1, 2 oraz dodatkowo 0+2, 1+2, 2+2, czyli łącznie 0, 1, 2, 3, 4.
OK, idę dalej.
Załóżmy że przeszedłem już przez monety 1 1 2. Wiem że da się wydać kwoty 0, 1, 2, 3, 4, ale 5 jeszcze nie umiem wydać.
Rozpatruję kolejną monetę, czyli 9.
Co mi to daje? Potrafię wydać 0, 1, 2, 3, 4, ale teraz dodatkowo też 0+9, 1+9, 2+9, 3+9, 4+9, czyli razem 0, 1, 2, 3, 4, 9, 10, 11, 12, 13.
W tym momencie jestem już pewny że 5 nie będzie dało się nigdy wydać. Bo kolejne monety, które będę rozpatrywał, będą większe lub równe 9.
Stop. Zatem wynik to 5.

Jak to zapisać?

edytowany 1x, ostatnio: pattom
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
au7h
au7h
au7h
au7h
  • Rejestracja:ponad 11 lat
  • Ostatnio:około rok
  • Postów:215
1

Chyba tak to będzie :P

Kopiuj
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void sortFnct(int* tab, int x, int y);
void walk(int* tab);
void printVec(vector<int> vecToPrint);
int findValue(vector<int> vec);

int main()
{
    int tab[] = {2,1,1,10,9};
    sortFnct(tab, 0, 5);
    walk(tab);
    
    return 0;
}

void sortFnct(int* tab, int x, int y)
{
    int i, j, t, v;
    i = x;
    j = y;
    v = tab[x];
    do
    {
        while(v > tab[i]) i++;
        while(v < tab[j]) j--;
        if(i <= j)
        {
            t = tab[i];
            tab[i] = tab[j];
            tab[j] = t;
            i++;
            j--;
        }
    }
    while(i <= j);
    if(x < j) sortFnct(tab, x, j);
    if(i < y) sortFnct(tab, i, y);
}

void walk(int* tab)
{
    vector<int> kwoty;
    kwoty.push_back(0);
    
    kwoty.push_back(tab[0]);
    kwoty.push_back(tab[0]+tab[1]);
    
    for(int i=2;tab[i]<=9;i++){
        int size = kwoty.size();
        for(int j=0;j<size;j++){
            if(!(find(kwoty.begin(), kwoty.end(), kwoty[j]+tab[i]) != kwoty.end())){
                kwoty.push_back(kwoty[j]+tab[i]);
            }
        }
    }
    printVec(kwoty);
    int var = findValue(kwoty);
    cout<<"Solve="<<var<<endl;
}

void printVec(vector<int> vecToPrint)
{
    cout<<"Printing vector...\n";
    for(int i : vecToPrint)
        cout<<i<<endl;   
}

int findValue(vector<int> vec)
{
    int last = vec.size() - 1;
    int solve;
    for(int i=0;i<last;i++)
    {
        if(vec[i]!=i)
        {
            solve = i;
            break;
        }
    }
    return solve;
}
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
pattom
PA
pattom
PA
  • Rejestracja:ponad 6 lat
  • Ostatnio:ponad 5 lat
  • Postów:83
1

Mam tak:

Kopiuj
#include <bits/stdc++.h>
using namespace std;
long long int money[200005];
int main ()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for (int i=0; i<n; i++)
	{
		cin>>money[i];
	}
	sort (money, money+n);	
    if (money[0]>1){
        cout<<1;
    return 0;
    }
    
	long long wynik=money[0];
	for (int i=1; i<n; i++)
    {
	    if(money[i]>wynik+1) break;
	    else wynik+=money[i];
	} 
	cout<<wynik+1;
	
	
}
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.

Utwórz konto