Анна мен Бруно — құмар ойындардың шеберлері. Олар ойынның дилері болып табылатын D-taro-мен ойын ойнайды.

Бұл ойында Анна мен Бруно әртүрлі бөлмелерде отырады. Олар бір-бірімен тек бұзылған құрылғы арқылы ғана байланыса алады. D-taro Аннаға бүтін сан береді. Анна мен Бруно үшін бұл ойынның мақсаты — берілген бүтін санды құрылғыны пайдаланып Аннадан Бруноға жіберу.

Ойын басталғанда, ең басында Анна $1$ мен $2\,000$ аралығындағы (шеткі мәндерді қоса алғанда) бүтін $m$ санын жариялайды. Содан кейін олар $Q$ раунд ойнайды. $i$-ші раунд ($1\le i\le Q$) келесідей өтеді.

1. D-taro Аннаға $A_i$ бүтін санын береді.
2. Анна құрылғыға $s_i,t_i$ массивтерін енгізеді. $s_i,t_i$ массивтерінің әрбір элементі $0$ немесе $1$ болуы керек. $s_i,t_i$ массивтерінің ұзындықтары бірдей болуы тиіс және ұзындығы $1$ мен $m$ аралығында (шеткі мәндерді қоса алғанда) болады.
3. $u_i$ массиві $s_i$ және $t_i$ массивтерінен карташа араластыру (riffle shuffle, төменді қараңыз) арқылы алынған массив болсын. Сонда құрылғы Бруноға $u_i$ массивін жібереді.
4. Бруно D-taro-ға бүтін сан жібереді. Егер бұл бүтін сан D-taro Аннаға берген $A_i$ бүтін санымен бірдей болса, Анна мен Бруно осы раундта жеңіске жетеді.

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

Карташа араластыру

Егер $Z$ массивінің элементтерін келесі екі шарт орындалатындай етіп екі топқа бөлуге болса, $Z$ массиві $X$ және $Y$ массивтерінен карташа араластыру арқылы алынған дейміз.

• Бірінші топтағы элементтерден дәл сол ретпен тұратын массив $X$ массивіне тең.
• Екінші топтағы элементтерден дәл сол ретпен тұратын массив $Y$ массивіне тең.

Мысалы, $Z=[1,1,1,0,0,0]$ массиві $X=[1,1,0]$ және $Y=[1,0,0]$ массивтерінен карташа араластыру арқылы алынған, өйткені $Z$ массивінің бірінші, екінші, төртінші элементтерінен дәл сол ретпен тұратын массив $[1,1,0]$ массиві болады, ал $Z$ массивінің үшінші, бесінші, алтыншы элементтерінен дәл сол ретпен тұратын массив $[1,0,0]$ массиві болады.

Екінші жағынан, егер $X=[1,1,0]$, $Y=[1,0,0]$ және $Z=[0,0,0,1,1,1]$ болса, онда $Z$ массиві $X$ және $Y$ массивтерінен карташа араластыру арқылы алынбаған.

Іске асыруรายละเอียดтары

Сізге екі файл жіберу қажет.

Бірінші файл — Anna.cpp. Ол Аннаның стратегиясын іске асыруы керек. Ол келесі функцияларды іске асыруы тиіс. Бағдарлама препроцессордың #include директивасын қолданып Anna.h файлын қосуы керек.

• int Declare()

  Бұл функция басында бір рет шақырылады.

  • Қайтарылатын мән — Анна жариялаған $m$ бүтін саны.
  • $m$ бүтін саны $1$ мен $2\,000$ аралығында (шеткі мәндерді қоса алғанда) болуы керек. Егер бұл шарт орындалмаса, бағдарламаңыз Wrong Answer [1] ретінде бағаланады.

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  Declare функциясы шақырылғаннан кейін, бұл функция $Q$ рет шақырылады. Бұл функцияның $i$-ші шақырылуы ($1\le i\le Q$) $i$-ші раундтың 1-қадамы мен 2-қадамына сәйкес келеді.

  • A параметрі — D-taro Аннаға берген $A_i$ бүтін саны.
  • Қайтарылатын мән — Анна құрылғыға енгізген екі $s_i,t_i$ массивінің жұбы.
  • $s_i,t_i$ массивтерінің әрбір элементі $0$ немесе $1$ болуы керек. Егер бұл шарт орындалмаса, бағдарламаңыз Wrong Answer [2] ретінде бағаланады.
  • $s_i,t_i$ массивтерінің екеуінің де ұзындығы $1$ мен $m$ аралығында (шеткі мәндерді қоса алғанда) болуы керек. Егер бұл шарт орындалмаса, бағдарламаңыз Wrong Answer [3] ретінде бағаланады.
  • $s_i,t_i$ массивтерінің ұзындықтары бірдей болуы керек. Егер бұл шарт орындалмаса, бағдарламаңыз Wrong Answer [4] ретінде бағаланады.

