Randka w ciemno - zadanie main2

0

Witam.
Piszę, gdyż program, który napisałem do zadania Randka w ciemno - https://main2.edu.pl/c/kurs-podstaw-algorytmiki-druga-e/p/ran/, w znacznej większości testów daje zły wynik.
Prosiłbym kogoś o pomoc, ponieważ nie mam pojęcia co działa nieprawidłowo.

#include<cstdio>
#include <algorithm>

int n,s;
using namespace std;
bool Szukanie(int q,int s,int liczba[],int &wynik1,int &wynik2)
	{
		int j=1;
		for(int i=0;i<q;i++)
		{
			while((j>i+2)&&(liczba[i]+liczba[j]>s))
				{
				j--;
				}
			while((j<q)&&(liczba[i]+liczba[j]<s))
				{
				j++;
				}
			if(liczba[i]+liczba[j]==s)
				{
				wynik1=i;
				wynik2=j;
				return 1;
				}
		}
		return 0;
	}

void Sortowanie(int porzad[],int liczba[], int left, int right )
{
    int i = left;
    int j = right;
    int x = liczba[( left + right ) / 2 ];
    while( i <= j )
    {
        while( liczba[i] < x )
             i++;
        
        while( liczba[j] > x )
             j--;
        
        if( i <= j )
        {
            swap( liczba[i], liczba[j] );
            swap( porzad[i], porzad[j]);
            i++;
            j--;
        }
    }
    
    if( left < j ) Sortowanie(porzad,liczba,left,j);
    
    if( right > i ) Sortowanie(porzad,liczba,i,right);
    
}

int main()
{
    scanf("%d %d",&n,&s);
    char imie[n][10];
    int porzad[n];
    int liczba[n];
    int wynik1,wynik2;
    for(int i=0;i<n;i++)
    {
    	scanf("%s %d",&imie[i],&liczba[i]);
		porzad[i]=i;
	}
	Sortowanie(porzad,liczba,0,n-1);
	bool praw=Szukanie(n-1,s,liczba,wynik1,wynik2);
	if(praw==1)
	{
	for(int i = 0; imie[porzad[wynik1]][i] != 0; ++i)
		printf("%c",imie[porzad[wynik1]][i]);
	printf(" ");
	for(int i = 0; imie[porzad[wynik2]][i] != 0; ++i)
		printf("%c",imie[porzad[wynik2]][i]);
	}
	else
    	printf("NIE\n");
	return 0;
}
0

Ja bym chyba użył std::map

1

A ja struktury i 2 tablic dla liczb parzystych i nieparzystych. Skoro wylosowana liczba zawsze jest nieparzysta, to znaczy że potrzebujemy po jednej osobie z każdej (2 parzyste lub 2 nieparzyste liczby naturalne zawsze dają parzystą sumę,więc nie ma co sprawdzać takich kombinacji) . Do tego szukanie binarne.

0

W najprostszej wersji wystarczy wczytać wszystkie liczby do jednej tablicy, posortować korzystając z std::sort(), a potem lecieć w pętli i dla każdej liczby poszukać binarnie odpowiednika korzystając np. z std::lower_bound(). Nieparzysta suma gwarantuje, że nie będzie sytuacji, że odpowiednikiem jakiejś liczby jest ona sama.

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