Editorial for Ostala si uvijek ista


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: allllekssssa

Zadatak možemo rešiti tako što ćemo isprobati sve kombinacije za indekse i, j, k, odnosno indekse l, m, n. Ukupno ima {4} \choose {3} \cdot 3! = 24 kombinacije za jednu od navedenih trojki (izaberemo prvo trojku indeksa, a onda sve permutacije izabranih indeksa). Obzervacije koje olakšavaju implementaciju rešenja su sledeće:

  • Ako postoje tri indeksa i, j, k tako da važi a_i + a_j = a_k, onda automatski postoje tri indeksa l, m, n (važi a_k - a_j = a_i iz prve jednakosti tako da možemo da stavimo l = k, m = j, n = i). Dovoljno proveriti samo zbir tri broja.
  • Ako proveravamo samo zbir, nama nije važan redosled indeksa i i j (a_i + a_j = a_j + a_i), tako da možemo pretpostaviti i < j što nas dovodi do 12 potrebnih kombinacija indeksa za proveru.
  • Sem što možemo ručno isprobati svaku od navedenih 12 kombinacija, isto možemo da koristimo i tri petlje za iteriranje po svakom od indeksa.

Comments

There are no comments at the moment.