Задача A. Манхэттен қашықтығы

Жазықтықта $N$ түрлі нүктелер берілген. (x1, y1) және (x2, y2) нүктелерінің ара қашықтығын келесідей есептейміз |x1 - x2| + |y1 - y2|. Әр нүкте үшін оған ең жақын нүктенің бірін табу керек. Кіріс файлдың бірінші жолында бір бүтін жазылған N (1 < $N$ <= $10^5$). Келесі N жолда екі саннан жазылған — нүктелердің координаталары. Координаталар – модулі $10000$ аспайтын бүтін сандар. Бір жолдағы сандар аралары пробелмен бөлінген. Шығыс файлда аралары пробелмен бөлінген $N$ сан жазылу керек: i-ші сан i-ші нүктеге ең жақын нүктелердің біреуінің номері. Нүктелер кіріс файлда берілген ретпен бірден бастап номерленеді. Вход

4
0 0
1 1
0 1
1 0

Ответ

3 4 1 1

Есеп B. Ішкі тізбек

$N$ бүтін саннан құралған тізбек берілген. Оның лексикографиялық ретімен $K$-шы өсетін ішкі тізбегін табу керек. Ішкі тізбек, бастапқы тізбектен нөл немесе одан да көп, бірақ барлығын емес, санды сызып тастау арқылы жасалады. Өсетін тізбекте әр сан оған дейінгі саннан, егер ол бар болса, үлкен болып келеді. $A = {a_1, a_2, \dots a_n}$ тізбегі лексикографиялық ретімен $B = {b_1, b_2, \dots b_m}$ тізбегінен кіші болады, егер $A$ — $B$ тізбегінің префиксі (басындағы бөлігі), немесе сондай $k$ саны табылады: $i < k$ болғанда $a_i = b_i$ , және $a_k < b_k$. Кіріс файлдың бірінші жолында екі бүтін сан жазылған $N$ және $K$ (1 < $N$ <= $60$, $K >= 1$). Келесі жолда шамасы $0$-ден $10^9$ дейін $N$ бүтін сан жазылған. Жолдағы сандар аралары пробелмен бөлінген. Ізделінді ішкі тізбек бар болуы кепілді. Шығыс файлдың бірінші жолында $M$ саны жазылу керек – табылған тізбектің ұзындығы. Екінші жолда аралары пробелмен бөлінген $M$ сан жазылу керек – табылған тізбектің сандары. Вход

3 2
1 1 2

Ответ

2
1 2

Есеп C. Трубалар

суретте келтірілген 11 түрлі трубаларды, әр труба бір ұяшықты алатындай және олар бір немесе бірнеше тұйық жүйе құрайтындай етіп $NxM$ өлшемді тақтада қанша түрлі әдіспен орналастыруға болады? Трубалардың жүйесі тұйық, егер кез-келген трубаның ұштары басқа трубанын ұшымен қосылып тұрса.

суретте тұйық жүйенің мысалы көрсетілген. Тақтада бос ұяшықтар қалуы мүмкін. Жауапты $P$ санының модулімен шығару керек ($0$ <= жауап < $P$). Кіріс файлдың бірінші жолында үш бүтін сан жазылған $N$, $М$ және $P$ (1 <= $N$ <= 8, 1 <= $M$ <= 8, 2 <= $P$ <= $10^9$). Сандар аралары пробел арқылы бөлінген. Шығыс файлда бір бүтін сан жазылу керек – есептің жауабы. Вход

2 2 10

Ответ

1

Жауаптагы сурет:

Есеп D. Түсқағаз

Жұмысшыларға ені $X$, биіктігі $Y$ болатын қабырғаны түсқағазбен жабыстыру керек. Түсқағаздың әрбір рулоны ені $A$, ал биіктігі $B$ сантиметрді құрайды. Әрбір рулон биіктіктері бірдей B горизонталь жолдарға бөлінген. Жолдардың барлығы келесі ретпен K түрлі түске боялған (жолдар төменнен жоғары қарай нөмірленеді):
1, K+1, 2K+1, .. нөміріндегі жолдар 1 нөмірлі түске;
2, K+2, 2K+2, .. нөміріндегі жолдар 2 нөмірлі түске;
...
K, 2K, 3K, .. нөміріндегі жолдар $K$ нөмірлі түске боялған.
Горизонталь бойынша тұрған көршілес жолдардың түстері сәйкес келетіндей, ал вертикаль бойынша түстер дәл рулондағыдай кездесіп отыратындай етіп түсқағазды қабырғаға жабыстыру керек (алайда төменгі жолдың түсі кез- келген бола алады). Берілген қабырғадан алдынғы қабырғаларды толық жабыстырып болғаннан кейін $N$ қалдық рулон қалды. Әрбір қалған қалдықтың ені рулонның енімен бірдей. Берілген шарттарды қанағаттандыратын және осы қабырғаны толық жабатындай ең аз дегенде қаншама бүтін рулон сатып алу керек? Бүтін емес рулонды сатып алуға болмайды. Түсқағаздарды жолдардың шекаралары бойынша ғана қырқуға болады. Кіріс файлдың бірінші жолы алты бүтін оң саннан тұрады $X$, $Y$, $A$, $B$, $K$, $N$ (1 <= $X$, $Y$, $A$, $B$ <= $10^9$, 1 <= $K, N$ <= $5 * 10^5$, $X mod A = 0$, $B mod K = 0$). Келесі $N$ жолдың әрқайсысында екі бүтін сан жазылған: біріншісі— қалдықтың төменгі жолындағы түс нөмірі, екіншісі – қалдықтың биіктігі (сантиметрмен берілген). Әрбір қалдық – бүтін рулонның бөгілі болатынына кепіл беріледі. Жолдағы сандар бос орын арқылы бөлінген. Шығыс файлға бір бүтін сан жазылу керек – ең аз дегендегі сатып алынатын рулондар саны. Вход

