Đề bài: Tạo hình vuông từ các cột hình vuông cơ bản

Bối cảnh

Bố tặng Dino rất nhiều khối hình vuông cơ bản kích thước 1 × 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.

Dữ liệu nhập vào từ bàn phím

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

Kết quả ghi ra màn hình

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

Ví dụ

XÂY NHÀ

Time Limit: 1.0s
Memory Limit: 1G

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à.

Dữ liệu nhập vào từ bàn phím

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 ≤ n ≤ 10⁷)
• Dòng 2: k – vị trí tòa nhà chọc trời (1 ≤ k ≤ n)
• Dòng 3: h – chiều cao của tòa nhà thứ k (1 ≤ h ≤ 10⁸)
• Dòng 4: d – chênh lệch tối đa giữa 2 nhà liền kề (1 ≤ d < h)

Kết quả ghi ra màn hình

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à.

Ví dụ

Hình minh họa ví dụ 1

TÌM CHỮ SỐ

Time Limit: 1.0s
Memory Limit: 1G

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?

Dữ liệu nhập vào từ bàn phím

• Một dòng duy nhất chứa một số tự nhiên N (1 ≤ N ≤ 10¹²)

Kết quả ghi ra màn hình

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

Ví dụ

Ràng buộc

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

CHIA HẾT CHO 3

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ể

Yêu cầu

Đưa ra số lớn nhất có thể tạo thành từ N mà chia hết cho 3 bằng cách xóa một số chữ số (hoặc không xóa chữ số nào).

Dữ liệu nhập vào từ bàn phím

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

Kết quả ghi ra màn hình

• 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.

Ví dụ

Ràng buộc

• 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

XÓA SỐ

Mô tả

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:

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

Ví dụ với N = 5, X = 2, chu kỳ K = 3:

• Lượt 1: Xóa 2 → còn [1,3,4,5]
• Lượt 2: Từ ngay sau 2 (là 3) đếm 3 bước → xóa 5 → còn [1,3,4]
• Lượt 3: Từ sau 5 (quay vòng) đếm 3 bước → xóa 4 → còn [1,3]
• Lượt 4: Từ sau 4 đếm 3 bước → xóa 1 → còn [3]
• Lượt 5: Xóa 3

Yêu cầu

Tìm vị trí lượt xóa (lần thứ mấy) của số M trong quá trình mô phỏng. Nếu M không bị xóa thì in ra 0.

Input

Gồm 4 dòng:

• Dòng 1: Số nguyên N là số lượng số ban đầu trên vòng tròn (1 ≤ N ≤ 10^5).
• Dòng 2: Số nguyên X là vị trí bắt đầu xóa (1 ≤ X ≤ N).
• Dòng 3: Số nguyên K là bước đếm mỗi lượt (1 ≤ K ≤ N).
• Dòng 4: Số nguyên M là số cần theo dõi (1 ≤ M ≤ 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 0.

Ví dụ

Ràng buộc

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