Young ICT 2024 - Phòng thi thử - Bảng B

Mẹ nhờ em đong dầu.

Coi như số lượng dầu mẹ em đang có là vô hạn. Em cần đong \(n\) lít dầu vào can dầu lớn, tuy nhiên trong nhà chỉ có 2 loại can là loại can \(2\) lít và can \(3\) lít. Vì nhà giàu nên em muốn bao nhiêu can thuộc 2 loại trên đều có đủ. Em có thể thực hiện các thao tác sau:

• Múc đầy một can \(2\ell\) hoặc \(3\ell\) để đưa thêm dầu từ nguồn vào can lớn
• Múc đầy một can \(2\ell\) hoặc \(3\ell\) để rút bớt dầu từ can lớn về lại nguồn.

Người ta bảo "người lười thường rất thông minh". Em hãy tính xem số thao tác tối thiểu cần phải dùng để đong được đúng \(n\) lít dầu vào can lớn

Input

• Một dòng duy nhất chứa một số nguyên dương \(n\) \((n \le 10^9)\)

Output

• Số lượng can ít nhất em cần dùng để đong được \(n\) lít dầu.

Subtask

• Subtask \(1\) (\(60\%\) số điểm): \(n \le 10^3\)
• Subtask \(2\) (\(40\%\) số điểm): Không có giới hạn gì thêm.

Sample

5

2

Cho hai số \(a, b\). Ta cần biến đổi để một trong hai số \(a\) hoặc \(b\) về \(0\).

Ở mỗi phép biến đổi, ta thực hiện như sau:

• Nếu \(a \ge b\), ta đặt lại \(a\) bằng \(a-b\)
• Ngược lại, ta đặt lại \(b\) bằng \(b-a\).

Đếm số lượng phép biến đổi cần phải thực hiện.

Input

• Một dòng duy nhất chứa hai số \(a, b\) (\(a, b \le 10^{18}\)).

Output

• Một dòng duy nhất chứa số lượng phép biến đổi cần thực hiện.

Subtask

• Subtask \(1\) (\(40\%\) số điểm): \(a, b \le 10^6\)
• Subtask \(2\) (\(20\%\) số điểm): \(a\) chia hết cho \(b\)
• Subtask \(3\) (\(40\%\) số điểm): \(a, b \le 10^{18}\)

Sample

12 18

3

Pandora là một hành tinh xanh xinh đẹp, là nơi cư ngụ của chủng tộc người Navi. Một ngày đẹp trời, bọn người Trời đến từ trái đất xa xôi quyết định đem các khí tài quân sự hiện đại nhằm xâm lược hành tinh này.

Có \(n\) robot, robot thứ \(i\) có lượng máu là \(a[i]\), có \(m\) dũng sĩ Navi, dũng sĩ Navi thứ \(j\) có sức tấn công là \(b[j]\). Người Navi rất tôn sùng tín ngưỡng của mình, họ yêu chuộng hòa bình nên mỗi dũng sĩ Navi chỉ có thể tấn công một robot duy nhất. Dũng sĩ Navi thứ \(j\) được coi là tiêu diệt được robot thứ \(i\) nếu như \(b[j] \ge a[i]\).

Hãy tính xem các dũng sĩ Navi có thể tiêu diệt được nhiều nhất bao nhiêu robot?

Input

• Dòng đầu tiên ghi 2 số nguyên \(n\) và \(m\) \((1 \le n,m \le 10^6)\)
• Dòng thứ hai ghi \(n\) số, với số \(a[i]\) là lượng máu của robot thứ \(i\) \((1 \le i \le n\) và \(1 \le a[i] \le 10^9)\)
• Dòng thứ ba ghi \(m\) số, với số \(b[j]\) là sức tấn công của người Navi thứ \(j\) \((1 \le j \le m\) và \(1 \le b[j] \le 10^9)\)

Output

Số lượng Robot nhiều nhất mà các chiến binh Navi có thể tiêu diệt được (Lưu ý: mỗi chiến binh Navi chỉ tấn công một robot duy nhất)

Subtask

• Subtask \(1\) (\(10\%\) số điểm): \(a[i] = b[j] = 1\ (1 \le i \le n, 1 \le j \le m)\)
• Subtask \(2\) (\(30\%\) số điểm): \(b[1] = b[2] = \dots = b[n]\)
• Subtask \(3\) (\(60\%\) số điểm): Không có ràng buộc gì thêm

Sample

3 2
1 2 3
1 1

1

