Raketa - Okruzno SS 2017

Pozdrav svima,

Vec neko vreme sam se ubijao sa ovim zadatkom. I nakon nenoramlno mnogo vremena sam odustao i pogledao zvanicno resenje. Ono glasi:

int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << (abs(a+d-b-c) + 1) / 2;
	return 0;

Da li neko moze da mi objasni zasto ovo radi? Uopste mi nije jasno zasto ovo matematicki vazi?

Link zadatka: https://petlja.org/BubbleBee/r/problemi/takmicenja-srednje-skole/02_raketa#

Hvala unapred!

1 Like

@Delta003 @denkoRa Hey, jel možete da bacite pogled na ovo, pls?

Da li bi neko bio ljubazan da odgovori na postavljeno pitanje? Hvala.

1 Like

Nemam bas dokaz, ali ovo je neko moje misljenje (ne znam da li je 100% ispravno).
Ako posmatramo zbirove na dijagonalama, primetimo da se u svakom potezu, svaka dijagonala poveca tacno za 1. Dakle razlika dijagonala je stalna. Sada, bilo koju matricu mozemo pomocu ponudjenih operacija dovesti u poziciju da na jednoj dijagonali ima dva maksimuma (ne obavezno pocetni maksimumi). U dva poteza mozemo povecati maksimume za po jedan, a jedan broj na drugoj dijagonali za dva. Ako dovedemo matricu u takvu poziciju da i na drugoj dijagonali postoji jedan broj jednak maksimumu, klackavost nase matrice ce biti tacno d1-d2. Sada imamo ovakvu matricu.

max max
a max

Najmanju klackavost dobijamo kada nam i druga dijagonala bude u ravnotezi, odnosno kada a dovedemo do maks. Ako povecamo a za dva, svaki od max na d1 ce se povecati za 1. Dakle da bi doveli a do max, povecacemo ga za max-a. A max na drugoj dijagonali ce se povecati za (max-a)/2. Dakle najmanja klackavost je

max+(max-a)/2-max=(max-a)/2=(max+max-max-a)/2=(d1-d2)/2

Naravno, gornji ceo deo, jer ako je max-a neparno, u jednom preostalom potezu moramo povecati jedan od maksimuma na d1.
Ponavljam, to je samo moje misljenje, ispravite me ako gresim.

2 Likes

Zdravo,

Evo teksta (pisanog za neki nesuđeni bilten) koji opisuje ovo i nekoliko usputnih lošijih rešenja za ovaj zadatak.

http://people.dmi.uns.ac.rs/~marko.savic/raketa_sol.pdf

Prvo ide tekst zadatka, iza njega ide rešenje, a objašnjenje ovog O(1) rešenja je na samom kraju.

2 Likes