2025 · Tuyển sinh 10 · Quảng Trị

Một hệ thống khai thác nước ngầm tự động giám sát mực nước hiện tại trong bồn chứa.

Nếu mực nước hiện tại ~X~ ~cm^2~ chưa đạt đến mức yêu cầu tối thiểu ~Y~ ~cm^2~ hệ thống sẽ kích hoạt máy bơm hoạt động. Mỗi lần máy bơm hoạt động, mực nước sẽ tăng lên một lượng cố định ~K~ ~cm^2~. Máy bơm sẽ tự động ngắt.

Yêu cầu: Hãy tính số lần bơm tối thiểu để đạt hoặc vượt mức nước yêu cầu.

Input

Vào từ file văn bản CAU1.INP gồm:

Dòng đầu tiên chứa hai số nguyên dương ~X~ và ~Y~ cách nhau dấu cách, lần lượt là mực nước hiện tại và mức nước yêu cầu ~(1 \leq X \leq Y \leq 10^{12})~.

Dòng thứ hai chứa một số nguyên dương ~K~ là lượng nước tăng thêm sau mỗi lần bơm ~(1 \leq K \leq 10^4)~.

Output

Ghi ra file văn bản CAU1.OUT gồm một dòng ghi một số nguyên là số lần bơm tối thiểu tìm được.

Scoring

• Subtask ~1~ ~(60\%)~: số tests tương ứng với ~60\%~ số điểm của bài có ~X, Y \leq 10^8, K \leq 10^5~.

• Subtask ~2~ ~(40\%)~: số tests còn lại tương ứng với ~40\%~ số điểm của bài không có ràng buộc gì thêm.

Example input 1

20 35
5

Example output 1

3

Note 1

• Lần bơm thứ nhất: ~20+5=25~
• Lần bơm thứ hai: ~25+5=30~
• Lần bơm thứ ba: ~30+5=35~

Sau ba lần bơm bồn chứa từ ~20~ ~cm^2~ đạt mức tối thiểu ~35~ ~cm^2~.

Cho hai số nguyên dương ~a~, ~b~.

Yêu cầu: Hãy tìm số lượng các số nguyên dương ~c~ sao cho ba số ~a~, ~b~, ~c~ là độ dài ba cạnh của một tam giác.

Input

Vào từ file văn bản CAU2.INP gồm một dòng chứa hai số nguyên ~a~, ~b~ cách nhau dấu cách ~(1 \leq a,b \leq 10^9)~.

Output

Ghi ra file văn bản CAU2.OUT gồm một dòng ghi một số là số lượng số ~c~ tìm được.

Scoring

• Subtask ~1~ ~(70\%)~ tương ứng với ~70\%~ số điểm của bài có ~a~, ~b~ ~\leq 10^5~.

• Subtask ~2~ ~(30\%)~ còn lại tương ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Example input 1

2 2

Example output 1

3

Tý có ~A~ cái kẹo chanh, ~B~ cái kẹo dừa và muốn chia tất cả cho vài người bạn. Tý nhận thấy: nếu mỗi bạn nhận được số kẹo bằng nhau với mỗi loại thì sẽ có bao nhiêu cách để chia.

Ví dụ: Với ~A=4,B=12~, có ba cách chia:

1. Nếu chia cho một bạn thì bạn đó sẽ nhận ~4~ cái kẹo chanh và ~12~ cái kẹo dừa;

2. Nếu chia cho hai bạn thì mỗi bạn sẽ nhận ~2~ cái kẹo chanh và ~6~ cái kẹo dừa;

3. Và nếu chia cho bốn bạn thì mỗi bạn sẽ nhận ~1~ cái kẹo chanh và ~3~ cái kẹo dừa.

Yêu cầu: Hãy giúp Tý tìm và ghi ra tất cả các cách có thể chia hết số kẹo cho các bạn sao cho mỗi bạn luôn được số kẹo bằng nhau mỗi loại. Giả sử Tý có vô số bạn bè để chia kẹo.

Input

Vào từ file văn bản CAU3.INP gồm một dòng chứa hai số nguyên ~A,B~ cách nhau dấu cách ~(1 \leq A,B \leq 10^{17})~.

Output

