Барои ин саҳифа компютери ҳақиқӣ лозим аст: парвандаҳо, терминал ва скрипт истифода мешаванд. Хонандае, ки танҳо телефон дорад, онро хонда ва ба саволҳо ҷавоб дода метавонад.
Масъала
n адади бутун ва адади k дода шудаанд. Ҷуфтҳои мавқеъҳои i < j-ро бишуморед, ки барояшон aᵢ + aⱼ = k. Маҳдудиятҳо: 1 ≤ n ≤ 2 · 10⁵, −10⁹ ≤ aᵢ, k ≤ 10⁹.
Вуруд
Баромад
Ҳамаи ҷуфтҳо барои калонтарин n 2 · 10¹⁰ қадам аст, барои ҳамин ҳал бо map мешуморад. Барои ҳар адади x шарикони он ададҳои баробар ба k − x мебошанд. Ҳар қиматро як маротиба бишуморед, шарикони ҳар ҷузъро ҷамъ кунед ва натиҷаро ду баробар кам кунед, чунки ҳар ҷуфт аз ҳарду канор ёфт мешавад:
Намуна мегузарад. Оё ҳал дуруст аст? Тахмин накунед: санҷед.
Се барнома ва як скрипт
Дар мусобиқаҳо ҳамин тавр мекунанд: парвандаи ҳалли шумо айнан ҳамон тавр ки пешниҳод мекунед, санҷиши ҳамаи вариантҳо дар парвандаи дуюм, генератор дар сеюм ва скрипте, ки онҳоро бо ҳам муқоиса мекунад.
Санҷиши ҳамаи вариантҳо ҳар ҷуфтро месанҷад. Он барои 2 · 10⁵ адад аз ҳад суст аст, вале дар он ҷое барои хато нест:
Генератор як тести тасодуфиро чоп мекунад. Он аз сатри фармон ду адад мегирад: рақами тест, ки тухми ададҳои тасодуфӣ аст, ва калонтарин n.
argv[1] аввалин калимаест, ки баъд аз номи барнома навишта мешавад, ва atoi онро ба int табдил медиҳад. Рақами тест тухм аст, барои ҳамин gen 17 10 > in.txt тести 17-ро ҳар вақт лозим шавад, бармегардонад.
Скрипт се барномаро ҳазор бор иҷро мекунад. Аввал онҳоро ба sol, brute ва gen компилятсия кунед, масалан бо g++ -O2 pairs.cpp -o sol. Дар Linux, macOS, WSL ё Git Bash инро ҳамчун stress.sh нигоҳ доред ва bash stress.sh-ро иҷро кунед:
Барои ҳар тест скрипт вурудро месозад, ҳарду барномаро иҷро мекунад ва баромадҳоро муқоиса мекунад; diff -w фосилаҳоро ба ҳисоб намегирад. Дар аввалин тафовут он тест ва ҳарду ҷавобро чоп мекунад:
Агар вай фавран «All 1000 tests passed» нависад, санҷед, ки барномаҳо воқеан иҷро шудаанд. Скрипте, ки ягон барномаро наёфтааст, ду баромади холиро ҳазор бор муқоиса мекунад ва ҳамаро мегузаронад.
Тести ғалатдиҳандаро кӯтоҳ кунед
Тести хурдтарро пайгирӣ кардан осонтар аст. Аз генератор тестҳои хурдтар талаб кунед: скриптро бо gen $i 2 иҷро кунед, ва он ба зудӣ дар тести ду адад қатъ мешавад:
Ё онро бо даст кӯтоҳ кунед. Як ададро нест кунед (ва n-ро мувофиқан кам кунед) ва ҳарду барномаро боз иҷро кунед. Агар онҳо ҳанӯз фарқ кунанд, тағйирро нигоҳ доред; агар не, ададро баргардонед. Аз тести 10 ҳаштҳо, шашҳо ва дуи яккаро як-як хориҷ мекунем. Се сеи боқимонда ҳанӯз ғалат медиҳанд (4 муқобили 3), ва ду то аз онҳо низ (2 муқобили 1). Хурдтарин тести ғалатдиҳанда ва аст. Хаторо дар он пайгирӣ кунед: