[општински 2019]Дедо Мраз

Имам прашање за задачава за оние кои ја имат решено бидејќи ми прегоре напојувањето пробувајќи да ја решам за време на натпреварот дали сум на добар пат?

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
   int N,T,res=0,totalA=0,totalB=0;
   cin >> N;
   vector <int> fake,needed;
   for(int i=0;i<N;i++)
   {
       int in;
       cin >> in;
       fake.push_back(in);
       totalA+=in;
   }
   cin >> T;
   for(int i=0;i<T;i++)
   {
       int in2;
       cin >>in2;
       needed.push_back(in2);
       totalB+=in2;
   }
   if(totalB>totalA)
   {
       cout << 0;
       return 0;
   }
   vector <pair<int,pair<int,int> > > cpbs,cpbs2;//Saa u taj slucaj ako razgledame minimum
 
   for(int i=0;i<N;i++)
   {
       for(int j=i;j<N;j++)
       {
           cpbs.push_back(make_pair((fake[i]+fake[j]),make_pair(i,j)));
       }
   }
     for(int i=0;i<T;i++)
   {
       for(int j=i;j<T;j++)
       {
           cpbs2.push_back(make_pair((needed[i]+needed[j]),make_pair(i,j)));
       }
   }
   for(int i=0;i<cpbs.size();i++)
   {
        for(int j=0;j<T;j++){
            if(cpbs[i].first==needed[j])
            {
                needed[j]=0;
                fake[cpbs[i].second.first]=0;
                fake[cpbs[i].second.second]=0;
                res++;
            }
 
            }
   }
    for(int i=0;i<cpbs2.size();i++)
   {
        for(int j=0;j<N;j++){
            if(cpbs2[i].first==fake[j])
            {
                fake[j]=0;
                needed[cpbs2[i].second.first]=0;
                needed[cpbs2[i].second.second]=0;
                res++;
            }
 
            }
   }
     //Sum gi trgnal site ti dek so a+b moze da dade c i saa treba da delam.
   sort(fake.begin(),fake.end());
   sort(needed.begin(),needed.end());
   set <int> emptiz,emptiz2;
   for(int i=0;i<needed.size();i++)
   {
       if(needed[i]!=0)
       {
           emptiz.insert(needed[i]);
       }
   }
   for(int i=0;i<fake.size();i++)
   {
       if(fake[i]!=0)
       {
           emptiz2.insert(fake[i]);
       }
   }
   for(int i=fake.size()-1;i>=0;i--)
   {
       for(int j=0;j<=fake[i];j++){
       if(emptiz.count(fake[i]-j)>0 && emptiz.count(j)>0)
       {
           emptiz.erase(fake[i]-j);
           emptiz.erase(j);
           fake[i]=0;
           res++;
       }
 
       }
   }
    for(int i=needed.size()-1;i>=0;i--)
   {
       for(int j=0;j<=needed[i];j++){
       if(emptiz2.count(needed[i]-j)>0 && emptiz2.count(j)>0)
       {
           emptiz.erase(needed[i]-j);
           emptiz.erase(j);
           fake[i]=0;
           res++;
       }
 
       }
   }
    sort(fake.begin(),fake.end());
    sort(needed.begin(),needed.end());
    reverse(fake.begin(),fake.end());
    reverse(needed.begin(),needed.end());
    int h=0,res2=0,didtimes=0;
    for(int i=0;i<fake.size() && fake[i]!=0;i++)
    {   int z=0;
        while(fake[i]>z)
        {
            if(needed[h]!=0)
            res2++;
            z+=needed[h];
 
            if(z>=fake[i])
            {
                needed.push_back(z-fake[i]);
                fake[i]=0;
                didtimes++;
            }
            needed[h]=0;
 
 
            h++;
        }
    }res2-=didtimes;
   cout << res+res2;
}

Ви благодарам.

p.s

Ова задача спаѓа во Ad-hoc проблеми?

Krenkov wrote:Ова задача спаѓа во Ad-hoc проблеми?