Ghi ra file văn bản CAU3.OUT tương ứng với mỗi cách chia ghi ra ba số nguyên ~n,x,y~ cách nhau dấu cách. Số ~n~ là số bạn mà Tý có thể chia kẹo. Số ~x~ và ~y~ là số kẹo chanh và kẹo dừa mà mỗi bạn nhận được trong cách chia đó. Mỗi cách ghi ra đúng một lần và theo thứ tự tăng của ~n~.

Scoring

• Subtask ~1~ ~(30\%)~ tương ứng với ~30\%~ số điểm của bài có ~A,B \leq 10^7~.

• Subtask ~2~ ~(30\%)~ khác tương ứng với ~30\%~ số điểm của bài có ~A,B \leq 10^{12}~.

• Subtask ~3~ ~(40\%)~ còn lại tương ứng với ~40\%~ số điểm của bài không có ràng buộc gì thêm.

Example input 1

4 12

Example output 1

1 4 12
2 2 6
4 1 3

Một khu vui chơi gần bờ biển trải dài và hẹp, được chia thành ~n~ khu vực, đánh số từ ~1~ đến ~n~ và các khu vực được xem như nằm trên cùng một đường thẳng.

Để giám sát an ninh và các hoạt động trong các khu vui chơi, Ban quản lý đã lắp đặt các camera tại một số khu vực. Họ đã lắp ~q~ cameras tại các khu vực ~c_1,c_2,...,c_q~. Một khu vực có thể lắp đặt một hoặc nhiều camera hoặc không. Nếu có camera lắp đặt tại khu vực ~i~ thì camera đó sẽ giám sát các khu vực ~i-r,...,i-1,i,i+1,...,i+r~; tức là ngoài khu vực ~i~ thì camera có thể giám sát ~r~ khu vực bên trái và ~r~ khu vực bên phải của nó (nếu có ít hơn r khu vực bên trái hoặc bên phải của ~i~ thì camera sẽ chỉ giám sát các khu vực có trong phạm vi đó).

Yêu cầu: Hãy giúp Ban quản lý xác định xem tại mỗi khu vực trong khu vui chơi được giám sát bởi bao nhiêu cameras?

Input

Vào từ file văn bản CAU4.INP gồm:

• Dòng đầu tiên chứa số nguyên ~n(1 \leq n \leq 10 ^ 5)~;

• Dòng thứ hai chứa hai số nguyên ~q, r(1 \leq q \leq 10 ^ 5, 0 \leq r < n)~;

• Dòng thứ ba chứa q số nguyên ~c_1 ,c_2 ,...,c_q (1 \leq c_{i} \leq n, i = 1, 2 ,...,q)~.

Output

Ghi ra file văn bản CAU4.OUT gồm một dòng ghi ~n~ số nguyên cách nhau dấu cách, số thứ ~i~ là số lượng cameras giám sát khu vực ~i~.

Scoring

• Subtask ~1~ ~(20\%)~ số tests tương ứng với ~20\%~ số điểm của bài có ~r=0~;

• Subtask ~2~ ~(40\%)~ số tests khác tương ứng với ~40\%~ số điểm của bài có ~n,q \leq 7000~;

• Subtask ~3~ ~(20\%)~ số tests khác tương ứng với ~20\%~ số điểm của bài có ~n \leq 7000~;

• Subtask ~4~ ~(20\%)~ số tests còn lại tương ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Example input 1

8
5 2
5 3 7 1 3

Example output 1

3 3 4 3 4 2 2 1

Example input 2

5
4 0 
1 2 1 3

Example output 2

2 1 1 0 0

Note 1

• Có ~8~ khu vực trong khu vui chơi, có ~5~ cameras và bán kính giám sát của chúng là ~2~. Camera thứ nhất tại khu vực ~5~ sẽ giám sát các khu vực ~3, 4, 5, 6, 7~. Camera thứ hai tại khu vực ~3~ sẽ giám sát các khu vực ~1, 2, 3, 4, 5~. Camera thứ ba tại khu vực ~7~ sẽ giám sát các khu vực ~5, 6, 7, 8~. Camera thứ tư tại khu vực ~1~ sẽ giám sát các khu vực ~1, 2, 3~. Camera cuối cùng tại khu vực ~3~ sẽ giám sát các khu vực ~1, 2, 3, 4, 5~.

Note 2

• Bán kính giám sát của các cameras bằng ~0~ nên camera được lắp đặt tại khu vực nào chỉ giám sát khu vực đó.