Makowce i Keksy

Jesli jest to zadanie optymalizacyjne czyli z serii, podaj maksymalna mozliwa ilosc wyrobow jaka mozna wykonac z danych skladnikow to wtedy implementujesz cos takiego:
http://pl.wikipedia.org/wiki/Problem_plecakowy

Wydaje mi sie ze tak jest chociaz w zadaniu nie jest to sprecyzowane, a byc powinno.

Wrzucę kod mniej więcej taki jaki napisałem na zawodach. Algorytm pozostał taki sam.
Wydaje mi się, że zdobyłem za niego <40 punktów. (Wnioskuję po tym, że jedno zadanie mam tak jak inni, podostawali 100, a ogółem miałem <140, bo nie załapałem się do laureatów, z których najniższy miał właśnie 140.)
http://ideone.com/r05FH1
btw. może być niezrozumiałe do końca

    unsigned int maxMakowcow1 = 0xFFFFFFFF, maxMakowcow2 = 0xFFFFFFFF;
    unsigned int maxKeksow1 = 0xFFFFFFFF, maxKeksow2 = 0xFFFFFFFF;

ta liczba w nazwie zmiennej oznacza kolejność w jakiej robimy ciastka czy jak to sie tam zwie. Np maxKeksow2 jest liczą keksów jakie można zrobić po uprzednim zrobieniu makowców.
są jeszcze dostepne1 i dostepne2, ale to tylko po to żeby rozróżnić dwie kopie.

@Krycho
Twój daje złe wyniki. W dodatku jest niezoptymalizowany.
Sprawdź chociażby dla
3
5 4 8
1 2 2
2 1 3
(zamienione miejscami składniki dla keksów i makowców)

Tu chodzi o maksymalną ilość keyksów i makowców jaką można upiec bo dla drugiego przykładu są dwie opcje:
albo jest 3 keksy i jeden makowiec
lub 4 makowce i jeden keks
chyba dobrze licze. W treści zadania nie ma ,że musi być maksymalna ogółem liczba ciast. Ale z tego co napisałem to wywnioskowuje ,że właśnie chodzi o tą maksymalną ilość ciast

Sorru za pisanie posta pod postem, ale ja wykombinowałem taki algorytm wydaje mi się ,że będzei działać dla wszystkich przypadków

Dla pierwszego przykładu:
5 4 8 <-- stan początkowy

rozważmy przypadek kiedy byśmi chcieli na początku upiec makowca.
suma składników po tym zabiegu będzie wynosiła:

3 3 5 <-- po upieczeniu makowca

a gdybyśmy na początku upiekli keksa to po tym będziemy mieli tyle składników:

4 2 6 <-- po upieczeniu keksa

Teraz pytanie który na początku przypadek wybrać. Otóż musimy dążyć do tego ,aby
rozkład był jak najbardziej równomierny
W pierwszym przypadku różnica pomiędzy 3 a 3 wynosi 0 a pomiędzy 3 a 5 różnica wynosi 2
W drugim przypadku różnica pomiędzy 4 a 2 wynosi 2 a pomiędzy 2 a 6 wynosi 4.
Od razu wiadomo ,że drugi przypadek jest zły ,ponieważ liczby są rozłożone mniej równomiernie.
Jedziemy dalej:

Jeśli upieczemy makowca zostanie nam:

1 2 2 --> abs(1-2) + abs(2 - 1) = 1

a jeśli keksa:

2 1 3 --> abs(2 -1) + abs(1-3) = 3

zatem od razu już wiemy jaką drogą podążymy.
Więc zostaje nam:

1 2 2

tutaj zostaje nam już tylko jedna opcja. Upieczenie keksa.

Dla drugiego przykładu:

7 5 8 <-- wartość początkowa

jeśli upieczemym makowca na początku:

6 4 7 teraz wartości bezwzględne z sąsiednich komórek wynoszą: 5

jeśli upieczemy keksa:

5 4 6 suma wartości bezwględnych z sąsiednich komórek wynosi: 3 zatem podążamy tą drogą

teraz jeśli upieczemy makowca:

4 3 5 suma wartości bezwględnych z sąsiednich komórek wynosi: 3

a jeśli keksa:

3 3 4 suma wartości bezwględnych z sąsiednich komórek wynosi: 1 zatem podążamy tą drogą

teraz jeśli upieczemy makowca:

