Program, zrozumienie

Mam do napisania program, sprawdzający czy spośród 4 podanych przeze mnie cyfr, znajdziemy taki podzbiór, by suma tych cyfr wyniosła "0". Znalazłem taki oto kod z rozwiązaniem, lecz nie do końca rozumiem jego działanie. Mógłby ktoś tak ogólnie wytłumaczyć idee?

#include <bits/stdc++.h>
#define int long long
using namespace std;
main()
{
    int t;
    cin >> t;
    while (t--) {
        int A[4];
        for (int i = 0; i < 4; i++)
            cin >> A[i];
        int tot = 1 << 4;
        int sum = 0;
        bool flag = 0;
        for (int mask = 1; mask < tot; mask++) {
            for (int i = 0; i < 4; i++) {
                int x = 1 << i;
                if (mask & x)
                    sum += A[i];
            }
            if (sum == 0)
                flag = 1;
            sum = 0;
        }

        if (flag)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

Ten kod nie ma NIC wspólnego z twoim zadaniem.
Skąd przekonanie, że to jest rozwiązanie?

Sorry, to miał być ten kod, pochodzi to z CodeChef i zostało zaakceptowane.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

int main() {
	lld t;
	cin>>t;
	while(t--)
	{
	    lld a[4];
	    cin>>a[0]>>a[1]>>a[2]>>a[3];
	    lld tot=1<<4,flag=0; 
	    for (lld i=1;i<tot;i++)
	    {
	        int temp=0;
	        for (lld j=0;j<4;j++)
	        {
	            lld f=1<<j;
	          if (f&i)temp+=a[j];
	        }
	        if (temp==0)
	        {
	            flag=1;
	            break;
	        }
	    }
	    if (flag==0)cout<<"No"<<endl;
	    else cout<<"Yes"<<endl;
	}
	return 0;
}

myślę że też nie :)
napisałbyś szybciej niż ta zabawa w ciuciubabkę

Skądinąd oba są patologiczne

To pochodzi ze strony CodeChef, kod został zaakceptowany, więc myślałem, że jest prawidłowy.

xyz91i napisał(a):

To pochodzi ze strony CodeChef, kod został zaakceptowany, więc myślałem, że jest prawidłowy.

Czyli dobra odpowiedź, nieważne jakie było pytanie ;)
Nie uważasz, ze to kabaretowe?

Czyli jak mam rozumieć ten kod? Co zostało tu robione?

xyz91i napisał(a):

To pochodzi ze strony CodeChef, kod został zaakceptowany, więc myślałem, że jest prawidłowy.

Nie wiem co to CodeChef ale np. na CodeForces ludzie pisza tak paskudny, nieczytelny kod na tych contestach ze to jakas porazka :D
No ale w sumie dziala, kto by sie przejmowal ze sa jakies zmienne pokroju "x, z" nie? :P

A ja mam problem z treścią zadania:

xyz91i napisał(a):

sprawdzający czy spośród 4 podanych przeze mnie cyfr, znajdziemy taki podzbiór, by suma tych cyfr wyniosła "0".

Cyfra to liczba od 0 do 9. Suma n nieujemnych liczb jest równa zero, jeśli wszystkie n liczb są równe zero. Jedna cyfra to jakby nie patrzeć podzbiór czteroelementowego zbioru cyfr. Czy program powinien sprawdzać czy którakolwiek z cyfr jest zerem?

Czy może czegoś nie zrozumiałem?

Pierwsza linijka i od razu taka brzydka rzecz...

#include <bits/stdc++.h>

Nie używaj nagłówków z katalogu bits jeśli nie masz w tym konkretnego celu. Tam mogą być rzeczy wychodzące poza standard i działać inaczej.

To co jest robione w środku tego programu, to generowanie podzbiorów zbioru, za pomoca "counting in binary":
https://en.wikipedia.org/wiki/Binary_number#Counting_in_binary
Twoja mask idzie od 1 do 15, bo mozliwości jest 16, ale podzbioru pustego nie sprawdzasz.
Te wątki, wraz z linkami, powinne wyjaśnić:
https://stackoverflow.com/questions/31883816/all-possible-subsets-of-a-set-using-bit-manipulations-in-java
https://stackoverflow.com/questions/10869866/generating-all-subsets-from-a-single-set

Może podaj zadanie w pełnej formie, a nie własnymi słowami, bo tak jak wspomniał @rafal__ , zadanie w takiej postaci nie ma sensu.

Napisałbym to krócej:

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

int main()
{
    const int Count=4;
    lld t,a[Count],temp=1;
    for(cin>>t;t--;temp=1)
    {
        for(int i=0;i<Count;++i) cin>>a[i];
        for(lld tot=(1UL<<Count)-1;(temp)&&(tot>0);--tot)
        {
            temp=0;
            for(int i=0;i<Count;++i) if((tot>>i)&1) temp+=a[i];
        }
        cout<<(temp?"No":"Yes")<<endl;
    }
    return 0;
}

Owszem przy 4-ch składowych nie ma to znaczenia, zaś przy większej ilości raczej trzeba przejść na kod Graya
Poniżej kod O(2^(n-1)) poprzedni O(2^n)

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

int bin2log(long src)
{
	int ret;
	asm 
	(
		"bsr %1,%%eax;"
		"movl %%eax,%0;"
		:"=r"( ret )
		:"r"( src )
	);
	return ret;
}

int main()
{
    const int Count=4;
    long test,val[Count],prev=0,sum=0,gray,curr;
    for(cin>>test;test--;prev=0,sum=0)
    {
        for(int i=0;i<Count;++i) cin>>val[i];
        for(curr=(1L<<Count)-1;curr>0;--curr,prev=gray)
        {
        	gray=(curr^(curr>>1));
        	int pos=bin2log(gray^prev);
        	if(gray&(1L<<pos)) sum+=val[pos];
        	else sum-=val[pos];
        	if(!sum) break;
        }
        cout<<(curr?"Yes":"No")<<endl;
    }
    return 0;
}

To jest pełna treść: "Chef likes problems which using some math. Now he asks you to solve next one. You have 4 integers, Chef wondering is there non-empty subset which has sum equals 0."

To teraz, przeanalizuj sobie linki z mojego posta powyżej i wróć, jak czegoś nie zrozumiesz.

Tak szczerze to nie zrozumiałem do końca kodu _13th_Dragon.

Zobacz https://www.geeksforgeeks.org/subset-sum-problem-dp-25/

Dla zbioru 4 elementowego tu nie ma co kombinować, ten brutal force jest jak najbardziej ok.
Jakby zbiór liczb wejściowych był wielki +100 to wtedy robi się interesująco i brutal force jest bezcelowy.

Może być ciężko optymaliować, bo problem jest NP complete:
https://en.wikipedia.org/wiki/Subset_sum_problem