5 5 1 10 10 10
6 4
6 2
3 3
2 4
10 1
5 2
6 2
8 3
2 5
2 5

Ответ

2

Есеп G. Google Maps

Сіз Google Maps сервисін қолданып n=404&v=14&t=trtrstsrtstrt – бұл Алматы қаласының сілтемесі. Мұндағы t параметрі келесі жолмен құрастырылады: ең алдымен бүкіл Жер - «t» жолымен берілген шаршы

бұл шаршы 4 тең шаршыларға бөлінеді: «tq», «tr», «tt», «ts»

әрбір пайда болған шаршы дәл сол секілді (рекурсивті) 4 тең шаршыларға бөлінеді де, берілген параметрге «q» (сол жақ жоғарғы), «r» (оң жақ жоғарғы), «t» (сол жақ төменгі), «s» (оң жақ төменгі) жалғаулары жалғанады. Қазіргі тұрған жеріңіз белгілі болса, t параметрін қалай табуға болады? Жер шаршысының қабырғасының ұзыдығы 2 – нің $N$ дәрежесіне тең және оның сол жақ төменгі бұрышының координатасы (0,0) болсын. Координаттары бүтін (x,y) болатын P нүктесі берілген. Осы нүктені қамтитын ең кіші мүмкін шаршы үшін t параметрін табыңыз. (мұндағы P нүктесі шаршы қабырғасында жатпауы тиіс) Кіріс файлда үш бүтін сан жазылған – $N$ (0 < $N$ < 1000) және Р нүктенің x және y координаталары, 0 < x,y < $2^N$ (2 – нің N дәрежесі). Шығыс файлда бір жол жазылу керек – есептің жауабы. Вход

8 5 3

Ответ

tsq

оң жақ төменгі сол жақ жоғарғы

Есеп H. Жұлдызды аспан

Денис Назаров, Уфа

Қыстың жарқын кешінде информатикадан Республикалық олимпиаданың қазылар алқасы Иван Васильевич асықпай үйіне бара жатты. Кей уақыттарда оның назары, өзінің сұлулығымен таң қалдырған бұлтсыз аспанға түсіп тұрды. Үйіне келгенде ол, жұлдыздар координаталар жазықтығында тек бүтін санды координаталарға ие нүктелерде орналасатындай, жұлдызды аспанның картасын құруды шешті. Ені мен ұзындығының координаталар жазықтығында бірлігі ретінде 1 жарық жылды алуды шешті. Иван Васильевич жұлдыздарды келесі ереже бойынша бөлді: жұлдыз қандай да бір жұлдыз шоғырына тиісі болады, егер бұл жұлдыз шоғырында кем дегенде осы жұлдызға дейінгі координаталар жазықтығында ара қашықтығы K жарық жылдан аспайтындай тағы бір жұлдыз табылса. Бір жұлдыз, екі жұлдыз шоғырына тиісті бола алмайды және кез-келген жұлдыз шоғырында кем дегенде бір жұлдыз бар. Бұдан кейін Иван Васильевич жұлдыздар шоғырының центрін келесі ережемен табуды шешті: егер жұлдызды картадан алып тастағанда, жұлдыздар шоғыры тағы да бірнеше жұлдыздар шоғырына бөлінетін болса, ол жұлдыздар шоғырының центрі болып есептеледі. Бір жұлдыздар шоғырында бірнеше центр болуы мүмкін. Екі немесе одан да аз жұлдыздардан құралған жұлдыздар шоғырында, анықтама бойынша центірі болмайды. Иван Васильевичке барлық жұлдыздар шоғырларының центрлерін табуға көмектесіңіз. Кіріс файлда барлық жұлдыздардың координаталары жазылған (xi,yi). Жұлдыздар координаталарының жұптары әр түрлі. Жұлдыздардың жалпы саны 3000-нан аз, бірақ 1-ден көп. Жұлдыздардың координаталарының абсолют шамасы 214 -нен аз болатын бүтін сандар. Соңғы жолда $10^9$-нен кіші теріс емес $K$ бүтін саны жазылған. Сіздің программаңыз шығыс файлға екі бүтін сан шығаруы тиіс. Бірі – жұлдыздар шоғырының жалпы саны, екіншісі – олардың жұлдыздар картасындағы центрлерінің жалпы саны. Вход

4
0 0
1 1
0 1
1 0

Ответ

3 4 1 1