2 2 3 suma wartości bezwględnych z sąsiednich komórek wynosi: 1

a jeśli keksa

1 2 2 suma wartości bezwględnych też wynosi 1 , ale po tym nie moglibysmy już nic upiec
zatem podążamy pierwszą drogą tam gdzie po zsumowaniu będziemy mieli większą liczbę składników(czyli bedziemy mogli więcej upiec)

po upieczeniu makowca:

1 1 2 suma wartości bezwględnych też wynosi 1

po upieczeniu keksa:

0 1 1 tutaj suma wartości bezwzględnych wynosi też 1, ale w pierwszym przypadku pozostało
nam więcej składników więc podążamy tamtą drogą

no i tutaj pozostaje nam tylko upieczenie makowca ,ponieważ na keksa już nie mamy składników
pozostaje nam:
0 0 1

Gość nie chce gotowego rozwiązania, ale wyjaśnienia czemu jego metoda nie działa! Chwała mu za to.
Nikt mu tego nie powie, bo napisał kod w taki sposób, że głowa boli, a nie był łaskaw wyjaśnić jaki miał pomysł (a domyślanie się tego na podstawie takiego błędnego spaghetti to istna katorga).

Ma może ktoś linka? Jak słusznie zauważył @Shalom jest przy pierwszym poście.
Chyba wymyśliłem ciekawy algorytm, ale nie wiem czy będzie tu pasować.

Witam, przebudowałem cały algorytm, moglibyście teraz mi napisać czemu dostałem tylko 40 punktów, na wszystkie testy 1 rozwiązało błędnie i parę razy był limit czasu. Oto kod:

#include <iostream>

using namespace std;

const int imax=100000;
int S[imax];
int M[imax];
int K[imax];

int main()
{
	int N;
	cin>>N;
	for(int i=0;i<N;i++) cin>>S[i];
	for(int i=0;i<N;i++) cin>>M[i];
	for(int i=0;i<N;i++) cin>>K[i];

	int min= 100000;
	for(int i=0;i<N;i++)
	{
		if(M[i]==0) continue;
		if(S[i]/M[i]<min)min=S[i]/M[i];
	}
	int max=0;



	while(min>0)
	{
		int min_k=100000;
		for(int i=0;i<N;i++)
		{
			if(K[i]==0) continue;
			if(K[i]!=0 && (S[i]-(M[i]*min))/K[i]<min_k) min_k=(S[i]-(M[i]*min))/K[i];
		}
		if(min_k+min>max)
		{
			max=min_k+min;
		}
		min--;
	}
	cout<<max;
	return 0;
} 

czemu zły algorytm skoro uzyskałem 50 punktów gdy wprowadziłem modyfikację:

 #include <iostream>

using namespace std;

const int imax=100000;
int S[imax];
int M[imax];
int K[imax];

int main()
{
	int N;
	cin>>N;
	for(int i=0;i<N;i++) cin>>S[i];
	for(int i=0;i<N;i++) cin>>M[i];
	for(int i=0;i<N;i++) cin>>K[i];

	int min= 1000000000;
	for(int i=0;i<N;i++)
	{
		if(M[i]==0) continue;
		if(S[i]/M[i]<min)min=S[i]/M[i];
	}
	int max=0;


	while(min>0)
	{
		int min_k=1000000000;
		for(int i=0;i<N;i++)
		{
			if(K[i]==0) continue;
			if(K[i]!=0 && (S[i]-(M[i]*min))/K[i]<min_k) min_k=(S[i]-(M[i]*min))/K[i];
		}
		if(min_k+min>max)
		{
			max=min_k+min;
		}
		min--;
	}
	cout<<max;
	return 0;
}

Czy moglibyście mi zoptymalizować ten algorytm, jeśli się da:

#include <iostream>

using namespace std;

const int imax=100000;
int S[imax];
int M[imax];
int K[imax];

int main()
{
	ios_base::sync_with_stdio(0);
	int N;
	cin>>N;
	for(int i=0;i<N;i++) cin>>S[i];
	for(int i=0;i<N;i++) cin>>M[i];
	for(int i=0;i<N;i++) cin>>K[i];

	int min=1000000000;
	for(int i=0;i<N;i++)
	{
		if(M[i]!=0)
		{
			if(S[i]/M[i]<min)min=S[i]/M[i];
		}
	}
	int max=0;


	while(min>0)
	{
		int min_k=1000000000;
		for(int i=0;i<N;i++)
		{
			if(K[i]!=0)
			{
				if((S[i]-(M[i]*min))/K[i]<min_k) min_k=(S[i]-(M[i]*min))/K[i];
			}
		}
		if(min_k+min>max) max=min_k+min;
		min--;
	}
	cout<<max;
	return 0;
} 

