Есеп А. Теңбүйірлі үшбұрыштар

Теңбүйірлі үшбұрыш — бұл ұзындықтары бойынша екі қабырғасы тең үшбұрыш. Қабырғаларының ұзындықтары $1$-ден $N$-ға дейін бүтін сан болатын, теңбүйірлі үшбұрыштардың сандарың табыңыз. Еске салайық, үшбұрыштың әр қабырғасы оның басқа екі қабырғасының қосындысынан кіші болуы керек. Бірінші жолда бір бүтін сан берілген $N$. Есептің жауабын шығарыңыз. Бұл есеп 10 тесттен тұрады, әр тест 10 ұпайға бағаланады:

1. 1-2 тест үшін $1 <= N <= 100$ орындалады.
2. 3-5 тест үшін $1 <= N <= 5000$ орындалады.
3. 6-10 тест үшін $1 <= N <= 10^6$ орындалады.

Вход

4

Ответ

12

Мысалдағы теңбүйірлі үшбұрыштар:
1 1 1
2 2 1
2 2 2
2 2 3
3 3 1
3 3 2
3 3 3
3 3 4
4 4 1
4 4 2
4 4 3
4 4 4

Задача B. Жұп сандар

Сізге $L$ және $R$ сандары беріледі. $L$-дан $R$-ға дейін барлық цифралары ондық санау жүйесінде жұп болатын сандардың санын табу керек. Есептің жауабын табыңыз. Бірінші жолда екі натурал $L$ және $R$ $(1 <= L <= R <= 10^{10})$ сандары берілген. Бірінші жолда есептің жауабын — бір бүтін санды шығарыңыз. Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

1. $1 <= L <= R <= 10^2$. 1-2 нөмердегі тесттер.
2. $1 <= L <= R <= 10^6$. 3-4 нөмердегі тесттер.
3. $1 <= L <= R <= 10^{10}$. 5-10 нөмердегі тесттер

Вход

3 10

Ответ

3

Задача C. Мейрамхана

Мейрамханада $n$ даяршы бар. Олар $1$-ден $n$-ға дейін нөмірленген. Үстелде $m$ стақан тұр. Олар $1$-ден $m$-ге дейін нөмірленген. Бастапқыда барлық стақан бос. Әр даяршы бірнеше стақанға сусын құюы керек. $i$-ші даяршы $l_i$-ден $r_i$-ге дейінгі стақандарға $x_i$ миллилитр сусын құюы керек. Бір даяршы ұйықтап қалып, стақандарға сусын құюды ұмытып кетті. Одан басқа барлық даяршылар тапсырмаларын орындады. Сізге әр стақандағы сусын мөлшері берілген. Сізге ұйықтап қалу мүмкін даяршылардың тізімін табу керек. Бірінші жолда $n$ және $m$ $(1 <= n, m <= 10^5)$ — даяршылар саны және стақандар саны берілген. Келесі $n$ жолдарда $l_i$, $r_i$ және $x_i$ $(1 <= l_i <= r_i <= m$, $1 <= x_i <= 10^3)$ үш сандар берілген. Келесі жолда $m$ бүтін сандар берілген, $a_1$, $a_2$, $\dots$, $a_m$, мұнда $a_i$ $i$-ші стақандағы сусынның миллилитр санын көрсетеді. Ұйықтап қалу мүмкін даяршылардың нөмірлерін өсу ретінде шығарыңыз. Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

1. $1 <= n, m <= 100$. 1-2 нөмердегі тесттер.
2. $1 <= n, m <= 3000$. 3-5 нөмердегі тесттер.
3. $1 <= n, m <= 10^5$. 6-10 нөмердегі тесттер

Вход

5 4
1 3 2
2 4 3
1 3 2
3 4 1
3 3 1
2 5 7 4

Ответ

1 3

Задача D. Бөлгіштер

Сізге $n$ бүтін саны берілген. $1$-ден $n$-ге дейін бөлгіштердің саны жұп болатын сандардың санын табыңыз. Бірінші жолда бүтін $n$ $(1 <= n <= 10^9)$ саны берілген. Есептің жауабын шығарыңыз. Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

