Wizytówki zadanie z OIG

0

Witam, rozwiązuję zadanie http://main.edu.pl/pl/archive/oig/6/gum
Napisałem kod:

#include <iostream>
#include <string>

using namespace std;

int N=0;
string *wyrazy;

int main()
{
	cin>>N;
	wyrazy=new string[N];
	for(int i=0;i<N;i++)
	{
		cin>>wyrazy[i];
	}   
	string *max=&wyrazy[0];
	for(int m=0;m<N;m++)
	{
		if(wyrazy[m]>*max)
		{
			max=&wyrazy[m];
		}
	}
	string tmp=*max;
	*max=wyrazy[0];
	wyrazy[0]=tmp;
	max=&wyrazy[0];
	for(size_t i=0;i<wyrazy[0].size();i++)
	{
		for(int o=1;o<N;o++)
		{
			short ask=1;
			for(size_t p=0;p<wyrazy[o].size();p++)
			{
				if(wyrazy[0][i]==wyrazy[o][p])
				{
					wyrazy[o].erase(p, 1);
					ask=0;
					break;
				}
			}
			if(ask==1)
			{    
				wyrazy[0].erase(i, 1);
				i--;
				break;
			} 
		}  
	}


	string wynik;
	for(size_t i=0;i<wyrazy[0].size();i++)
	{
		int adres=i+1;
		for(size_t o=i+1;o<wyrazy[0].size();o++)
		{
			if(wyrazy[0][adres]<wyrazy[0][o])
			{
				adres=o;
			}
		}
		if(wyrazy[0][adres]>wyrazy[0][i])
		{
			wynik+=wyrazy[0][adres];
			i=adres;
		}
		else
		{
			wynik+=wyrazy[0][i];
		}
	}
	wyrazy[0]=wynik;


	const string bitek="bitek";
	for(size_t i=0;i<wyrazy[0].size() && i<bitek.size();i++)
	{
		if(bitek[i]>wyrazy[0][i])
		{
			cout<<bitek; 
		}
		else
		{
			cout<<wyrazy[0]; 
		}
	}
} 

Gdy za pierwszym razem wysłałem ten kod(tyle że wczytanie danych testowych było w oddzielnej funkcji) do oceny dostałem 10 punktów, gdy teraz sprawdzam z danymi testowymi na moim komputerze działa okej, gdy wysyłam je na platformę OIG dostaję 0 punktów, 1 odpowiedź jest dobra, możecie zobaczyć gdzie jest błąd w moim kodzie(ja piszę pod Visualem, a oni to oceniają pod gcc linuxowym)

0

a to ten kod za który uzyskałem 10 punktów:

 #include <iostream>
#include <string>
using namespace std;
int N=0;
string *wyrazy;

inline string wynik()
{
	cin>>N;
	wyrazy=new string[N];
	for(int i=0;i<N;i++)
	{
		cin>>wyrazy[i];
	} 
	string *max=&wyrazy[0];
	for(int m=0;m<N;m++)
	{
		if(wyrazy[m]>*max)
		{
			max=&wyrazy[m];
		}
	}
	string tmp=*max;
	*max=wyrazy[0];
	wyrazy[0]=tmp;
	max=&wyrazy[0];
	for(size_t i=0;i<wyrazy[0].size();i++)
	{
		for(int o=1;o<N;o++)
		{
			short ask=1;
			for(size_t p=0;p<wyrazy[o].size();p++)
			{
				if(wyrazy[0][i]==wyrazy[o][p])
				{
					wyrazy[o].erase(p, 1);
					ask=0;
					break;
				}
			}
			if(ask==1)
			{    
				wyrazy[0].erase(i, 1);
				i--;
				break;
			} 
		}  
	}

	string wynik;
	for(size_t i=0;i<wyrazy[0].size();i++)
	{
		int adres=i+1;
		for(size_t o=i+1;o<wyrazy[0].size();o++)
		{
			if(wyrazy[0][adres]<wyrazy[0][o])
			{
				adres=o;
			}
		}
		if(wyrazy[0][adres]>wyrazy[0][i])
		{
			wynik+=wyrazy[0][adres];
			i=adres;
		}
		else
		{
			wynik+=wyrazy[0][i];
		}
	}


	const string bitek="bitek";
	for(size_t i=0;i<wynik.size() && i<bitek.size();i++)
	{
		if(bitek[i]>wynik[i])
		{
			return bitek;
		}
		if(bitek[i]<wynik[i])
		{
			return wynik; 
		}
	}
}
int main()
{
	cout<<wynik();
	int pausa;
	cin>>pausa;
	return 0;
}
0

