Messages posted by: MODDI

????? ?? ?????? ?? ?????? 8 ????????, ?? ?????????? ?? ???? ?? ?????, ???? ?? ?? ???????

Кодов ми работи на 14/20 тест примери на останатите ми дава надминат временски лимит, дали може задачава да се реши на ваков начин или треба да барам побрз.

Задачата Rectangles од делот интернационални е повторно дп, ми работи на 2/10 малку хелп.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int size;
    cin>>size;
    int side[size][size];
    for(int i=0;i<size;i++)
        for(int j=0;j<2;j++)
            cin>>side[i][j];
      
    int dp[size][2];
    dp[0][0]=side[0][0];
    dp[0][1]=side[0][1];
    for(int i=1;i<size;i++)
    {
        if(i%2!=0)
        {
            dp[i][1]=max(dp[i-1][1]+side[i][0]+abs(side[i][1]-side[i-1][0]),dp[i-1][1]+side[i][1]+abs(side[i][0]-side[i-1][0]));
            dp[i][0]=max(dp[i-1][0]+side[i][1]+abs(side[i-1][1]-side[i][0]),dp[i-1][0]+side[i][0]+abs(side[i][1]-side[i-1][1]));
        }
        else
        {
            dp[i][1]=max(dp[i-1][1]+side[i][1]+abs(side[i][0]-side[i-1][1]),dp[i-1][1]+side[i][0]+abs(side[i][1]-side[i-1][1]));
            dp[i][0]=max(dp[i-1][0]+side[i][1]+abs(side[i][0]-side[i-1][1]),dp[i-1][0]+side[i][0]+abs(side[i][1]-side[i-1][0]));
        }
    }
    cout<<max(dp[size-1][0]-1,dp[size-1][1]-1);
     
    return 0;
}

Задачава неможев да ја сфатам, поточно на врските немозам да го сфатам начинот на кој тие се добиваат, сликата што е дадена во текстот на задачата повеќе ме збунува мене отколку ми појаснова, ако може некој барем псевдо код да даде или base-cases од dpto и да ми ја појасни задачава.

Со кодов ми поминува на 27/37 тест примери на останатите ми паѓа на време, дали со неколку модификации на кодов може да се реши задачава или ќе треба да го земам фактот дека 1≤N≤100 000, а дека задачава работи О(N na kvadrat)

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> pom;
bool Prime(int N)
{
	if(N<=1)
		return false;
	if(N<=3)
		return true;
	if(N%2==0 || N%3==0)
		return false;
	for(int i=5;i*i<=N;i+=6)
		if(N%i==0 || N%(i+2)==0)
			return false;

return true;
}
int create(vector<int> digits, int minus)
{
	int number=0;
	int faktor=pow(10,digits.size()-minus-1);
	for(int i=0;i<digits.size()-minus;i++)
	{

number+=digits[i]*faktor;
		faktor/=10;
	
	}
	if(minus!=0)
	pom.push_back(digits[minus]);

return number;
}
int main()
{
	string cena;
	cin>>cena;
	int counter=0;
	int size_counter=0;
	vector<int> digits;
	for(int i=0;i<cena.size();i++)
		digits.push_back(int(cena[i]-'0'));
	int dp[digits.size()+1][digits.size()];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<digits.size();i++)
		dp[i][i]=digits[i];
	for(int i=1;i<digits.size();i++)
	{
		dp[0][i]=create(digits,digits.size()-1-i);
		dp[i][0]=create(digits,digits.size()-1-i);
	}	
	/*for(int i=1;i<digits.size();i++)
	{
		dp[i][digits.size()-1]=dp[0][digits.size()-1]%faktor;
		faktor/=10;
	}*/
	
	for(int j=2;j<digits.size();j++)
	{
		int faktor=pow(10,j);
		for(int i=1;i<digits.size();i++)
		{
			if(i!=j && dp[i][j]==0)
			{
				dp[i][j]=dp[i-1][j]%faktor;
				faktor/=10;
			}
		}
	}
	vector<int>primes;
	for(int i=0;i<digits.size();i++)
	{
		for(int j=i;j<digits.size();j++)
		{
			if(Prime(dp[i][j])==true)
			{
				bool vis=false;
				for(int k=0;k<primes.size();k++)
				{
					if(primes[k]==dp[i][j])
					{
						vis=true;
						break;
					}
				}
				if(vis==false)
				{
					primes.push_back(dp[i][j]);
					counter++;
				}
			}
		}
	}
						
	
	/*for(int i=0;i<digits.size();i++)
	{
		for(int j=0;j<digits.size();j++)
		{
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	cout<<counter<<endl;
	return 0;
			
	
	
}

Зошто на мендо на сите тест примера ми враќа RUNTIME ERROR

#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

Ако може псевдо код или пак, подетално објаснување бидејќи заглавив

Ја решавав задачава, мојот код работи на дадените тест примери и кога го праќам на мендо ми работи само на 1, малку хелп, немора решение, само сакам да знам дали сум во добра насока за да ја решам задачава или треба да почнам од почетокч

Некоја идеја за задачава ??

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
vector<string>registered;
vector<int> indexes;
bool check(string one, string two)
{
	if(one.size() != two.size())
		return false;
	else
	{
		for(int i=0;i<one.size();i++)
		{
			if(one[i]==two[i])
				continue;
			else
				return false;
		}
	}
	return true;
}
void split_string(string inserted_name)
{
	for(int i=0;i<registered.size();i++)
	{
		int numbers=0;
		int index=pow(10,registered[i].size()-inserted_name.size());
		string pom=registered[i];
		if(registered[i]==inserted_name)
		indexes.push_back(0);
		else
		{
			for(int j=pom.size();j>inserted_name.size();j++)
			{
				if(pom[j]>='1' && pom[j]<='9')
				{
					if(index==10)
					numbers+=(int(pom[j])-'0');
					else
					{
						numbers+=(int(pom[j]-'0'))*index;
						index/=10;
					}
				}
				else
				break;
			}
		}
		if(check(pom,inserted_name)==true)
		indexes.push_back(numbers);
		
	}
	return ;
}
int main()
{
	string inserted_name;
	cin>>inserted_name;
	int size;
	cin>>size;

for(int i=0;i<size;i++)
	{
		string a;
		cin>>a;
		registered.push_back(a);
	}
	split_string(inserted_name);
	sort(indexes.begin(),indexes.end());
	
	for(int i=0;i<indexes.size();i++)
	{
		if(indexes[i]+1!=indexes[i+1])
		{
			cout<<inserted_name<<indexes[i]+1<<endl;
			return 0;
		}
	}
	
	cout<<inserted_name<<endl;
	return 0;
	
}

Ја решавав задачава, кодов ми работи на 6 тест примери, на останатите ми враќа прогрешен резултат, хелп

Ох, не ни приметив дека сортот ми е пред да внесам елементи во векторот, фала многу

Колку што те разбрав, вака нешто би требало да е ова решение ми работи на 6 примера

Некоја идеја за задачава

Благодарам многу, изглеа ти го потрошив времето за проста задача али рекурзијата не ми е баш усовршена, затоа повеќе се фокусирам на таков вид на задачи..
Фала многу уште еднаш