Ако сакаш со твојов код, можеш да продолжиш да се обидуваш (сега ја има задачата во тренинг делот на МЕНДО).
Ама, ако сакаш хинт како се решава: (рекурзија) [Има и предавање во делот за алгоритми за користење на рекурзија при решавање на слични задачи]

Слични?

BATIR wrote:Слични?

Па да, опишаните техники во предавањата за рекурзија (backtracking) - повикување на истата функција за да се разгледаат разни состојби, функцијата да прима соодветни параметри кои ја опишуваат тековната состојба и од таму создавање на други состојби и слично. Ако сме решиле доста задачи со таа техника, другите задачи делуваат слично бидејќи само треба да откриеме кои параметри се потребни за определување на состојба (во новата задача), кои следни состојби се доволни да ги правиме/разгледуваме, итн.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int time=0;
vector<int> A, B;
void quickest_way(int indexB,int M,int N)
{
    if(indexB==B.size())
        return;
    else
    {
        for(int i=0;i<N;i++)
        {
            if(A[i]<B[indexB] && A[i]!=-1)
            {
                for(int j=i+1;j<N;j++)
                {
                    if(A[j]+A[i]==B[indexB] && A[j]!=-1)
                    {
                        time++;
                        A[j]=-1;
                        A[i]+=A[j];
                        quickest_way(indexB+1,M,N);
                        return ;
                    }
                }
                for(int j=i+1;j<N;j++)
                {
                    if(A[j]-A[i]>=0 && A[j]!=-1 )
                    {
                        if(A[j]-A[i]==0)
                        {
                        A[i]+=A[j];
                        A[j]=-1;
                        time++;
                        quickest_way(indexB+1,M,N);
                        return ;
                        }
                        else
                        {   
                        A.push_back(A[j]-A[i]);
                        A[j]-=A[i];
                        time++;
                        quickest_way(indexB+1,M+1,N+1);
                        return ;
                        }
                    }
                }
            }
        }
        for(int i=indexB;i<N;i++)
        {
            if(A[i]>B[indexB])
            {
                A.push_back(A[i]-B[indexB]);
                A[i]=B[indexB];
                time++;
                quickest_way(indexB+1,M,N+1);
                return ;
            }   
        }   
        for(int i=0;i<N;i++)
        {
            if(A[i]==B[indexB])
            {
                quickest_way(indexB+1,M,N);
                return; 
            }
        }
    }
    return ;
}
int main()
{
    int N;
    cin>>N;
    int size1=0, size2=0;
    for(int i=0;i<N;i++)
    {
        int a;
        cin>>a;
        size1+=a;
        A.push_back(a);
    }
    int M;
    cin>>M;
    for(int i=0;i<M;i++)
    {
        int b;
        cin>>b;
        size2+=b;
        B.push_back(b);
    }
    if(size2>size1)
    {
        cout<<-1<<endl;
        return 0;
    }
    sort(B.begin(),B.end());
    reverse(B.begin(),B.end());
    sort(A.begin(),A.end());
    reverse(A.begin(),A.end());
    quickest_way(0,M,N);
    cout<<time<<endl;
    return 0;
       
}

Кодов ми работи на 12/20 тест примери, малку хелп ако може??

Па добро, твојов код користи рекурзија колку да се каже. Самиов кодот можеш да го прекуцаш и без рекурзија.
Поентата кога користиме backtracking е што кога ќе направиме некој потег, продолжуваме натака со рекурзијата како да е тоа правилен потег, меѓутоа после кога се враќаме назад, правиме друг потег во тој чекор.

На пример, замисли три кутии, и сакаме да разгледаме разни ситуации (каде или може да ставиме некое топче во кутија, или да не ставиме).
Со backtracking, во рекурзијата, прво ја гледаме првата кутија и викаме 1) стави топче во првата кутија, и продолжи рекурзивно да ги разгледаш другите кутии.
Потоа, кога рекурзијата ќе се врати назад (кога ќе заврши разгледувањето на другите две кутии), потоа викаме 2) не ставај топче во првата кутија, и продолжи рекурзивно да ги разгледаш другите кутии.
На тој начин разгледуваме разни состојби. Оваа техника е опишана во предавањето за рекурзија/backtracking, но може да се најдат разни примери со пребарување на Google.

