У далекој земљи Бајтовији живи \(n\) програмера. За ову земљу је карактеристично то да су њени становници или истинољупци, они који увек говоре истину, или лажљивци, они који увек говоре лажи.

Нашли сте се на одмору у овој чудноватој земљи и желите да откријете једног од лажљиваца. Како не бисте трошили превише времена, желите то да урадите тако што ћете поставити највише \(q\) питања. Свако питање треба да поставите једном од становника Бајтовије и да га питате да ли међу становницима из скупа \(S = \{ s_1, s_2, \dots, s_k \}\) постоји непарно лажљиваца. Скуп \(S\) може да буде празан, а може и да садржи становника коме постављате питање.

Опис функција

Потребно је да имплементирате функцију

• \(\text{NadjiLazova}(n, q)\)

где је \(n\) број становника Бајтовије, \(q\) дозвољени број питања, а функција враћа индекс једног од лажова, или \(-1\) уколико сви становници говоре истину.

Ваш програм може да користи функцију

\(\text{Pitaj}(x, s)\)

која враћа одговор становника са индексом \(x\) на питање “да ли се у скупу \(s\) налзи непарно становника Бајтовије који лажу?”

• Скуп \(s\) треба да проследите као низ међусобно различитих индекса становника.

Становници Бајтовије су индексирани од 1.

Информација о томе ко су истиниљупци, а ко лажљивци је фиксирана пре покретања ваше функције и не зависи од питања које постављате.

Ограничења

Тест примери су подељени у неколико подзадатака. У сваком подзадатку је дато ограничење \(q\), које представља дозвољен број позива функције \(\text{Pitaj}\).

• [10 поена]: \(n = 1000\), \(q = 2000\)
• [12 поена]: \(n = 1000\), \(q = 1000\)
• [25 поена]: \(n = 1000\), \(q = 30\), тачно један становник Бајтовије лаже.
• [33 поена]: \(n = 1000\), \(q = 30\), непаран број становника Бајтовије су лажови.
• [20 поена]: \(n = 1000\), \(q = 30\)

Детаљи имплементације

Потребно је да пошаљете тачно један фајл који имплементира поменуту функцију. Осим тражене функције, ваш фајл може да садржи и додатне глобале променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

int NadjiLazova(int n, int q)

Ваш програм мора улључивати header code.h, у ком је дефинисана функција \(\text{Pitaj}\) следећег потписа:

bool Pitaj(int koga, vector<int> skup)

Уз задатак, обезбеђен вам је “template” фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом и једином реду, бројеве \(n\) и \(q\), и стринг \(s\) дужине \(n\) сачињен од јединица и нула. Сваки карактер стринга \(s\) односи се на једног становника Бајтовије тако да јединица означава оне становнике који лажу, а нула оне који говоре истину.

Затим овај програм позива вашу функцију и штампа повратну вредност на екран. Уколико ваше решење користи функцију \(\text{Pitaj}\) више од \(q\) пута, биће прекинуто са статусом RTE (runtime error).