12230. Napój Jasia [AL_01_01]

[przemek625]

Zastanawiam się jak rozwiazać to zadanie aby zmieścić się w czasie. Wpadłem na pomysł aby dane z drugiej i trzeciej lini wstawic do tablic. Następnie posortować te tablicę. Jak na razie tyle, nad resztą myślę. Może jakieś podpowiedzi? Czy sortowanie jest tutaj dobrym pomysłem?

[narbej]

Jak najbardziej tak, to chyba dobry pomysł, bo bez sortowania jak? Ale myśl, nie będę przeszkadzał i naprowadzał, bo może można inaczej, lepiej i szybciej i łatwiej?

PS
Abstrachując od tego zadania. Jak powstają wielkie i genialne pomysły? Wszyscy wiedzą, że nie da się zrobić w ten sposób i przychodzi ktoś, kto o tym nie wie i robi w właśnie w ten sposób, o którym przecież wszyscy wiedzieli, że ... .

[przemek625]

Wymyśliłem! Ale przepraczam limit czasu :(!

wag1-pierwszy składnik
wag2-drugi składnik
zapytanie czyli ta konkretna porporcja nutelii i mleka.
szukane- to taga wag2, że wag1+wa2=zapytanie.

Program dział tak:

wczytuje dane, sortuje 3 linie wejścia(wag2) i binarnie wyszukuje w wag2 dla każdego w wag1 takiej liczby szukane, że dadzą obie sumie zapytania(czyli te odpowiednie proporcje wa obu składników o które pyta Jaś). Jeśli znajdzie to przerywa pętlę i wybiera kolejne zapytanie. Czyli jeśli takiej proporcja nie iestnieje to musi przelecież po kolei cały wektor wag1

Do głowy przychodzi mi jeszcze cos takie aby liczbę i wstawiać na i-te miejsce w tablicy. Zrobiłbym tylko tak dla wag2. wag1 byłąby normalną nieposortowana tablicą. Wtedy wystarczyłoby obliczyć ile należy dodać do i-tego elementu z wag1 aby otrzymać proporcje i odwołać się do j-tego miejsca w tablicy wag2. Tym samym jeśli wag1,wag2 maja po n elementów to i-ty element wag1 sprawdza tylko czy pasuje do jednego elementu, a nie jak poprzednio do n elementów.

Weźmy przykład, bo to prościej zrozumieć. Dane przykładowe z treści:

wag1: 6 3 2 5 2
wag2: 7 4 1 6 8
zapytania:
15
14
5
4
9

Czyli wag(7)=7, wag(4)=4, itd. Natmiast wag(2)=0, wag(9)=0 - bo takie elementy nie pojawiły siena wejściu.

Bierzemy teraz wag1(0)=6, zapytanie(0)=15, szukane=15-9. Sprawdzamy, czy wag(9)==9. Nie jest to prawda. Podobnie dla wag(1),wag(2)... Dla zapytania(15) akurat nie znajdziemy.

Poniżej kod STAREGO ROZWIAZANIA, które nie mieście sie w limicie:smile:

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

using namespace std;

void wczytaj(vector<int> &b);

int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> wag1(n);
    vector<int> wag2(n);
    vector<int> zapytania(m);
    vector<string> odp;

    wczytaj(wag1);
    wczytaj(wag2);
    wczytaj(zapytania);

    sort(wag2.begin(),wag2.end());

    for(int i=0;i<m;i++)
    {

        for(int k=0;k<n;k++)
        {

            int szukane=zapytania[i]-wag1[k];
            if(binary_search(wag2.begin(),wag2.end(),szukane))
               {
                   odp.push_back("TAK");
                   break;
               }
              else if(!binary_search(wag2.begin(),wag2.end(),szukane) && k==n-1)
              {
                  odp.push_back("NIE");
              }
    }
    }

    for(int i=0;i<odp.size();i++)
    {
        cout<<odp[i]<<endl;
    }

}

void wczytaj(vector<int> &b)
{
    for(int i=0;i<b.size();i++)
    {
        int liczba;
        cin>>liczba;
        b[i]=liczba;

    }
}

