Hide

Problem A
Töflur

Languages en is

Þú elskar að spila leiki með vinkonu þinni. Núna eruð þið að spila leik þar sem hver leikmaður fær n reiti með tölu á. Hver leikmaður setur svo reitina niður á borð í röð að þeirra vali. Látum aj tákna töluna á j-ta reitnum í röð leikmanns, fyrir j=1,2,,n. Fjöldi stiga sem leikmaðurinn fær fyrir þessa röð er reiknuð með því að skoða hverjar tvær tölur sem eru hlið við hlið, taka mismun þeirra og setja þær í annað veldið, og leggja svo saman allar niðurstöðurnar, þ.e.

j=1n1(ajaj+1)2.

Leikmaðurinn með lægsta stigafjöldann vinnur.

Inntak

Fyrsta lína inniheldur heiltölu n (1n106), fjöldi reita. Næsta lína inniheldur n heiltölur, tölurnar á reitunum, sem eru að minnsta kosti 1 en ekki stærri en 106.

Úttak

Skrifið út eina línu með minnsta mögulega stigafjölda ef leikmaður raðar reitunum á sem bestan máta.

Stigagjöf

Hópur

Stig

Takmarkanir

1

15

n=3

2

42

n18

3

43

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
9
1 2 3 1 1 2 2 3 3
2
Sample Input 2 Sample Output 2
7
4 8 7 25 95 97 6
5199
Hide

Please log in to submit a solution to this problem

Log in