Abay Baimukanov

Есеп №1.

Есеп H. Оңай математика

Уақытка қойылған шектеу:

1 second

Жадқа қойылған шектеу:

256 megabytes

Абайдың $n$ оң бүтін саны бар. Ол операциялардың 2 түрін жасай алады: 1) $n$-ді $x$-қа көбейту ($x$ - кез келген оң бүтін сан) 2) $n$-ді $\sqrt{n}$-ға ауыстыру (бұл жағдайда, $\sqrt{n}$ бүтін сан болуы керек) Екі операцияны да бірнеше рет жасауға болады. Абайға осы операцияларды орындау арқылы қандай ең аз санды алуға болатынын анықтаңыз. Абай ең аз санды алу үшін қанша ең аз операциялардың істеу керек екенін анықтаңыз.

Оқу форматы

Бірінші жолда $n$ саны берілген ($1 <= n <= 10^6$).

Жазу форматы

Екі сан шығарыңыз: алуға болатын ең аз сан және сол санды алу үшін керек ең аз операция саны.

Мысалдар:

Оқу

Жауап

10 2

Оқу

Жауап

6 4

Түсініктеме

Бірінші мысалға жауап: 20 -> $ 20 \times 5 = $ 100 -> $ \sqrt {100} = $ 10 — нәтижесінде 2 операция. Екінші мысалға жауап: 5184 -> $ \sqrt {5184} = 72 $ -> $ 72 \times 18 = 1296 $ -> $ \sqrt {1296} = 36 $ -> $ \sqrt {36} = $ 6 — барлығы 4 операция. ( Abay Baimukanov )
комментарий/решение(6) олимпиада

Есеп №2.

Есеп H. Оңай математика

Уақытка қойылған шектеу:

1 second

Жадқа қойылған шектеу:

256 megabytes

Оқу форматы

Бірінші жолда $n$ саны берілген ($1 <= n <= 10^6$).

Жазу форматы

Екі сан шығарыңыз: алуға болатын ең аз сан және сол санды алу үшін керек ең аз операция саны.

Мысалдар:

Оқу

Жауап

10 2

Оқу

Жауап

6 4

Түсініктеме

Есеп №3.

Задача C. From And with love

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Абай массивтерді өте жақсы көреді. Әсіресе массивтің тізбекшелерімен ойнағанды ұнатады. Тізбекше — ол массивтен бірнеше(мүмкін 0) элементтің өшіру арқылы алынатын сандар тізбегі. Сізге $N$ саннан тұратын $A$ массивы беріледі. Массивтің кез-келген бір тізбегін қарастырайық. Олардың биттік AND $X$-қа тең болсын. Тізбекше жақсы деп аталады, егер тізбекте $X$-ке тең сан болмаса. Массивтегі жақсы тізбекшелердің саның табыңыз.

Формат входного файла

Бірінші жолда бір бүтін сан $N$ — $A$ массивының размері берілген. Келесі жолда $N$ бүтін теріс емес сандар берілген — $A$ массивының элементтері.

Формат выходного файла

Жалғыз бүтін сан шығарыңыз — жақсы тізбекшелердің саның. Жауап өте үлкен болуы мүмкін, сол себептен оның $10^9 + 7$ге бөлгендегі қалдығын шығарыңыз.

Система оценки

Есеп 25 тесстен тұрады, әр тест 4 баллға бағаланады:

$1 <= N <= 15$, $0 <= A_i < 2^{20}$. Тест 1 -- 3
$1 <= N <= 10^5$, $0 <= A_i < 2^4$. Тест 4 -- 7
$1 <= N <= 10^5$, $0 <= A_i < 2^{10}$. Тест 8 -- 12
$1 <= N <= 10^5$, $0 <= A_i < 2^{15}$. Тест 13 -- 18
$1 <= N <= 10^6$, $0 <= A_i < 2^{20}$. Тест 19 -- 25

Пример:

Вход

5
0 2 5 3 7

Ответ

Замечание

