CSES - Tutkimus
  • Time limit: 4.00 s
  • Memory limit: 128 MB
Uolevin sukuyritys myy omenoita torilla, mutta viime vuosina liiketoiminta on ollut raskaasti tappiollista. Niinpä Uolevi tilasi kaveriltaan Jarkalta tutkimuksen siitä, miten omenan kilohinta vaikuttaa liikevoittoon.

Jarkan työn tuloksena syntyi taulukko $v_0,v_1,\ldots,v_{n-1}$, missä $v_k$ tarkoittaa liikevoittoa, kun omenan kilohinta on $k$. Taulukosta selviää, että tiettyyn rajaan asti kilohinnan kasvattaminen lisää liikevoittoa, mutta tämän jälkeen se vähentää liikevoittoa.

Jarkka suhtautuu kuitenkin vakavasti tietoturvaan ja toimitti taulukon kryptattuna. Jokaista taulukon arvoa $v_k$ vastaa neljä arvoa $a_k$, $b_k$, $c_k$ ja $d_k$. Näistä pystyy laskemaan arvon $v_k$ käyttämällä seuraavaa algoritmia:

[switch]
[m C++]
int decrypt(uint32_t a, uint32_t b, uint32_t c, uint32_t d) {
for(int i = 0; i < 10000; ++i) {
c *= a; d ^= a; c *= b; a ^= c; d += b; a += c;
b -= a; b *= c; c ^= d; c *= d; d ^= a; c += b;
a ^= c; d -= b; c += b; b *= a; d -= a; c -= d;
a += c; c ^= b; b *= a; a ^= d; c -= d; d -= a;
c -= a; d -= b; c += d; b -= c; c += b; c += d;
b *= c; b -= d; b *= a; b ^= c; d -= b; d -= a;
}

a %= 1000000u;
return (int)a - 500000;
}
[/m]
[m Java]
private static int decrypt(int a, int b, int c, int d) {
for(int i = 0; i < 10000; ++i) {
c *= a; d ^= a; c *= b; a ^= c; d += b; a += c;
b -= a; b *= c; c ^= d; c *= d; d ^= a; c += b;
a ^= c; d -= b; c += b; b *= a; d -= a; c -= d;
a += c; c ^= b; b *= a; a ^= d; c -= d; d -= a;
c -= a; d -= b; c += d; b -= c; c += b; c += d;
b *= c; b -= d; b *= a; b ^= c; d -= b; d -= a;
}

while(a < 0) a -= 1000000000;
a %= 1000000;
return a - 500000;
}
[/m]
[/switch]

Ongelmana on kuitenkin, että algoritmin silmukassa on 10000 kierrosta ja arvojen purkaminen on hidasta. Voisitko auttaa Uolevia etsimään aineistosta tehokkaasti kilohinnan, joka tuottaa suurimman liikevoiton?

Syöte

Syötteen ensimmäisellä rivillä on luku $n$, taulukon $v$ koko.

Seuraavaksi syötteessä on jokaiselle $k = 0, 1, \ldots, n-1$ yksi rivi, jossa on välein eroteltuna luvut $a_k$, $b_k$, $c_k$ ja $d_k$.

Tuloste

Ohjelman tulee tulostaa yksi rivi, jolla on kilohinta $h$ siten, että $v_h$ on suurin mahdollinen.

Rajat
  • $2 \leq n \leq 10^5$
  • $0 \leq a_k, b_k, c_k, d_k < 10^6$
  • $-5\cdot 10^5 \leq v_k < 5 \cdot 10^5$
  • $v_0 < \ldots < v_{h - 1} < v_h > v_{h + 1} > \ldots > v_{n-1}$
Esimerkki

Syöte:
4
879479 618085 843425 972716
232376 383233 639282 763757
252843 370229 101963 278328
8702 979114 391694 473238


Tuloste:
2

Syötteessä taulukko $v$ on [-90601, 149544, 241747, 237726], ja maksimi löytyy kohdasta 2 (241747).