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$).
Жазу форматы
Екі сан шығарыңыз: алуға болатын ең аз сан және сол санды алу үшін керек ең аз операция саны.
Мысалдар:
Оқу 20Жауап
10 2Оқу
5184Жауап
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$ оң бүтін саны бар. Ол операциялардың 2 түрін жасай алады: 1) $n$-ді $x$-қа көбейту ($x$ - кез келген оң бүтін сан) 2) $n$-ді $\sqrt{n}$-ға ауыстыру (бұл жағдайда, $\sqrt{n}$ бүтін сан болуы керек) Екі операцияны да бірнеше рет жасауға болады. Абайға осы операцияларды орындау арқылы қандай ең аз санды алуға болатынын анықтаңыз. Абай ең аз санды алу үшін қанша ең аз операциялардың істеу керек екенін анықтаңыз.
Оқу форматы
Бірінші жолда $n$ саны берілген ($1 <= n <= 10^6$).
Жазу форматы
Екі сан шығарыңыз: алуға болатын ең аз сан және сол санды алу үшін керек ең аз операция саны.
Мысалдар:
Оқу 20Жауап
10 2Оқу
5184Жауап
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) олимпиада
Есеп №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Ответ
6
Замечание
жақсы тізбекшелердің бірі: 2, 5, 7. Оның биттік AND 0ге тең, және 0 осы тізбекте жоқ .
Биттік AND операциясы барлық заманауи бағдарламалау тілдерінде бар, С++ және Java тілінде <<$\string&$>>, ал Pascal тілінде <комментарий/решение(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$ ұпайға бағаланады.
Примеры:
Вход 3 3 12 1 2 3 5 2 5 3 2 4Ответ
12Вход
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Ответ
71( 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
)
комментарий/решение олимпиада