Cho dãy số \(A\) gồm \(N\) phần tử, và một số \(K\).
Ta có thể chọn một dãy con sao cho vị trí các phần tử được chọn cách nhau tối thiểu \(K\) đơn vị.

Tìm tổng lớn nhất có thể đạt được.

Input

• Dòng 1 gồm 2 số \(N\) và \(K\) \((N, K \le 10^5)\)
• Dòng 2 gồm \(N\) số là giá trị các số trong dãy \(A\) \((A[i] \le 10^5)\).

Output

• Một số duy nhất là kết quả của bài toán

Subtask

• Subtask \(1\) (\(25\%\) số điểm): \(n, k \le 20\)
• Subtask \(2\) (\(5\%\) số điểm): \(n = k\)
• Subtask \(3\) (\(15\%\) số điểm): Các phần tử có giá trị bằng nhau
• Subtask \(4\) (\(30\%\) số điểm): \(n, k \le 10^3\)
• Subtask \(5\) (\(25\%\) số điểm): \(n, k \le 10^5\)

Sample

5 3
2 4 3 5 1

7

Nhập vào một số \(n\).

In ra \(n\) dòng, dòng thứ \(i\) in ra \(i * i\) ký tự * liên tiếp nhau.

Input

• Một dòng duy nhất chứa một số \(n\) (\(n \le 100\)).

Output

• In ra \(n\) dòng theo yêu cầu đề bài

Sample

3

*
****
*********

Thiên nhiên trân quý ban tặng cho chúng ta mạng sống, chúng ta có quyền được sống và quyền tự do làm những điều mình thích. Nhưng gần đây người của hành tinh Sao Hỏa đang tiến về Trái Đất để đánh cắp lõi Trái Đất, rất may Irene đã phát hiện và chuẩn bị kế hoạch phục kích.

Địa hình lúc đó có \(N\) hành tinh không tính Trái Đất, hành tinh thứ \(i\) cách Trái Đất \(x_i\) km về bên trái. Tương ứng với mỗi hành tinh đều có một thiết bị bắn tỉa. Thiết bị bắn tỉa ở hành tinh \(A\) có thể bắn đến hành tinh \(B\) khi và chỉ khi \(x_A \ge x_B\).

Người Sao Hỏa rất thông minh bọn chúng cùng với phi thuyền đang trốn ở một hành tinh trong \(N\) hành tinh để không bị phát hiện. Vì hòa bình và sự sống của Trái Đất, Irene quyết tâm tìm và phá hủy phi thuyền của người Sao Hỏa dù có hy sinh mạng sống của mình.

Biết rằng phi thuyền chỉ có thể phá hủy bằng thiết bị bắn tỉa nhưng Irene không biết mình nên phục kích ở hành tinh nào. Là một lập trình viên, vệ tinh có thể cung cấp khoảng cách của \(N\) hành tinh so với Trái Đất hãy giúp Irene tìm ra nơi phục kích lí tưởng nhất.

Input

• Dòng đầu tiên: Chứa duy nhất một số nguyên dương \(N\) là số lượng hành tinh \((1 \le N \le 10^6)\).

• Dòng tiếp theo: Chứa \(N\) số nguyên dương \(x_i\) là khoảng cách của hành tinh thứ i so với Trái Đất \((1 \le x_i \le 10^9)\).

• Dữ liệu đảm bảo không có hai hành tinh nào đồng thời bắn được nhau.

Output

• Gồm \(1\) số nguyên là khoảng cách của hành tinh được cho là nơi phục kích lí tưởng nhất so với Trái Đất.

Example

5
234 1 4 3 75

234

Ngọc Anh vừa tốt nghiệp một khóa học kiến trúc và ngay lập tức, cô ấy được giao một công việc thiết kế một ngôi nhà. Ngôi nhà đã hoàn thiện, nhưng vốn là một người yêu Toán học nên Ngọc Anh đã cố tình thiết kế cầu thang với các bậc thang có chênh lệch độ cao giữa hai bậc thang khác nhau.

Biết cầu thang có tổng cộng \(n\) bậc thang, bậc thang thứ \(i\) có cao hơn bậc thang thứ \(i-1\) một khoảng \(a_{i}\) đơn vị độ dài. Ngọc Anh đặt ra một câu hỏi: Giả sử bước chân của một người chỉ có thể leo lên bậc thang kế tiếp nếu chênh lệch giữa bậc thang kế tiếp và bậc thang hiện tại không quá \(t\), hỏi người đó có thể leo được tối đa bao nhiêu bậc thang?