жақсы тізбекшелердің бірі: 2, 5, 7. Оның биттік AND 0ге тең, және 0 осы тізбекте жоқ . Биттік AND операциясы барлық заманауи бағдарламалау тілдерінде бар, С++ және Java тілінде <<$\string&$>>, ал Pascal тілінде <>. Биттік AND операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $and$ 1 = 1, 1 $and$ 0 = 0\\ 0 $and$ 1 = 0, 0 $and$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі. ( Abay Baimukanov )
комментарий/решение(3) олимпиада

Есеп №4.

Задача A. Кесте

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Сізге бүтін оң сандардан тұратын $N \times M$ кестесі, сондай-ақ $K$ бүтін саны беріледі. Егер кесте шаршы болса және оның элементтерінің соммасы $K$-дан аспаса, кестені жақсы деп атайық. Жақсы ішкі кестелердің санын есептеңіз. Ішкі кесте -- егер сіз сол және оң жақ жиектен бірнеше (мүмкін нөл) бағандарды, сондай-ақ жоғарғы және төменгі жиектен бірнеше(мүмкін нөл) жолдарды алып тастасағанда пайда болатын кесте. Бұл жағдайда ішкі кесте бос болмауы керек.

Формат входного файла

Бірінші жолда $3$ бүтін сандар $N$, $M$, $K$ — кестенің өлшемдері берілген . ($1 <= N, M <= 1500$, $0 <= K <= 10^9$) Келесі $N$ жолдардың әрқайсысында $M$ бүтін оң сандар — кестенің элементтері берілген ($1$-ден $1000$-ға дейінгі сандар).

Формат выходного файла

Бір санды — жақсы ішкі кестелердің санын шығарыңыз.

Система оценки

Есеп $6$ бөлімнен тұрады:

Есептің шартында берілген тесттер. $0$ ұпайға бағаланады.
$N, M <= 2$. $15$ ұпайға бағаланады.
$N, M <= 100$. $17$ ұпайға бағаланады.
$N, M <= 500$. $24$ ұпайға бағаланады.
$N, M <= 1500$ және кестенің элементтері бірге тең. $15$ ұпайға бағаланады.
Есептің бастапқы шектеулері. $29$ ұпайға бағаланады.

Примеры:

Вход

Ответ

Вход

  
6 6 30
4 4 4 1 1 1
2 5 5 3 2 3
3 2 2 4 1 3
1 1 4 4 4 5
1 3 3 4 5 5
2 5 5 4 3 4

Ответ

( Abay Baimukanov )
комментарий/решение(2) олимпиада

Есеп №5.

Есеп D. Массив және сұраныстар

Ограничение по времени:

1.5 seconds

Ограничение по памяти:

256 megabytes

Абай сізге аңызсыз қарапайым есеп әкелді. $N$ натурал саннан тұратын $A$ массиві бар. Оған қоса, $L, R$ түріндегі $Q$ сұраныстары берілген. Сұранысқа жауап — бұл $A_L$, $A_{L+1}$, ..., $A_R$ тізбегінін ішінде, $X$, $2X$, $4X$, ..., $2^K \cdot X$ сандарының бәрі кездесетіндей, $X$ натурал саны табылса, $K$ ($K \ge 0$) санының ең үлкен мәні. Ескерту: натурал сан деп нөлден үлкен бүтін сандарды айтамыз.

Формат входного файла

Бірінші жолда екі $N$ және $Q$ ($1 <= N, Q <= 5 \cdot 10^5$) натурал сандары берілген. Екінші жолда $A$ массиві берілген ($1 <= A_i <= 10^{18}$). Үшінші жолдан бастап сұраныстар, $L$, $R$ ($1 <= L <= R <= N$), беріледі. Әр сұраныс бөлек жолда берілген.

Формат выходного файла

$Q$ жолдарын шығарыңыз, $i$-ші жолда $i$-ші сұранысқа жауап болуы керек.

Пример:

Вход

6 3
6 9 12 24 18 9
2 3
4 6
1 5

Ответ

0
1
2

Замечание

Мысалға түсініктеме: Екінші сұраныста, 18 және 9 сандарын таңдасақ, $K = 1, X = 9$ шығады. Үшінші сұраныста — 6, 12, 24 ($K = 2, X = 6$). ( Abay Baimukanov )
комментарий/решение олимпиада