Kilka uwag ogólnie:

  1. Jeżeli zamierzasz startować w OIG/OI, to nie pisz programów w Visualu, które klepiesz aby się przygotować na te zawody, tylko zainstaluj sobie MinGW, bo możesz mieć wiele takich niespodzianek. Wtedy pisz w jakimś innym IDE/edytorze, ale ważne abyś kompilował w g++. Mimo to jeżeli możesz to zainstaluj sobie linuxa, większość osób preferuje ubuntu, instalacja jest bardzo łatwa, a GCC masz od razu.

  2. Nie wczytywałem się w kod, ale po co robisz to na wskaźnikach? Skoro w zadaniu jest "Sumaryczna długość słów na wejściu nie może przekroczyć 10^7". Ale i tak to jest klasa string, wystarczy, że wczytasz napis, a w tej klasie zostanie zarezerwowane tyle miejsca ile jest potrzebne. Poza tym tu masz wyciek pamięci, bo masz new, a nie masz delete.

  3. *max=wyrazy[0];
    Po co Ci to, czy nie wystarczy jak w max zapamiętasz indeks, a nie będziesz się we wskaźniki bawił (może to ma głębsze przesłanie, bo jak mówiłem, nie wczytywałem się dokładnie)?

  4. Polecam wczytywanie z printfów/scanfów są szybsze, ale jeżeli koniecznie cout/cin (a tutaj są stringi, więc tak jest wygodniej) to dopisuj na początku programu ios_base::sync_with_stdio(0); (inaczej jest za wolno).

  5. for(size_t p=0;p<wyrazy[o].size();p++)
    Taka konstrukcja bardzo spowalnia Twój program TLE (przekroczenie czasu) gwarantowany - oblicz wcześniej raz size i zapisz do zmiennej. Takich konstrukcji masz kilka.

  6. inline na tyle linii? Nie potrzebnie.

  7. cin>>pausa; nie można dawać czegoś takiego na sprawdzarkę! W życiu nie wejdzie. Poczytaj sobie pisze o tym i o innych takich rzeczach na stronie OI. Dlatego jeżeli chcesz brać udział w OIG to kompiluj w GCC i uruchamiaj w konsoli (lub najlepiej na linuxie w terminalu).

To są takie uwagi ogólne, popraw to i najlepiej sam uruchom to kompilując na GCC (do tego zobacz jakimi opcjami kompilują na zawodach, one mogą Cię ostrzec przed większą ilością błędów, np. -Wall i -Wextra), bo jeżeli chcesz wziąć udział w OIG, to i tak musisz zainstalować ten kompilator.

0

Biorę udział w tegorocznym finale OIG, a że piszę go pierwszy raz i nie pisałem drugiego etapu i nikt z mojego miasta nie brał udziału w tym konkursie to nie orientuję się w jego wymogach, mam zainstalowanego Dev-C++ z MinGW ale z nim są same problemy, np. brakuje mu iostream :)

0

Awansowałem za najlepszy wynik w województwie:)

0

Poprawiłem kod, ale dalej nie zyskał na prędkośći:

 
#include <iostream>
#include <string>
using namespace std;
int N=0;
string *wyrazy;