Екінші файл — Bruno.cpp. Ол Бруноның стратегиясын іске асыруы керек. Ол келесі функцияны іске асыруы тиіс. Бағдарлама препроцессордың #include директивасын қолданып Bruno.h файлын қосуы керек.

• long long Bruno(std::vector<int> u)

  Анна құрылғыға массивтерді енгізгеннен кейін, бұл функция бір рет шақырылады. Барлығы бұл функция $Q$ рет шақырылады. Бұл функцияның $i$-ші шақырылуы ($1\le i\le Q$) $i$-ші раундтың 3-қадамы мен 4-қадамына сәйкес келеді.

  • u параметрі — $i$-ші раундта құрылғы Бруноға жіберген $u_i$ массиві.
  • Қайтарылатын мән — Бруноның D-taro-ға жіберген бүтін саны.
  • Қайтарылатын мән D-taro Аннаға берген $A_i$ бүтін санымен бірдей болуы керек. Егер бұл шарт орындалмаса, бағдарламаңыз Wrong Answer [5] ретінде бағаланады.

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

• Сіздің бағдарламаңыз ішкі пайдалану үшін басқа функцияларды іске асыра алады немесе жаһандық айнымалыларды пайдалана алады. Жіберілген файлдар грейдермен бірге компиляцияланып, біртұтас орындалатын файлға айналады. Басқа файлдармен қайшылықтарды болдырмау үшін барлық жаһандық айнымалылар мен ішкі функциялар атаусыз атаулар кеңістігінде (unnamed namespace) жариялануы тиіс. Тексеру кезінде ол Анна мен Бруноның екі процесі ретінде іске қосылады. Аннаның процесі мен Бруноның процесі жаһандық айнымалыларды ортақ пайдалана алмайды.
• Бағдарламаңыз стандартты енгізуді және стандартты шығаруды пайдаланбауы тиіс. Бағдарламаңыз басқа файлдармен ешқандай әдіспен байланыспауы керек. Дегенмен, бағдарламаңыз жөндеу (debugging) ақпаратын стандартты қателер ағынына (standard error) шығара алады.

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

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

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

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

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

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

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

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

$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$

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

Үлгі грейдер стандартты шығаруға келесі ақпаратты шығарады (тырнақшалар түсінікті болу үшін берілген).

• Егер бағдарламаңыз дұрыс деп бағаланса, ол Declare функциясының қайтарған $m$ мәнін “Accepted: 2000” ретінде жазады.
• Егер бағдарламаңыз Wrong Answer түрлерінің бірі ретінде бағаланса, үлгі грейдер оның түрін “Wrong Answer [1]” ретінде жазады.

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

Үлгі грейдер орындалған кезде, әрбір раунд үшін карташа араластыру жалған кездейсоқ сандарды пайдаланып есептеледі. Олардың нәтижелері іске қосулар арасында өзгермейді. Жалған кездейсоқ сандардың бастапқы мәнін (seed) өзгерту үшін үлгі грейдерді келесі жолмен іске қосыңыз.

./grader 2022

Бірінші аргумент бүтін сан болуы керек.

Шектеулер

• $1\le Q\le 1\,000$.
• $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).

Ішкі есептер

1. (5 ұпай) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 ұпай) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 ұпай) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 ұпай) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 ұпай) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 ұпай) Қосымша шектеулер жоқ. Бұл ішкі есеп үшін сіздің ұпайыңыз келесідей есептеледі.

   • $m^*$ осы ішкі есептің барлық тест жағдайлары үшін Анна жариялаған $m$ бүтін сандарының ең үлкені болсын.
   • Сіздің ұпайыңыз келесідей болады.

Мысалдар

Мұнда үлгі грейдерге арналған кіріс деректердің мысалы және сәйкес функция шақырулары берілген.

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

2
42
2000

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

Бұл мысалда $Q\ (=2)$ раунд бар. 1-раундта D-taro Аннаға $A_1\ (=42)$ бүтін санын береді. 2-раундта D-taro Аннаға $A_2\ (=2000)$ бүтін санын береді.

Бұл мысал барлық ішкі есептердің шектеулерін қанағаттандырады.