[narbej]

Twój ostatni pomysł jest raczej niewykonalny. Nawet jak użyjesz tablicy bool to i tak jej nie zmieścisz, ale możesz spróbować. Mimo, że elementów jest nie więcej niż 10^4 to wartości są z zakresu < 2^31 = 2147483648. Lepiej jest więc użyć wcześniejszego sposobu.
Pomyś, co się stanie, gdy np poszukujesz sumy = 15. Z pierwszej tablicy wybierasz kolejne, a potem szukasz binarnie w drugiej wagi = suma - waga1[i]
Co będzie gdy waga1[i] >= 15? W twoim programie nie ma to znaczenia. Dalej będziesz szukał ujemnej [lub zerowej] wagi w drugim ciągu. A jeżeli w pierwszym ciągu tagich wag, już większych od szukanej jest więcej? Więc może warto i ten ciąg posortować i przy pierwszej wadze1[i] >= szukana przerwać pętlę? Więcej można uwzględnić, że w drugim ciągu istnieje najmniejsza waga > 0 i ten fakt dodatkowo uwzględnić? Zamiast wyszukiwania binarnego, można jednocześnie [na zmianę] "poruszać" się po obu ciągach ale w odwrotnych kierunkach. Wtedy dodatkowo może warto też posortować jeszcze też ostatni ciąg, ciąg zapytań [ale po indeksach, aby powrócic do jego wersji nie posortowanej]. Możliwe, że jeszcze nie jest to dla Ciebie zupełnie jasne, więc raczej nie pytaj, a wróć do tego postu za jakiś czas, bo chciałbym abyś do rozwiązania doszedł w jak największym stopniu w miarę możliwości samodzielnie.

[przemek625]

Zmodyfikowałem swój program i nadal nie przechodzi testów

Dodałem linijkę sprawdzającą

if( zapytania[i] < wag1[k] && k==n-1 )
            {
               odp.push_back("NIE");
               break;

            }

            if(zapytania[i] < wag1[k] && k!=n-1)
            {
                continue;
            }

Czyli jeśli po prostu szukane < 0 to nie przerywam pętlę.

int szukane=zapytania[i]-wag1[k];

Cały kod:

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

using namespace std;

void wczytaj(vector<int> &b);

int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> wag1(n);
    vector<int> wag2(n);
    vector<int> zapytania(m);
    vector<string> odp;

    wczytaj(wag1);
    wczytaj(wag2);
    wczytaj(zapytania);

    sort(wag2.begin(),wag2.end());
    sort(wag1.begin(),wag1.end());

    for(int i=0;i<m;i++)
    {

        for(int k=0;k<n;k++)
        {

            int szukane=zapytania[i]-wag1[k];
            int szukane2=zapytania[i]-wag2[k];

            if(szukane<=0 || szukane2<=0)
            {
                odp.push_back("NIE");
                break;
            }

            bool exist=binary_search(wag2.begin(),wag2.end(),szukane);
            bool exist2=binary_search(wag1.begin(),wag1.end(),szukane2);

            if(exist || exist2)
               {
                   odp.push_back("TAK");
                   break;
               }
              else if((!exist || !exist2) && k==n-1)
              {
                  odp.push_back("NIE");
              }
    }
    }


    for(int i=0;i<odp.size();i++)
    {
        cout<<odp[i]<<endl;
    }
}


void wczytaj(vector<int> &b)
{
    for(int i=0;i<b.size();i++)
    {
        int liczba;
        cin>>liczba;
        b[i]=liczba;

    }
}

[narbej]

No, ok, a jak brzmi pytanie? Jeżeli chodzi o twój, post wyżej, aktualny kod, to nie jest to to, co Ci podpowiedziałem.

[przemek625]

Jaka złożoność obliczeniowa powinna być tego rozwiązania? Wydaje mi się, że wyszukiwanie binarne w ogóle nie sprawdzi się tutaj, bo już przekobinowałem te zadanie. A w sumie to się już zapętliłem

Więcej można uwzględnić, że w drugim ciągu istnieje najmniejsza waga > 0 i ten fakt dodatkowo uwzględnić?

