Республиканская олимпиада по информатике 2010 год, Кызылорда


Есеп A. Қосынды

Ограничение по времени:
2 секунд
Ограничение по памяти:
256 мегабайт

Вовочка математикалық есептерді ойлап табуды ұнатады. Жуырда ол келесі есепті ойлап тапты: берілген $S$-ке, $A \le B$ және $A + (A + 1) + (A + 2) + ... + (B - 1) + B = S$ шарттары орындалатындай, барлық бүтін оң $A$ және $B$ сандарын табыңыз.
Формат входного файла
Енгізу файлда бір бүтін сан $S$ берілген ($1 \le S \le 10^{12}$).
Формат выходного файла
Шығару файлдың бірінші жолында $K$ — табылған $A$ және $B$ жұптарының саны. Келесі $K$ жолдарда екі бүтін саннан, бірінші сан екіншіден үлкен емес — сәйкес жұп. Жұптарды бірінші сандарының өсу тәртібімен шығарыңыз.
Пример:
Вход
25
Ответ
3
3 7
12 13
25 25

комментарий/решение шыгару

Есеп B. Жол

Ограничение по времени:
2 секунд
Ограничение по памяти:
256 мегабайт

Мемлекетте $N$ қала бар. Тек қана кейбір қалалар арасында бар белгілі жүрістермен арқылы ауысуға болады. $K > 1$ және әр $i < K$ үшін $A_i$ және $A_{i + 1}$ арасында жол бар, $A_1$, $A_2$, ... $A_K$ қалалар тізімін жол деп атаймыз. Әр жолдың ұзындығы, яғни жолдағы көршілес қалалар арасындағы жүрістердің қосындысы бар. $1$-ші қаладан $N$-ші қалаға дейнгі барлық жолдарды ұзындығының өсуі бойынша реттейік, ал егер екі жолдың ұзындығы бірдей болса, онда лексиграфиялық тәртіппен реттейміз. Осы тізімдегі алғашқы екі жолды табыңыз (жолдардың саны екіден аз болмайтынына кепіл беріледі).
Формат входного файла
Енгізу файлының бірінші жолында екі бүтін сан $N$ — қалалар саны, $M$ — жолдар саны ($1 \le N \le 20, 0 \le M \le N(N - 1)$). Келесі $M$ жолдың әрқайсысы үш бүтін саннан $S_i$, $T_i$ — $i$-ші жол қосатын қалалардың нөмірлері, $C_i$ — оның ұзындығы тұрады ($1 \le S_i, T_i \le N$, $S_i \ne T_i$, $1 \le C_i \le 100$). Жолдардағы сандар бос орынмен бөлінген.
Формат выходного файла
Шығару файлға екі жолды — табу керек екі жолды тізімдеғі ретімен шығарыңыз. Әр жолдағы бірінші сан $K$ — табылған жолдағы қалалар саны, келесі $K$ сан — қалалардың табылған жолдағы ретімен шығар. Жолдағы сандар бос орынмен бөлінген.
Пример:
Вход
4 4
1 2 3
1 3 1
2 4 4
3 4 2
Ответ
3 1 3 4
3 1 2 4

комментарий/решение шыгару

Есеп C. Ойын

Ограничение по времени:
2 секунд
Ограничение по памяти:
256 мегабайт