string wynik()
{
	cin>>N;
	wyrazy=new string[N];
	cin>>wyrazy[0];
	string *max=&wyrazy[0];
	for(int i=1;i<N;i++)
	{
		cin>>wyrazy[i];
		if(wyrazy[i]>*max)
		{
			max=&wyrazy[i];
		}
	} 
	string tmp=*max;
	*max=wyrazy[0];
	wyrazy[0]=tmp;
	max=&wyrazy[0];
	for(unsigned int i=0;i<wyrazy[0].size();i++)
	{
		for(int o=1;o<N;o++)
		{
			short ask=1;
			for(unsigned int p=0;p<wyrazy[o].size();p++)
			{
				if(wyrazy[0][i]==wyrazy[o][p])
				{
					wyrazy[o].erase(p, 1);
					ask=0;
					break;
				}
			}
			if(ask==1)
			{    
				wyrazy[0].erase(i, 1);
				i--;
				break;
			} 
		}  
	}
	string wynik;
	unsigned int length=wyrazy[0].size();
	for(unsigned int i=0;i<length;i++)
	{
		int adres=i+1;
		for(unsigned int o=i+1;o<length;o++)
		{
			if(wyrazy[0][adres]<wyrazy[0][o])
			{
				adres=o;
			}
		}
		if(wyrazy[0][adres]>wyrazy[0][i])
		{
			wynik+=wyrazy[0][adres];
			i=adres;
		}
		else
		{
			wynik+=wyrazy[0][i];
		}
	}
	delete[]wyrazy;
	const string bitek="bitek";
	unsigned int wsize=wynik.size();
	for(unsigned int i=0;i<wsize && i<5;i++)
	{
		if(bitek[i]>wynik[i])
		{
			return bitek;
		}
		if(bitek[i]<wynik[i])
		{
			return wynik; 
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cout<<wynik();
	int pausa;
	cin>>pausa;
	return 0;
}
0

Po pierwsze - jaki masz błąd - zła odpowiedź, czy przekroczenie limitu czasu?

Po drugie nie zastosowałeś się do wszystkich moich wskazówek, a do jednej, a i tak nie do końca bo nadal masz:
for(unsigned int i=0;i<wyrazy[0].size();i++)

Po trzecie jak poprawisz to co Ci napisałem, to i tak nie mam czasu szukać błędu, napisałem Ci co na pewno powinieneś poprawić, jak mówiłem nie zaglądałem głębiej w kod, tylko na szybko, a błąd może się kryć gdzie indziej (mimo to najpierw spróbuj poprawić wszystko to co Ci napisałem, łącznie z kompilacją w GCC, przy czym jak na windows to MinGW jest portem GCC).

Edit: No i nadal masz:
int pausa;
cin>>pausa;
Zastosuj się do wszystkich wskazówek!

0

int pause mam tylko dla sprawdzenia, wysyłam bez tego.

0

Witam odświeżam temat, poprawiłem kod, ale dalej jest błąd choć już mniej, możecie wygenerować mi przypadki testowe na których ten algorytm się wywala:

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int N;
struct wyraz
{
	string w;
	int ost;
	int tmp;     
	wyraz()
	{
		ost=0;
		tmp=0;
	}
};

string WypTab()
{
	/*
	fstream plik;
	plik.open("plik.txt", ios::in);
	plik>>N;
	wyraz *wyrazy;
	wyrazy = new wyraz[N];
	plik>>wyrazy[0].w;
	string *max=&wyrazy[0].w;
	for(int i=1;i<N;i++)
	{
		plik>>wyrazy[i].w;
		if(*max<wyrazy[i].w)
		{
			max=&wyrazy[i].w;
		}
	} 
	*/
	cin>>N;
	wyraz *wyrazy;
	wyrazy = new wyraz[N];
	cin>>wyrazy[0].w;
	string *max=&wyrazy[0].w;
	for(int i=1;i<N;i++)
	{
		cin>>wyrazy[i].w;
		if(*max<wyrazy[i].w)
		{
			max=&wyrazy[i].w;
		}
	} 




	unsigned int length=wyrazy[0].w.size();
	for(unsigned int i=0;i<length;i++)//litera wzorca
	{
		bool jest=true;
		for(int o=1;o<N;o++)//wyraz
		{
			bool ask=false;
			for(unsigned int p=wyrazy[o].ost;p<length;p++)//litery wyrazu
			{
				if(wyrazy[0].w[i]==wyrazy[o].w[p])//literka występuje
				{    
					wyrazy[o].tmp=p;
					wyrazy[o].w.erase(p, 1);
					length--;
					ask=true;
					break;
				}
			}
			if(ask==false)//nie było literki w analizowanym wyrazie
			{    
				//usuwanie ze wzorca literki i apamiętanie nowej długości wzorca
				jest=false;
				wyrazy[0].w.erase(i, 1);
				length--;
				i--;
				break;
			}
		} 
		if(jest==true)//jeżęli istnieje to wszystkie wyrazy do momentu o od 1 ost=tmp
		{
			for(int i=0;i<N;i++)
			{
				wyrazy[i].ost=wyrazy[i].tmp+1;
			}
		} 
	}



	string wynik;
	length=wyrazy[0].w.size();
	for(unsigned int i=0;i<length;i++)
	{
		int adres=i;
		char max=wyrazy[0].w[adres];
		for(unsigned int o=i+1;o<length;o++)//przeglądanie wzoru
		{
			if(max<wyrazy[0].w[o])
			{
				max=wyrazy[0].w[o];
				adres=o;
			}
		}
		wynik+=wyrazy[0].w[adres];
		i=adres;
	}
	delete[]wyrazy;
	const string bitek="bitek";
	unsigned int wsize=wynik.size();
	for(unsigned int i=0;i<wsize && i<5;i++)
	{
		if(bitek[i]>wynik[i])
		{
			return bitek;
		}
		if(bitek[i]<wynik[i])
		{
			return wynik; 
		}
	}
	return wynik; 
}
int main()
{
	ios_base::sync_with_stdio(0);
	cout<<WypTab();
	int pausa;
	cin>>pausa;
	return 0;
} 
0

Może ktoś z was pomóc mi znaleźć ten błąd?

0

Nie. Odpal pod debugerem. Nikt tego za ciebie nie zrobi.

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