A: Jakkara

Tehtävä

Tehtävänä on etsiä luku $x$ niin, että summa $|x-a|+|x-b|+|x-c|+|x-d|$
on mahdollisimman pieni.

Ensimmäinen havainto on, että optimaalinen $x$ on aina vähintään $x_1=\min(a,b,c,d)$ ja korkeintaan $x_2=\max(a,b,c,d)$. Niinpä riittää käydä läpi kaikki luvut väliltä $[x_1,x_2]$ ja valita niistä arvo, joka tuottaa pienimmän summan.

Tällä tavalla saa ratkaistua kaksi ensimmäistä alitehtävää. Esimerkiksi Pythonilla ratkaisun voi toteuttaa näin:

a, b, c, d = [int(x) for x in raw_input().split(" ")]
x1 = min(a,b,c,d)
x2 = max(a,b,c,d)
p = 10**18
for x in range(x1,x2+1):
    u = abs(x-a)+abs(x-b)+abs(x-c)+abs(x-d)
    p = min(p,u)
print p

Tehokas ratkaisu perustuu havaintoon, että optimaalinen $x$ on itse asiassa aina yksi luvuista $a$, $b$, $c$ ja $d$. Tämä johtuu siitä, että jos $x$ on lukujen välissä, summan suurutta voi pienentää siirtämällä $x$:ää vasemmalle tai oikealle sen mukaan, kummassa suunnassa on useampi luvuista $a$, $b$, $c$ ja $d$. Jos taas molemmissa suunnissa on kaksi lukua, summa säilyy samana.

Tuloksena on seuraava ratkaisu:

a, b, c, d = [int(x) for x in raw_input().split(" ")]
p = 10**18
for x in [a,b,c,d]:
    u = abs(x-a)+abs(x-b)+abs(x-c)+abs(x-d)
    p = min(p,u)
print p

Vielä tarkemmin voidaan todeta, että optimaalinen pituus on lukujen mediaani eli kumpi tahansa keskimmäisistä pituuksista. Kaavoja supistamalla ratkaisu pelkistyy seuraavaan muotoon:

t = sorted(int(x) for x in raw_input().split())
print(t[3] + t[2] - t[0] - t[1])

Ratkaisu toimii myös yleisessä tapauksessa jalkojen määrästä riippumatta:

t = sorted(int(x) for x in raw_input().split())
print(sum(abs(t[len(t) // 2] - i) for i in t))

B: Aita

Tehtävä

Jos $2k>n$, ratkaisua ei ole olemassa, koska luvun $k$ viereen ei voi laittaa mitään toista lukua. Jos $2k \le n$, ratkaisu on olemassa ja sen voi muodostaa valitsemalla luvut järjestyksessä $u+1,1,u+2,2,u+3,3,\ldots$, missä $u=\lfloor n/2 \rfloor$. Tässä lukujonossa jokaisen kahden peräkkäisen luvun ero on ainakin $k$.

Seuraava koodi toteuttaa ratkaisun:

n, k = [int(x) for x in raw_input().split(" ")]
if k*2 > n:
    print "QAQ"
    exit()
u = n/2
v = []
for i in range(1,u+1):
    v.append(u+i)
    v.append(i)
if n%2 == 1:
    v.append(n)
print " ".join([str(x) for x in v])

C: Lähetit

Tehtävä

Ensimmäisen alitehtävän voi ratkaista raa'an voiman ratkaisulla, joka käy läpi kaikki mahdolliset tavat valita lähettien sijainnit.

Tehokas ratkaisu syntyy havainnosta, että shakkilaudan mustilla ja valkeilla ruuduilla olevia lähettejä voi laskea toisistaan riippumattomasti. Merkitään $m(n,x)$ ja $v(n,x)$ tapoja sijoittaa $x$ lähettiä mustille ja valkeille ruuduille $n \times n$ -shakkilaudassa. Nyt ratkaisu tehtävään on $\sum m(n,x)v(n,k-x)$, missä $x=0,1,\ldots,n^2$.

Toinen alitehtävä ratkeaa laskemalla funktioiden $m$ ja $v$ arvot raa'alla voimalla. Kolmas alitehtävä ratkeaa käyttämällä dynaamista ohjelmointia. Vinorivit voi käydä läpi pituusjärjestyksessä (1, 1, 3, 3, 5 jne.), jolloin joka vinoriville tulee enintään yksi lähetti ja jokainen asetettu lähetti myös vähentää yhden mahdollisen ruudun kaikilta myöhemmiltä vinoriveiltä.