co tu optymalizować skoro daje zły wynik.

Nie daje złego wyniku, poprawiłem, dawał zły wynik gdyż dałem za mały zakres zmiennej, int, a nie long long int

patrzyłeś w link? od kiedy to 10 nie mieści się w int?

Nie 10 a 18, doczytaj.

Uzyskałem 50 punktów, wszystkie odpowiedzi dobrze a w kilku limit czasu :)

Sory, pomyliłem zadania :) Chodziło o to że jedną zmienną zainicjowałem zbyt małą artością i wywalał się na jednym teście :)

Gościu umiesz czytać ze zrozumieniem?
To łopatologicznie, jeśli do swojego programu wpiszesz dane:

2
10 10
5 0
1 1

to twój kod zwraca 6, a prawidłowa odpowiedź to 10 (10 keksów +0 makowców).

 #include <iostream>

using namespace std;

const int imax=100000;
int S[imax];
int M[imax];
int K[imax];

int main()
{
	ios_base::sync_with_stdio(0);
	int N;
	cin>>N;
	for(int i=0;i<N;i++) cin>>S[i];
	for(int i=0;i<N;i++) cin>>M[i];
	for(int i=0;i<N;i++) cin>>K[i];

	int min=1000000000;
	for(int i=0;i<N;i++)
	{
		if(M[i]!=0)
		{
			if(S[i]/M[i]<min)min=S[i]/M[i];
		}
	}
	int max=0;


	while(min>=0)
	{
		int min_k=1000000000;
		for(int i=0;i<N;i++)
		{
			if(K[i]!=0)
			{
				if((S[i]-(M[i]*min))/K[i]<min_k) min_k=(S[i]-(M[i]*min))/K[i];
			}
		}
		if(min_k+min>max) max=min_k+min;
		min--;
	}
	cout<<max;
	return 0;
}

Oj, moje przeoczenie, ale to nie zmienia faktu że jest limit czasu a nie zła odpowiedź:
Załączam screena z testami:

Tak przy okazji. Nie wiem czemu w niektórych testach mam złe wyniki, skoro algorytm jest na pierwszy rzut oka poprawny
Chodzi mi o ten, który podałem w 3 poście w temacie. Mógłby ktoś do niego zajrzeć?
Wykonuje się bardzo szybko, ale na niektórych testach się wywala, szkoda, że nie można podpatrzeć. Jakby poprawić błąd to może byłoby dużo punktów.
Działa na łopatologicznej zasadzie sprawdzania ile można zrobić keksów, jeśli najpierw zrobiono max makowców i na odwrót. Nie mam pojęcia jak to może dawać złe wyniki.

http://screenshooter.net/6191878/geotidf
http://screenshooter.net/6191878/usgmxos

http://ideone.com/r05FH1

haha, w zadaniu talerz, na rozwiązaniu wzorcowym (algorytm ten co podawali na omówieniu, nie dało rady wcisnąć nic co mogło by znacząco spowolnić działanie) mam limit czasu w kilku sprawdzeniach ;d
Może wina tego, że piszę na strumieniach? ;d

Sopelek napisał(a):

Nie mam pojęcia jak to może dawać złe wyniki.

3
55 40 55
1 2 3
3 2 1

Da się upiec 20 = 10 keksów + 10 makowców.

twój algorytm daje - 19

Żeby zrozumieć jak rozwiązać to zadanie narysujcie sobie układ współrzędnych: x - liczba keksów; y - liczba makowców.
Każdy składnik daje ograniczenie jak maksymalne sumy keksów i makowców można zrobić. Ograniczenie to na wykresie będzie widoczne jako prosta nierosnąca. Każdy składnik to osobna prosta, które w sumie wyznaczają pewną łamaną określającą zależność ile można zrobić makowców przy zadanej ilości keksów.
Teraz zadaniem jest wynaczynienie prostej stycznej do tej krzywej o nachyleniu -1 .