THTA Vòng Khu vực Bắc & Trung 2025

Bố tặng Dino rất nhiều khối hình vuông cơ bản kích thước \(1 \times 1\).
Hiện Dino đang xếp được 4 cột liên tiếp, mỗi cột gồm \(a, b, c, d\) hình vuông cơ bản chồng lên nhau.

Hỏi cần xếp thêm ít nhất bao nhiêu hình vuông cơ bản nữa vào các khối đã xếp để tạo thành một hình vuông?

Yêu cầu

• Tìm số lượng tối thiểu hình vuông cơ bản cần thêm vào để tạo thành một hình vuông.

Input

• Gồm 4 dòng, mỗi dòng chứa một số nguyên dương: \(a, b, c, d\) (\(1 \leq a, b, c, d \leq 100\)).

Output

• Một số tự nhiên là số hình vuông cơ bản cần thêm.

Example

1
3
6
2

24

Trên một con đường có \(n\) lô đất, mỗi lô sẽ được xây một tòa nhà, đánh số từ \(1\) đến \(n\) từ trái sang phải.
Chính quyền muốn xây một tòa nhà chọc trời tại vị trí \(k\) với độ cao \(h\) tầng.
Các tòa nhà còn lại cần được xây với độ cao thấp nhất có thể, sao cho:

• Mỗi tòa nhà có ít nhất 1 tầng.
• Hai tòa nhà liền kề có độ chênh lệch không quá \(d\) tầng.
• Vẫn phải đảm bảo tòa nhà thứ \(k\) cao đúng \(h\) tầng.

Yêu cầu

Tính tổng số tầng tối thiểu cần xây cho cả \(n\) tòa nhà.

Input

• Gồm 4 dòng, mỗi dòng là một số nguyên dương:
  • Dòng 1: \(n\) – số tòa nhà (\(1 \leq n \leq 10^7\))
  • Dòng 2: \(k\) – vị trí tòa nhà chọc trời (\(1 \leq k \leq n\))
  • Dòng 3: \(h\) – chiều cao của tòa nhà thứ \(k\) (\(1 \leq h \leq 10^8\))
  • Dòng 4: \(d\) – chênh lệch tối đa giữa 2 nhà liền kề (\(1 \leq d < h\))

Output

• Một dòng duy nhất ghi tổng số tầng tối thiểu cần xây cho \(n\) tòa nhà.

Example

6
2
3
1

10

  █ 
█ █ █
█ █ █ █ █ █
1 2 3 4 5 6

5
3
6
2

18

Scoring

• Subtask \(1\) (\(30\) điểm): \(n \leq 100\).
• Subtask \(2\) (\(30\) điểm): \(d = 1\).
• Subtask \(3\) (\(40\) điểm): Không giới hạn gì thêm.

Hãy viết liên tiếp các số tự nhiên chia hết cho \(3\) (theo thứ tự tăng dần), và nối các số đó theo thứ tự lại thành một số mới:
\(3691215182124...\)

Hỏi: chữ số thứ \(N\) trong số ghép trên là số nào?

Input

• Một dòng duy nhất chứa một số tự nhiên \(N\) (\(1 \leq N \leq 10^{12}\))

Output

• Một số tự nhiên là chữ số thứ \(N\) trong số ghép được tạo ra.

Example

4

1

Scoring

• 60% số test ứng với 60% số điểm có \(N \leq 10^3\)
• 40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm

Cho một số tự nhiên \(N\) chỉ gồm các chữ số từ \(1\) đến \(9\).
Hãy tìm cách xóa một số chữ số trong \(N\) (có thể không xóa chữ số nào), sao cho số còn lại chia hết cho 3 và có giá trị lớn nhất có thể.

Input

• Một dòng duy nhất chứa số tự nhiên \(N\) (có số chữ số không quá \(10^4\)).
• Lưu ý: Các chữ số trong \(N\) chỉ nằm trong khoảng từ 1 đến 9, không có chữ số 0.

Output

• Một dòng ghi số lớn nhất chia hết cho 3 theo yêu cầu.
• Nếu không thể tạo được số nào chia hết cho 3 thì in ra 0.

Example

232

3

369

369

25

0

Scoring

• Subtask \(1\) (\(30\) điểm): \(N\) chỉ gồm các chữ số \(1, 2, 3\).
• Subtask \(2\) (\(30\) điểm): Độ dài của \(N\) không quá \(100\) chữ số.
• Subtask \(3\) (\(40\) điểm): Không giới hạn gì thêm.

Cho \(N\) số tự nhiên từ \(1\) đến \(N\) được đặt lần lượt trên một vòng tròn (số thứ \(N\) kề với số \(1\)).
Người ta thực hiện xóa lần lượt các số khỏi vòng tròn theo quy tắc:

• Bắt đầu từ số \(X\), xóa số đó khỏi vòng tròn
• Mỗi lượt tiếp theo, đếm \(K\) bước theo chiều kim đồng hồ (bỏ qua số đã xóa), xóa số thứ \(K\)
• Lặp lại cho đến khi vòng tròn rỗng

Giả sử với \(N=5\), bắt đầu xóa ở vị trí \(X=2\), chu kì \(K=3\) thì các bước xóa lần lượt như sau:

Yêu cầu

Tìm vị trí lượt xóa (thứ mấy) của số \(M\) trong quá trình mô phỏng xóa trên vòng tròn.

Input

• Dòng 1: Số nguyên \(N\) là số lượng số ban đầu trên vòng tròn (\(1 \leq N \leq 10^5\))
• Dòng 2: Số nguyên \(X\) là vị trí bắt đầu (\(1 \leq X \leq N\))
• Dòng 3: Số nguyên \(K\) là bước đếm (\(1 \leq K \leq N\))
• Dòng 4: Số nguyên \(M\) là số cần theo dõi (\(1 \leq M \leq N\))

Output

• Một dòng duy nhất ghi số thứ tự lượt xóa của số M
• Nếu \(M\) không bị xóa thì in ra 0

Example

4
2
2
3

3

6
3
4
4

6

Scoring

• Subtask \(1\) (\(30\) điểm): \(N, K \leq 100\)
• Subtask \(2\) (\(30\) điểm): \(N, K \leq 10\,000\)
• Subtask \(3\) (\(40\) điểm): \(N, K \leq 100\,000\)