CP250802
Yêu cầu:
Bội riêng của bộ gồm 3 số nguyên dương ~(x, y, z)~ được định nghĩa như sau: Số nguyên dương ~t~ là bội riêng của bộ số ~(x, y, z)~ khi ~t~ chỉ chia hết cho đúng một số trong bộ ~(x, y, z)~.
Cho ~5~ số nguyên dương ~a, b, x, y, z~ Đếm số lượng bội riêng của ~(x, y, z)~ trong đoạn từ ~a~ đến ~b~.
Dữ liệu:
Dòng duy nhất ghi ~5~ số nguyên a, b, x, y, z (~0 < a < b ≤ 10^{18}, 0 < x, y, z ≤ 10^{18}~).
Kết quả:
Một số nguyên duy nhất là kết quả của bài toán.
Input 1:
10 20 2 3 5
Output 1:
2
Input 2:
10 20 2 11 5
Output 2:
6
Input 3:
10 100 2 8 16
Output 3:
35
Input 4:
10 100 2 3 5
Output 4:
42
Giới hạn
-25% số điểm có ~1 ≤ a, b, x, y, z ≤ 10^5~.
-25% số điểm có ~10^5 ≤ a, b, x, y, z ≤ 10^9~.
-50% số điểm có ~10^9 \leq a,b,x,y,z \leq 10^{18}~.
Yêu cầu:
Xâu Palindrome (hay còn gọi là xâu đối xứng) là một chuỗi ký tự có tính chất: đọc từ trái sang phải và từ phải sang trái đều giống nhau. Xâu có 1 ký tự cũng được xem là xâu Palindrome. Xâu con của xâu S là một dãy các ký tự liên tiếp trong xâu S.
Phép chia Palind trên xâu S là một cách chia xâu S thành các xâu con liên tiếp. Trong đó, từng xâu con trong cách chia đó đều là xâu Palindrome.
Cho xâu S, hãy xác định số cách chia Palind có thể thực hiện trên xâu S.
Dữ liệu:
Dòng duy nhất ghi xâu S (không rỗng) chỉ gồm các ký tự chữ cái thường ~'a'..'z'~. Số lượng ký tự của S không quá ~16~ ký tự.
Kết quả:
Một dòng duy nhất ghi số lượng phép chia Palind có thể thực hiện trên xâu S.
Input 1:
aab
Output 1:
2
Input 2:
a
Output 2:
1
Input 3:
banana
Output 3:
5
Giải thích:
Ví dụ 1: S= ~aab~ có thể thực hiện được 2 phép chia Palind như sau: [aa][b] và [a][a][b]
Giới hạn
- 30% số điểm có độ dài xâu không vượt quá ~10~ ký tự.
- 60% số điểm không ràng buộc gì thêm.
Yêu cầu:
Tèo là một cậu bé rất khỏe nhưng cũng cực kỳ lười biếng. Hôm nay, Tèo được phú ông giao cho nhiệm vụ vào rừng đốn củi. Phú ông đưa cho Tèo một danh sách gồm n cây của phú ông muốn đốn. Mỗi cây khi đốn sẽ mang lại cho Tèo ai bó củi. Những cây nào không đốn thì không được bó củi nào. Nếu Tèo đốn được ít nhất một nửa tổng số bó củi theo yêu cầu trong buổi sáng, thì sẽ được phú ông thưởng cho một bữa cơm trưa no nê. Ví dụ, nếu có ~3~ cây trong danh sách, tương ứng cho ~1~, ~3~ và ~4~ bó củi, thì tổng số là ~8~ bó, và chỉ cần đốn đủ ~4~ bó là đủ điều kiện để được thưởng. Tèo rất khỏe mạnh, có thể đốn bất kỳ cây nào mà không gặp khó khăn. Nhưng cậu lại rất lười, nên muốn đốn ít cây nhất có thể để vẫn được bữa cơm trưa ngon lành.
Tèo chỉ muốn đốn liền mạch một đoạn cây nào đó trong danh sách. Tức là Tèo chọn một cây số hiệu ~k~, rồi lần lượt đốn các cây số ~k, k+1, k+2,… ,~ cho đến khi vừa đủ số bó củi tối thiểu theo yêu cầu. Tuy nhiên, để giảm bớt công sức, Tèo có thể chọn bỏ qua nhiều nhất một cây trong đoạn đó, nếu việc bỏ cây đó giúp giảm số lượng cây phải đốn mà vẫn đảm bảo đủ chỉ tiêu.
Hãy xác định số lượng cây ít nhất mà Tèo cần đốn (theo chiến lược lười biếng của mình) để được phần thưởng từ phú ông.
Dữ liệu:
- Dòng thứ nhất là số nguyên ~n (1 ≤ 𝑛 ≤ 10^5)~
- Dòng tiếp theo ghi các số nguyên ~a_i~ là số bó củi khi đốn được cây thứ ~i (1≤a_i≤10^9 )~
Kết quả:
- Một dòng ghi số cây ít nhất mà Tèo cần phải đốn để đạt chỉ tiêu của Phú ông.
Input 1:
5
1 1 2 1 2
Output 1:
2
Input 2:
3
2 3 1
Output 2:
1
Giải thích
Ví dụ 1: Tèo có thể chọn đoạn gồm các cây [2 1 2] để đốn và có thể bỏ qua cây [1] mà vẫn có thể đảm bảo số lượng bó củi tối thiểu theo yêu cầu của phú ông.
Ví dụ 2: Tèo chọn đốn đúng một cây [3] để đạt chỉ tiêu của phú ông.
Giới hạn
- Có 30% số test ứng với 30% số điểm của bài có ~𝑛 ≤ 100~.
- Có 30% số test ứng với 30% số điểm của bài có ~100 < 𝑛 ≤ 10^3~.
- Có 40% số test ứng với 40% số điểm của bài có ~10^3 < 𝑛 ≤ 10^5~.