Жуырда Амир жаңа ойынды ойлап тапты. Ол $N \times M$ қара және ақ түсті тор көздерден тұратын тақта. Тор көзге басқанда, оған көршілес тор көздер қарама қарсы түске өзгереді. Ойын мақсаты: тақтадағы бастапқы бояудан берілген түпкі бояуды алу. Сіздің міндетіңіз — жеңу, яғни қай тор көздерді және қанша рет басу керек екенін анықтау.
Формат входного файла
Енгізу файлдың бірінші жолында екі бүтін сан берілген $N$ және $M$ берілген ($1 \le N, M \le 10$). Ыңғайлы болу үшін түстер келесі сандармен белгіленген: $1$ — қара, $2$ — ақ. Келесі $N$ жолдың әрқайсысы $1$-ден $2$-ге дейінгі $M$ бүтін саннан сәйкес бастапқы тақтадағы тор көздің түсі берілген. Келесі $N$ жолдың әрқайсысы $1$-ден $2$-ге дейінгі $M$ бүтін саннан сәйкес түпкі тақтадағы тор көздің түсі берілген. Жолдағы сандар бос орынмен бөлінген.
Формат выходного файла
Егер ойынды жеңуге болса, онда әрқайсысы $0$-ден $1$-ге дейінгі $M$ саннан — сәйкес тор көзді қанша рет басу керек, түратын $N$ жолды шығарыңыз. Егер ойынды жеңуге болмаса, онда \t{No solution}-ді шығарыңыз.
Пример:
Вход
2 2
2 1
1 2
1 1
1 1
Ответ
0 1
0 0

комментарий/решение шыгару

Есеп D. Салыстыру

Ограничение по времени:
2 секунд
Ограничение по памяти:
256 мегабайт

Тақтаға $N$ әр түрлі $1$-ден $N$-ге дейінгі бүтін сандарды жазылып және олардың арасында $<$, $>$ таңбалары қойылған. Осыдан кейін, сандарды өшіріп тастады, ал таңбаларды қалдырылды. Өшірілген сандарды қалпына келтіріңіз.
Формат входного файла
Енгізу файлдың бірінші жолында бір бүтін сан $N$ жазылған ($1 \le N \le 10^5$). Екінші жолда ұзындығы $N - 1$ сиволдан тұратын жол берілген. Әр символ $<$ немесе $>$ салыстыру таңбаларының бірі.
Формат выходного файла
Шығару файлға $N$ әр түрлі сандар — бастапқы тізбекті шығарыңыз. Егер бірнеше жауап болса, кез келгенін шығарыңыз.
Пример:
Вход
5
>><<
Ответ
3 2 1 4 5

комментарий/решение шыгару

Есеп E. Нөлдер

Ограничение по времени:
2 секунд
Ограничение по памяти:
256 мегабайт

$1$-ден $X$-ке дейінгі сандарды жазғанда, $0$ цифрының саны $S$-тен кем болмайтындай минимальды $X$-ті табыңыз.
Формат входного файла
Енгізу файлда бір бүтін сан $S$ берілген ($1 \le S \le 10^{18}$).
Формат выходного файла
Шығару файлына бір бүтін сан $X$-ті шығарыңыз.
Пример:
Вход
1
Ответ
10
Вход
2
Ответ
20

комментарий/решение шыгару

Есеп F. Жолдар

Ограничение по времени:
2 секунд
Ограничение по памяти:
256 мегабайт

Екі жол бар. Әр жолдан символдарды өшіруге болады, бірақ қатар өшірілшен символдардың саны $W$-дан аспауы тиіс. Сіздің міндетіңіз — мүмкіндігінше минималды символдар санын жойып, жолдарды бірдей жасау (әр түрлі регистрдың символын әр түрлі деп санаңыз).
Формат входного файла
Енгізу файлдың бірінші жолында $W$ ($1 \le W \le 1500$), ал екінші және үшіншісінде — ұзындығы $1500$ символдан көп емес, сандардан және ағылшын әліпбиінің символдарынан тұратын екі жолдар берілген.
Формат выходного файла
Шығару файлға екі жолдан есептің ережесі бойынша алуға болатын бір жолды шығарыңыз. Егер бірнеше жауап болса, кез келгенін шығарыңыз. Егер жауап жоқ болса, \t{No solution}-ді шығарыңыз.
Пример:
Вход
1
xabcd
aefdz
Ответ
No solution
Вход
2
xabcd
aefdz
Ответ
ad

комментарий/решение шыгару
результаты