Để tính cho cả nhà gia chủ, Ngọc Anh sẽ cần tính bậc thang tối đa có thể leo cho từng người một. Việc này khá tốn thời gian, nên Ngọc Anh đã nhờ Hải "dớ" xử lí hộ Ngọc Anh vấn đề này để Ngọc Anh có thể đi thiết kế những ngôi nhà khác.

Yêu cầu: Với mỗi người, xác định số bậc thang tối đa họ có thể leo?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n,m \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2},..., a_{n}\) (\(a_{i} \le 10^9\)).
• Dòng thứ ba chứa \(m\) số nguyên \(t\) (\(t \le 10^9\)).

Output

• Với mỗi người, in ra trên một dòng là số bậc thang tối đa họ có thể leo.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_{1} \le a_{2} \le a_{3} \le ... \le a_{n}\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

5 2
1 2 2 4 5
2 4

3
4

Cho mảng \(A\) gồm \(N\) số nguyên dương.

Yêu cầu: Hãy in ra tổng tất cả các cặp \((A_i \times A_j)\) với mọi cặp \((i,j)\) thỏa mãn \(1\le i<j\le N\) , chia lấy dư cho \(({10}^9+7)\). Hay nói cách khác: tổng tất cả các cặp tích của mảng.

Input

• Dòng đầu tiên nhập số nguyên dương \(N\) \((2\le N\le2\times{10}^5)\).
• Dòng còn lại nhập \(N\) số tiếp theo – là các phần tử của mảng \((1\le A_i\le{10}^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài sau khi chia lấy dư cho \(({10}^9+7)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N\le{10}^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 2 3

11

Cho hai mảng \(A\) và \(B\) cùng có \(N\) phần tử , mảng \(A\) gồm \(a_1,a_2,a_3,\ldots,a_N\) và mảng \(B\) gồm \(b_1,b_2,b_3,\ldots,b_N\).

Yêu cầu: Hãy tính \(\left(a_1^{b_1}+a_2^{b_2}+a_3^{b_3}+\ldots+a_N^{b_N}\right)\ mod\ {10}^9\).

Input

• Dòng một là số nguyên dương \(N\) duy nhất \((1 \le N\le{10}^5)\).
• Dòng thứ hai là \(N\) phần tử của mảng \(A\), mỗi số cách nhau một khoảng trắng \((1 \le {a}_i\le{10}^5)\).
• Dòng thứ ba là \(N\) phần tử của mảng \(B\), mỗi số cách nhau một khoảng trắng \((1 \le {b}_i\le{10}^5)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(25\%\) số điểm) : Có \(N = 1\) và \(a_i,b_i \le 8\).
• Subtask \(2\) (\(25\%\) số điểm) : Có \(b_i \le 100\).
• Subtask \(3\) (\(25\%\) số điểm) : Có \(a_1=a_2=...=a_N\).
• Subtask \(4\) (\(25\%\) số điểm) : Không có ràng buộc gì thêm.

Example

3
1 2 3
4 5 6

762

Sau kì thi tin học trẻ, shiba đã đặt mua \(N\) gói kẹo nhằm tự thưởng cho mình, và cũng để chia sẻ với _minhduc. Số kẹo lần lượt trong mỗi gói là \(a_1,a_2,a_3,\ldots,a_n\). shiba muốn chia các gói kẹo này thành hai phần, một phần đưa cho _minhduc, một phần để mình ăn. Để cho _minhduc khỏi ganh tị, shiba muốn tìm cách chia mà chênh lệch tổng số kẹo của hai người là nhỏ nhất. Vì các gói kẹo có hương vị khác nhau, shiba không muốn bóc các gói kẹo để tránh chúng bị trộn lẫn..

Yêu cầu: Hãy giúp shiba tìm cách chia các gói kẹo sao cho chênh lệch tổng số kẹo của hai người là nhỏ nhất có thể.

Input

• Dòng đầu tiên nhập số nguyên dương \(N\) – số gói kẹo \((2\le N\le{10}^4)\).
• Dòng thứ hai nhập \(N\) phần tử - số kẹo mỗi gói \((0 \le {a}_i\le{10}^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): Có \(N \le 20\).
• Subtask \(2\) (\(25\%\) số điểm): Có \(N \le 1000\), tổng số kẹo trong tất cả các gói không vượt quá \(3 \times {10}^4\).
• Subtask \(3\) (\(25\%\) số điểm): Có \(N \le 40\).
• Subtask \(4\) (\(25\%\) số điểm): Có \(N \le 10^4\), tổng số kẹo trong tất cả các gói không vượt quá \(12 \times {10}^5\).

Example

5
19 17 13 9 7

1