Tego nie rozumiem, może jakis przykład?

[narbej]

Taki [przekombinowany, przykład, aby wyjaśnić o co mi chodziło:
w1 posortowane:
2 4 6 8 10 16 17 18 20 21 itd
w2 posortowane:
8 10 12 14 16 .... 17 21 31 itd

Szukamy wagi 17.
Wg twojej metody [pierwszej metody - drugiej nie analizowałem], wybierasz po kolei kolejne wartości z w1 i sprawdzasz wyszukując binarnie odpowiadającej wartości w w2.
Jednak, przecież nie warto sprawdzać wartości powyżej 17 - bo wtedy musiałbyś mieć ujemne wartości w w2. Ale widać też, że w tym przypadku sprawdzenie powinieneś skończyć już na 8 w w1, bo jak weźmiesz następną wartość - 10, to w w2 min = 8, a 10+8 = 18 > 17
Proponuję Ci: narysuj kilka przykładów posortowanych ciągów na kartce i pokombinuj.

[narbej]

Proponuję Ci: narysuj kilka przykładów posortowanych ciągów na kartce i pokombinuj.

TZ
Narysuj chociaż jeden, jak wyżej np z zadania i pomyśl/pokombinuj, jak [z]robić to szybko [zadanie] "ręcznie" bez binary_search.

[przemek625]

Napisałem tak jak mówisz, mogę dodać 1000 innych warunków, dzieki którym będzie przerywać pętlę.
Mogę posortować jeszcze 3 ciąg, dodać aby abye nie sprawdzał jeśli lcizba się powtarza... Ale i tak w najgorszym przypadku złożoność obliczeniowa będzie n*logn. Tak jest chyba u mnie. To szukanie binarne chyba sensu w ogóle nie ma...Męczę się z nim, a może ono w ogóle nie jest dobrym sposobem na to zadanie. Przecież mogę napisać taki ciągi, że pętla będzie ZAWSZE dochodzić do ostatnego elementu w ciągi wag1 i następnie potem szukać binarnie.

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

using namespace std;

void wczytaj(vector<int> &b);

int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> wag1(n);
    vector<int> wag2(n);
    vector<int> szukana_suma(m);
    vector<string> odp(m);

    wczytaj(wag1);
    wczytaj(wag2);
    wczytaj(szukana_suma);

    sort(wag1.begin(),wag1.end());
    sort(wag2.begin(),wag2.end());


    for(int i=0;i<m;i++)
    {


        for(int k=0;k<n;k++)
        {

            int szukana_wartosc_w_wag2=szukana_suma[i]-wag1[k];


            
            if(szukana_wartosc_w_wag2<=0 || wag1[k]+wag2[0]>szukana_suma[i])
            {
                odp[i]="NIE";
                break;
            }
            else if(wag1[k]+wag2[n-1]<szukana_suma[i] && k!=n-1)
            {

                continue;
            }
            else if(wag1[k]+wag2[n-1]<szukana_suma[i] && k==n-1)
            {
                odp[i]="NIE";
                break;
            }

            bool exist=binary_search(wag2.begin(),wag2.end(),szukana_wartosc_w_wag2);

            if(exist)
               {
                   odp[i]="TAK";
                   break;
               }
              else if(!exist && k==n-1)
              {
                  odp[i]="NIE";
              }
    }
    }


    for(int i=0;i<m;i++)
    {
        cout<<odp[i]<<endl;
    }
}


void wczytaj(vector<int> &b)
{
    int liczba;

    for(int i=0;i<b.size();i++)
    {

        cin>>liczba;
        b[i]=liczba;

    }
}

[narbej]

No, ok, a jak brzmi pytanie? Jeżeli chodzi o twój, post wyżej, aktualny kod, to nie jest to to, co Ci podpowiedziałem.

Nie nie napisałeś tak jak mówiłem. Może ja źle mówię [ale przecież nie chcę podać Ci gotowego rozwiązania]. Albo Ty się uparłeś i nie uważnie słuchasz.
Może przeczytałbyś w końcu moje rady?