Анна мен Бруно — археологтар. Олар Ирандағы ежелгі қирандыларды зерттеп жатыр.

Олардың міндеттері келесідей: Анна қирандыларды аралап, жәдігерлерді табады, ал Бруно базалық лагерьде нәтижелерді талдайды.

Олардың зерттеуі $Q(=1\,000)$ күнге жоспарланған. Күн сайын Анна байланыс құрылғысын пайдаланып, Бруноға нәтижелерді жібереді. Әр күннің нәтижесі бір $X$ бүтін санымен өрнектеледі.

Анна байланыс құрылғысын күніне тек бір рет қана қолдана алады. Ол $0$ немесе $1$ сандарынан тұратын ұзындығы $N(=150)$ болатын тізбекті жібере алады.

Алайда құрылғы бұзылып қалған. Ұзындығы $N$ тізбекте бірнеше бұзылған орын бар. Бұзылған орында құрылғы нақты орнатылған мәнге қарамастан әрқашан $0$ мәнін жібереді. Анна тізбекті жіберген кезде бұзылған орындардың индекстерін көре алады. Бірақ Бруно оларды білмейді. Бұзылған орындардың орналасуы мен олардың саны күн сайын өзгеруі мүмкін.

Олардың зерттеуі кешігуі мүмкін деген қауіп бар. Сіз Иранда өтетін халықаралық программалау олимпиадасына қатысуға үміткер болғандықтан, Анна мен Бруно сізден олардың зерттеу нәтижелерін жіберетін программа жазып беруді сұрайды.

Тапсырма

Анна мен Бруно арасындағы байланысты жүзеге асыратын екі программа жазыңыз.

• Тізбектің ұзындығы $N$, жіберілетін бүтін сан $X$, бұзылған орындар саны $K$ және бұзылған орындардың позициялары $P$ берілгенде, бірінші программа Анна жіберетін $S$ тізбегін орнатады.
• Бруно қабылдап алған $A$ тізбегі берілгенде, екінші программа $X$ бүтін санын қалпына келтіреді.

Байланыс құрылғысы дұрыс жұмыс істейтін орында $S$ тізбегі мен $A$ тізбегінің мәндері бірдей болады. Бұзылған орында $S$ тізбегінің мәндеріне қарамастан $A$ тізбегінде әрқашан $0$ мәні болады.

Іске асыру егжей-тегжейі

Сіз бір программалау тілінде жазылған екі файлды тапсыруыңыз керек.

Бірінші файл — Anna.c немесе Anna.cpp. Бұл файл Анна жіберетін тізбекті орнатады және келесі функцияны іске асырады. Программа Annalib.h файлын қосуы (include) керек.

• void Anna( int N, long long X, int K, int P[] )

  Әрбір тест жағдайы үшін бұл функция $Q=1\,000$ рет шақырылады.

  • N параметрі — жіберілетін тізбектің ұзындығы.
  • X параметрі — жіберілетін бүтін сан.
  • K параметрі — бұзылған орындардың саны.
  • P[] параметрі — бұзылған орындардың позицияларын сипаттайтын ұзындығы $K$ болатын тізбек.

  Anna функциясының ішінде келесі функция шақырылуы тиіс.

  • void Set( int pos, int bit )

    Бұл функция байланыс құрылғысы арқылы жіберілетін $S$ тізбегіндегі бір битті орнатады.

    • pos параметрі — мән орнатылатын орынның позициясы. pos мәні $0$ мен $N-1$ аралығындағы (қоса алғанда) бүтін сан болуы керек. Позициялар $0$-ден бастап нөмірленетініне назар аударыңыз. Егер функция осы аралықтан тыс параметрмен шақырылса, программаңыз Wrong Answer[1] ретінде бағаланады. Бұл функцияны бірдей pos параметрімен бір реттен артық шақыруға рұқсат етілмейді. Егер ол бірдей параметрмен бір реттен артық шақырылса, программаңыз Wrong Answer[2] ретінде бағаланады.
    • bit параметрі — тізбектің pos-шы позициясына орнатылатын мән. bit мәні $0$ немесе $1$ болуы керек. Егер ол басқа параметрлермен шақырылса, программаңыз Wrong Answer[3] ретінде бағаланады.

  Set функциясы Anna функциясының ішінде дәл $N$ рет шақырылуы керек. Anna функциясы аяқталған кезде Set функциясының шақырылу саны $N$-нен өзгеше болса, программаңыз Wrong Answer[4] ретінде бағаланады.

  Егер Аннаның функция шақыруы жарамсыз деп танылса, программаңыз бірден тоқтатылады.

