Binarna aproksimacija

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 128 MB
Avtor:
  • Mitja Trampuš
  • UPM 2013

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Za poljuben neničeln d-dimenzionalen vektor (neničeln pomeni, da je vsaj ena koordinata različna od nič) x=(x_1, x_2, \ldots, x_d), definiramo njegovo binarno kotno aproksimacijo kot neničeln binarni vektor b=(b_1, b_2, \ldots, b_d), ki minimizira kot med x in b. "Binarni" pomeni b_i \in \{0,1\}.

Kot \phi med vektorjema x in b lahko neodvisno od števila dimenzij izpeljemo iz vsem dobro znane enačbe, ki na vsako stran enačaja postavi drugačen zapis skalarnega produkta vektorjev x in b:

||x||_2 ||b||_2 \cos \phi = \sum_i(x_i b_i)

Pri tem ||\cdot||_2 označuje dolžino vektorja.

Naloga

Napiši program, ki za podan vektor x izračuna njegovo binarno kotno aproksimacijo. Obstaja lahko več aproksimacij b z enakim kotom do vektorja x, zato poišči najmanjšo - če aproksimacijo b=(b_1, b_2, \ldots, b_d) interpretiramo kot število v dvojiškem zapisu b_1 b_2 \ldots b_d, naj bo to število čim manjše.

Vhodni podatki

V prvi vrstici se nahaja število dimenzij d. Naslednjih d vrstic vsebuje po eno komponento x_i vektorja x. Vektor x bo neničeln, njegove komponente po absolutni vrednosti ne bodo presegle 100 in bodo podane na največ 4 decimalna mesta.

Omejitve vhodnih podatkov

  • d \leq 10\ 000

Izhodni podatki

Izpiši binarno kotno aproksimacijo vektorja x, vsako komponento v samostojni vrstici.

Primeri

Vhod

3
0.707
0
0.707

Izhod

1
0
1

Vhod

4
5
12
-3.1415
10

Izhod

1
1
0
1
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task