Задача 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

Задача E. Графты бояу

$N$ төбесі және $M$ қабырғасы бар бағытталмаған графты қарастырайық. Берілген графтың төбелерін $K$ түске қанша әдіспен бояп шығуға болады? Екі бояу әдісі бірдей болып есептеледі, егер қабырғалардың тізімі өзгермейтіндей етіп және сәйкес төбелердің түстері бірдей болатындай етіп графтың төбелерін қайтадан нөмірлеп шығуға болатын болса. Мысалы, суреттегі екі бояу әдісі бірдей (сәйкес қайтадан нөмірлеу: 1->1, 2->2, 3->4, 4->3).

Кіріс файлдың бірінші жолында үш бүтін сан жазылған $N$, $М$ және $K$ (1 <= $K$ <= 10, 1 <= $N$ <= 10, 1 <= $M$ <= 100). Келесі $M$ жолдың әрқайсысында мәні 1 мен $N$ аралығында бүтін сандар берілген — граф қабырғалары. Графта қайталанатын қабырғалар және тұзақтар кездесуі мүмкін. Әр қабырғаның 7-ден аспайды. Жолдардағы сандар аралары пробелмен бөлінген. Шығыс файлда бір бүтін сан жазылу керек – түрлі бояулардың саны. Вход

4 3 2
1 2
2 3
2 4

Ответ

8

Есеп F. Көпбұрыш

Қабырғалары өзара қиылыспайтын көпбұрыш берілген. Осы көпбұрыштың ішіндегі немесе қабырғаларың бойындағы, координаталары бүтін сан болатын нүктелер санын есептеу керек. Кіріс файлдың бірінші жолында $N$ (1 <= $N$ <= $10^5$) бүтін саны жазылған. Келесі $N$ жолдың әрқайсысында модульдері 10000 аспайтын, үтірден кейін 3 цифрдан көп болмайтын екі нақты сан жазылған — (x, y) ретімен берілген көпбұрыш төбелерінің координаталары (x, y бүтін емес). Көпбұрыштың периметірі $10^6$ (1,000,000) аспайды. Жолдағы сандар аралары бос орынмен бөлінген. Шығыс файлға бір бүтін сан жазылу керек — есептің жауабы. Вход

3
14.815 43.958
21.457 34.883
21.802 50.559

Ответ

48