Екінші файл — Bruno.c немесе Bruno.cpp. Бұл файл зерттеу нәтижесін білдіретін бүтін санды қалпына келтіреді және келесі функцияны іске асырады. Программа Brunolib.h файлын қосуы керек.

• long long Bruno( int N, int A[] )

  Әрбір тест жағдайы үшін бұл функция $Q=1\,000$ рет шақырылады.

  • N параметрі — Бруно қабылдап алған тізбектің ұзындығы.
  • A параметрі — ұзындығы $N$ болатын бүтін сандар тізбегі. Бұл — Бруно қабылдап алған тізбек.
  • Bruno функциясы $X$ мәнін қалпына келтіріп, оны қайтаруы (return) керек.

Бағалау тәртібі

Бағалау келесі түрде жүргізіледі. Егер программаңыз Wrong Answer деп танылса, ол бірден тоқтатылады.

1. cnt = 0 деп орнатылады.
2. Anna функциясы бір рет шақырылады.
3. $S$ — Anna функциясы орнатқан тізбек болсын. $S$ тізбегіндегі $P$-да көрсетілген позицияларға $0$ мәнін қойып, $A$ тізбегін аламыз. $A$ параметрімен Bruno функциясы бір рет шақырылады.
4. cnt = cnt +1 деп орнатылады. Егер $\mathrm{cnt}<Q$ болса, (2)-ге өтеміз. Егер $\mathrm{cnt}=Q$ болса, (5)-ке өтеміз.
5. Программаңызға ұпай беріледі.

Маңызды ескертпелер

• Орындалу уақыты мен жад көлемі Бағалау тәртібінің (1), (2), (3), (4) қадамдары үшін есептеледі.
• Программаңыз (2)-дегі Anna немесе (3)-тегі Bruno функциясын шақыру кезінде Wrong Answer алмауы тиіс. Программаңыз орындалу уақытындағы қатесіз (runtime error) жұмыс істеуі керек.
• Программаңыз ішкі қажеттіліктер үшін басқа функцияларды іске асыра алады немесе глобалды айнымалыларды пайдалана алады. Жіберілген программалар грейдермен бірге компиляцияланып, бір орындалатын файлға айналады. Басқа файлдармен қайшылық туындамауы үшін барлық глобалды айнымалылар мен ішкі функциялар static деп жариялануы керек. Бағалау кезінде Анна мен Бруноның программалары 2 бөлек процесс ретінде орындалатындықтан, олар глобалды айнымалыларды ортақ пайдалана алмайды.
• Процесс барысында Anna және Bruno функцияларының әрқайсысы $Q=1\,000$ рет шақырылады. Программаларыңызда қолданылатын айнымалылар тиісті түрде инициализациялануы керек.
• Программаңыз стандартты енгізу мен стандартты шығаруды пайдаланбауы керек. Программаңыз ешқандай әдіспен басқа файлдармен байланыспауы керек.

Компиляция және сынақ ретінде іске қосу

Сіз жарыс веб-парақшасынан программаңызды тексеруге арналған үлгі грейдері бар архив файлын жүктей аласыз. Архив файлында программаңыздың үлгі бастапқы коды да бар.