Ти не го правиш ова. Може лесно и да се примети од твојот код, бидејќи го зголемуваш "time++" на неколку места и продолжуваш натаму (значи правиш потези), но никаде не ги поништуваш тие потези (да пробаш со нешто друго во тој чекор од рекурзијата).

Не те сватив баш, може псевдо код за делот со рекурзија

MODDI wrote:Не те сватив баш, може псевдо код за делот со рекурзија

За backtracking? Отвори го ова предавање http://mendo.mk/Lecture.do?id=31 и види ја Програма 10.1 со пермутациите. Пермутации (на кратко) е како можеш да наредиш одреден број на елементи. На пример, има шест пермутации од [1, 2, 3], и тоа се: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] и [3, 2, 1].
Мислам дека е поприлично јасно таму дадена програмата (со коментари и све). Види како во 40-ти ред имаме рекурзивен повик и што се случува потоа (42-46 ред). Тој вториот дел е она за што зборував погоре.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solutions;
void rec(int indexB,vector<int> bag_start, vector<int> bag_end, int time)
{
	if(indexB==bag_end.size())
	{
		solutions.push_back(time);
		return;
	}
	else
	{
		bool saw=false;
			for(int i=0;i<bag_start.size();i++)
				if(bag_start[i]==bag_end[indexB])
				{
					int pom=bag_start[i];
					bag_start[i]=-1;
					rec(indexB+1, bag_start, bag_end,time);
					bag_start[i]=pom;
					saw=true;
				}
		if(saw==false)
		{
			for(int i=0;i<bag_start.size();i++)
			{
				for(int j=i+1;j<bag_start.size();i++)
				{
					if(bag_start[i]+bag_start[j]==bag_end[indexB] && bag_start[i]!=-1 && bag_start[j]!=-1)
					{
						time++;
						bag_start[i]+=bag_start[j];
						int pom=bag_start[j];
						bag_start[j]=-1;
						rec(indexB+1,bag_start,bag_end,time);
						time--;
						bag_start[j]=pom;
						bag_start[i]-=pom;
						break;
					}
					else if(bag_start[i]+bag_start[j]>bag_end[indexB] && bag_start[i]!=-1 && bag_start[j]!=-1)
					{
						time+=2;
						int pom=bag_start[j];
						bag_start[i]+=pom;
						bag_start[j]=-1;
						bag_start.push_back(bag_start[i]-bag_end[indexB]);
						rec(indexB+1, bag_start, bag_end,time);
						time-=2;
						bag_start[j]=pom;
						bag_start[i]-=pom;
						bag_start[bag_start.size()-1]=-1;
						break;
					}
					else
					{
						time++;
						int pom=bag_start[j];
						bag_start[i]+=bag_start[j];
						bag_start[j]=-1;
						rec(indexB+1,bag_start, bag_end,time);
						time--;
						bag_start[j]=pom;
						bag_start[i]-=pom;
						break;
					}
				}
			}
		}
	}
}
int main()
{
	int size_start, size_end;
	cin>>size_start;
	vector<int> bag_start, bag_end;
	int sumA=0, sumB=0;
	for(int i=0;i<size_start;i++)
	{
		int a;
		cin>>a;
		sumA+=a;
		bag_start.push_back(a);
	}
	cin>>size_end;
	for(int j=0;j<size_end;j++)
	{
		int b;
		cin>>b;
		sumB+=b;
		bag_end.push_back(b);
	}
	sort(bag_start.begin(),bag_start.end());
	sort(bag_end.begin(),bag_end.end());
	rec(0,bag_start, bag_end, 0);
	sort(solutions.begin(),solutions.end());
	cout<<solutions[0]<<endl;
	return 0;
}

Пишував ново решение со рекурзија, ми работи на 2 тест примери, на 5 ми дава погрешен резултат, а на останатите runtime error, HELP PLS