Fwhy my solution isn't working ? I have tried many my test cases and all are working. http://www.z-trening.com/submit.php?submit=7100060154&subm_code=1
I'm getting WA on all of them
Thanks in advance !
You create a list containing positions of the first 500 ones in the sequence. However, there's a lot more than just 500 ones in a sequence of length 2^31. Generating all positions won't work.
I calculated number of ones in biggest test case and it's < 400. I generated first 400 positions and it worked... Filip has correct solution but grader isn't accepting it :\
@FilipKeri
thocevar je u pravu. Moraš povećati dimenziju niza sa 500 na 65536. Testirao sam i tvoj poslednji post daje pogrresne reultate za num > 125250. Ali, kad povećaš dimenziju 'niz'-a, imaćeš problem TLE, pa umesto sekvencijalnog pretraživanja iskoristi binarno.
Može i drugačiji pristup( i brži ). Jedinice su na pozicijama n*(n+1)/2 + 1.
Razrešavanjem jednačine n*(n+1)/2+1 = 2^31 dobijaš i potrebne dimenzije niza 'niz'.
Pozdrav.
P.S.
Kod Aleksandrovog rešenja (koji ima niz dimenzije 400) rezultat je pogrešan za vrednosti veće od 80200. Npr 80201, 80602,... njegovo rešenje je 0, a trebalo bi 1.