Үлгі грейдер grader.c немесе grader.cpp болатын бір бастапқы файлдан тұрады. Мысалы, егер программаларыңыз Anna.c мен Bruno.c немесе Anna.cpp мен Bruno.cpp болса, программаларыңызды компиляциялау үшін келесі командаларды орындайсыз.

• C

  gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

  g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Компиляция сәтті аяқталғанда, орындалатын grader файлы жасалады.

Нақты грейдер үлгі грейдерден өзгеше екенін ескеріңіз. Үлгі грейдер стандартты енгізуден деректерді оқып, нәтижелерді стандартты шығаруға жазатын бір процесс ретінде орындалады.

Үлгі грейдерге арналған кіріс деректер

Үлгі грейдер стандартты енгізуден келесі деректерді оқиды.

• Бірінші жолда бір бүтін сан $Q$ берілген.
• Одан кейін $Q$ сұраныс туралы ақпарат беріледі.

• Әрбір сұраныс туралы ақпарат келесідей екі жолдан тұрады.

  • Бірінші жолда бос орын арқылы бөлінген үш бүтін сан $N$, $X$, $K$ берілген. Бұл жіберілетін тізбектің ұзындығы $N$ екенін, Анна жіберетін бүтін сан $X$ екенін және $K$ бұзылған орын бар екенін білдіреді.
  • Екінші жолда бос орын арқылы бөлінген $K$ бүтін сан $P_0,P_1,\cdots,P_{K-1}$ берілген. Бұл әрбір $i$ ($0\le i\le K-1$) үшін тізбектегі $P_i$-ші орын бұзылғанын білдіреді.

Үлгі грейдердің шығыс деректері

Программа сәтті аяқталғанда, үлгі грейдер стандартты шығаруға келесі ақпаратты жазады. (Тырнақшалар іс жүзінде жазылмайды.)

• Егер программаңыз Wrong Answer деп танылса, үлгі грейдер оның түрін “Wrong Answer [1],” түрінде жазады және программаңыз тоқтатылады.
• Егер Anna функциясына жасалған әрбір шақыру Wrong Answer деп танылмаса, үлгі грейдер “Accepted” сөзін және $L^*$ мәнін жазады. $L^*$ мәні туралы Ішкі есептер бөлімінен қараңыз.

Егер программаңыз Wrong Answer-дің бірнеше түріне сәйкес келсе, үлгі грейдер олардың тек біреуін ғана хабарлайды.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады.

• $Q=1000$.
• $N=150$.
• $0\le X\le 1\,000\,000\,000\,000\,000\,000$.
• $1\le K\le 40$.
• $0\le P_i\le N-1$ ($0\le i\le K-1$).
• $P_i<P_{i+1}$ ($0\le i\le K-2$).

Ішкі есептер

• Осы есептің барлық тест жағдайлары бойынша келесі мәннің минимумын $L^*$ деп белгілейік.

  • $K\le L$ болатын әрбір сұраныс үшін Бруно $X$-тің дұрыс мәнін табатындай ең үлкен $L\le40$ бүтін саны.

• Бұл есептің ұпайы келесі тәсілмен есептеледі:

  • Егер $L^*=0$ болса, ұпай — 0 ұпай.
  • Егер $1\le L^*\le14$ болса, ұпай — 8 ұпай.
  • Егер $15\le L^*\le37$ болса, ұпай — $(L^*-15)\times2+41$ ұпай.
  • Егер $38\le L^*\le40$ болса, ұпай — $(L^*-38)\times5+90$ ұпай.

Мысалдар

Мұнда грейдерге арналған кіріс деректер мысалы және соған сәйкес функция шақырулары берілген. Келесі мысал $Q=2$, $N=3$ болғандықтан осы есептің шектеулерін қанағаттандырмайтынына назар аударыңыз.

Кіріс деректер 1

2
3 14 1
2
3 9 2
0 1

Функция шақыру үлгілері

Мұндағы Anna(...), Bruno(...), Anna(...), Bruno(...) функцияларының параметрлері келесідей.