Codah ClubВежбај. Испрати. Напредувај.
Најави се
Македонски
#00062B

NZD - Okružno 2012

Dat je niz prirodnih brojeva a od n elemenata. U jednom potezu dozvoljeno je odabrati proizvoljna dva susedna broja u nizu i zameniti ih njihovim zbirom. Na primer, ukoliko smo odabrali brojeve ai i ai + 1, niz (a1, a2, ..., ai, ai+1, ... an) postaje (a1, a2, ..., ai + ai+1, ... an). Ovo zatim možemo ponavljati na novodobijenim nizovima (primetimo da se broj elemenata niza svaki put smanjuje za 1).


Primeniti određeni broj poteza nad početnim nizom, tako da na kraju dobijemo tačno k brojeva čiji je najveći zajednički delilac najveći moguć.


InputU prvom redu ulaza nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj elemenata u početnom nizu i broj elemenata koji treba ostati na kraju (1 ≤ k < n ≤ 100,000). Sledeći red sadrži n prirodnih brojeva ai koji predstavljaju početni niz (ai ≤ 1,000,000). Suma svih brojeva nije veća od 1,000,000.

OutputU prvom redu izlaza ispisati maksimalan moguć najveći zajednički delilac preostalih brojeva. U drugom redu izlazne datoteke ispisati k prirodnih brojeva - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.

Ulaz:
6 3
12 7 3 2 15 15
Izlaz:
6
12 12 30

Objašnjenje.


Ukoliko izvršimo poteze (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) dobijamo brojeve 12, 12 i 30 čiji je najveći zajednički delilac jednak 6. Nije moguće dobiti 3 broja sa većim najvećim zajedničkim deliocem.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.