1. $1 <= n <= 1000$. 1-6 нөмердегі тесттер.
2. $1 <= n <= 10^5$. 7-8 нөмердегі тесттер.
3. $1 <= n <= 10^9$. 9-10 нөмердегі тесттер

Вход

10

Ответ

7

Мысалды:

1. $1$ санының бөлгіштері: $1$. Бөлгіштерінің саны $1$ - тақ.
2. $2$ санының бөлгіштері: $1, 2$. Бөлгіштерінің саны $2$ - жұп.
3. $3$ санының бөлгіштері: $1, 3$. Бөлгіштерінің саны $2$ - жұп.
4. $4$ санының бөлгіштері: $1, 2, 4$. Бөлгіштерінің саны $3$ - тақ.
5. $5$ санының бөлгіштері: $1, 5$. Бөлгіштерінің саны $2$ - жұп.
6. $6$ санының бөлгіштері: $1, 2, 3, 6$. Бөлгіштерінің саны $4$ - жұп.
7. $7$ санының бөлгіштері: $1, 7$. Бөлгіштерінің саны $2$ - жұп.
8. $8$ санының бөлгіштері: $1, 2, 4, 8$. Бөлгіштерінің саны $4$ - жұп.
9. $9$ санының бөлгіштері: $1, 3, 9$. Бөлгіштерінің саны $3$ - тақ.
10. $10$ санының бөлгіштері: $1, 2, 5, 10$. Бөлгіштерінің саны $4$ - жұп.

Задача E. Екінші максимум

Сізге $a_1$, $a_2$,..., $a_n$ $n$ саны беріледі. $2$-ден $n$-ге дейін әрбір $k$ үшін $a$ массивінің алғашқы $k$ санының ішіндегі екінші максимумды табыңыз. Бірінші жолда $n$ $(1 <= n <= 10^5)$ саны берілген. Екінші жолда $a_1$, $a_2$,..., $a_n$ $n$ бүтін саны берілген $(1 <= a_i <= 10^9)$. $2$-ден $n$-ге дейін әрбір $k$ үшін есептің жауабын шығарыңыз. Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

1. $1 <= n <= 100$. 1-3 нөмердегі тесттер.
2. $1 <= n <= 5000$. 4-6 нөмердегі тесттер.
3. $1 <= n <= 10^5$. 7-10 нөмердегі тесттер

Вход

7
1 2 3 3 7 5 6

Ответ

1 2 3 3 5 6

Мысалда:

1. $k=2$. Алғашқы $k$ сан $\underline{1}, 2$. Жауабы - $1$
2. $k=3$. Алғашқы $k$ сан $1, \underline{2}, 3$. Жауабы - $2$
3. $k=4$. Алғашқы $k$ сан $1, 2, \underline{3}, 3$. Жауабы - $3$
4. $k=5$. Алғашқы $k$ сан $1, 2, \underline{3}, 3, 7$. Жауабы - $3$
5. $k=6$. Алғашқы $k$ сан $1, 2, 3, 3, 7, \underline{5}$. Жауабы - $5$
6. $k=7$. Алғашқы $k$ сан $1, 2, 3, 3, 7, 5, \underline{6}$. Жауабы - $6$

Задача F. Үштіктер

Сізге ұзындығы $n$ болатын, бүтін сандардан тұратын $a$ массиві берілген. Массивтегі барлық сандар әртүрлі. Сізге $i \ne j$, $i \ne k$, $j \ne k$ және $a_i*a_j=a_k^2$ орындалатын $i$, $j$, $k$ үштіктер санын табу керек. Бірінші жолда $n$ $(3 <= n <= 10^5)$ бүтін саны берілген. Келесі жолда $a_1$, $a_2$, $\dots$, $a_n$ $(1 <= a_i <= 3 * 10^5)$ болатын $a$ массиві берілген. Есептің жауабын шығарыңыз. Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

1. $n <= 100$, $1 <= a_i <= 500$. 1-3 нөмердегі тесттер.
2. $n <= 5000$, $1 <= a_i <= 10000$. 4-6 нөмердегі тесттер.
3. $n <= 10^5$, $1 <= a_i <= 300000$. 7-10 нөмердегі тесттер

Вход

6
6 3 9 4 12 27

Ответ

6