Bài tập nâng cao 2

Cho \(N\) quả bóng với ngoại hình giống hệt nhau. Trong số đó, có \(N - 1\) quả bóng với khối lượng bằng nhau và cùng nặng hơn quả bóng còn lại. Bằng cách sử dụng cân hai đĩa, hỏi cần ít nhất bao nhiêu lần cân để chắc chắn xác định được quả bóng nhẹ nhất đó?

Input

• Một số nguyên duy nhất \(N\) (\(1 \le N \le 10^{18}\)).

Output

• In ra một số nguyên duy nhất là số lần cân ít nhất cần thiết.

Example

100

5

Trong hoạt động Hội trại kỷ niệm tháng Thanh niên, Đoàn trường tổ chức trò chơi lớn đó là "Giải mã mật thư". Bạn Nam nhận được một mật thư từ ban tổ chức với nội dung là một xâu kí tự đã được mã hóa theo quy luật. Xâu kí tự này gồm các cặp theo thứ tự kí tự chữ cái tiếng Anh viết hoa và kí tự số liên tiếp nhau, mật thư được giải mã theo quy luật dịch chuyển vòng tròn chữ cái được mô tả như hình sau:

Ví dụ: Xâu kí tự trong mật thư là R2F3M1 được giải mã theo quy luật: Kí tự R dịch chuyển thêm \(2\) vị trí được kí tự T, kí tự F dịch chuyển thêm \(3\) vị trí được kí tự I, kí tự M dịch chuyển thêm \(1\) vị trí được kí tự N. Vậy dòng văn bản R2F3M1 sau khi giải mã có kết quả là TIN.

Yêu cầu: Hãy giúp bạn Nam giải mã nội dung mật thư mà ban tổ chức đã cho.

Input

• Một xâu là nội dung mật thư có độ dài tối đa là \(10^5\) kí tự gồm các cặp theo thứ tự là một kí tự chữ cái tiếng Anh viết hoa (thuộc các kí tự từ A đến Z) và một kí tự số (thuộc các kí tự từ 0 đến 9) liên tiếp nhau.

Output

• Một xâu kí tự đã được giải mã.

Example

S1F2Y2M1E3L2I0A4K3

THANHNIEN

Sau khi tốt nghiệp mẫu giáo, Tèo đã nhận được phần thưởng là một hộp có \(n\) viên kẹo. Anh quyết định ăn một lượng kẹo bằng nhau mỗi sáng cho đến khi không còn kẹo nữa. Tuy nhiên, Hùng cũng chú ý đến chiếc hộp và quyết định lấy một ít kẹo cho mình.

Quá trình ăn kẹo như sau: ban đầu Tèo chọn một số nguyên duy nhất \(k\), giống nhau cho tất cả các ngày. Sau đó, vào mỗi buổi sáng anh ấy ăn \(k\) cái kẹo từ hộp (nếu có ít hơn \(k\) cái kẹo trong hộp, anh ấy ăn tất cả), sau đó vào mỗi buổi tối Hùng ăn \(10\%\) số kẹo còn lại trong hộp. Nếu vẫn còn kẹo trong hộp, quá trình lặp lại - ngày hôm sau Tèo ăn \(k\) kẹo một lần nữa, và Hùng ăn \(10\%\) kẹo còn lại trong một hộp. Như vậy, nếu số lượng kẹo trong hộp không chia hết cho \(10\), Hùng làm tròn số lượng ta lấy từ hộp xuống.

Ví dụ, nếu có \(97\) kẹo trong hộp, Hùng sẽ chỉ ăn \(9\) cái kẹo trong hộp. Đặc biệt, nếu có ít hơn \(10\) cái kẹo trong hộp, Hùng sẽ không ăn chút nào.

Yêu cầu: Tìm ra số lượng tối thiểu \(k\) mà Tèo có thể chọn để anh ta ăn ít nhất một nửa trong \(n\) cái kẹo anh ban đầu có. Lưu ý rằng số \(k\) phải là số nguyên.

Input

• Một dòng chứa số nguyên duy nhất \(n\) (\(1 \le n \le 10^{18}\)) - số lượng kẹo ban đầu trong hộp.

Output

• Một số nguyên duy nhất - số lượng tối thiểu \(k\) điều đó sẽ cho phép Tèo ăn ít nhất một nửa số kẹo mà anh ta có.

Scoring

• Có \(70\%\) số test ứng với \(n \le 10^6\).
• Có \(30\%\) số test ứng với \(n \le 10^{18}\).

Example

68

3

Công ty vận chuyển công nghệ cao \(ABC\) có \(m\) thiết bị vận chuyển tự động được đánh số thứ tự từ \(1\) đến \(m\), thiết bị thứ \(i\) có khả năng vận chuyển hàng hoá có khối lượng tối đa \(a_i\) kilogam. Trong một phiên làm việc có \(n\) hàng hoá được đánh số thứ tự từ \(1\) đến \(n\) cần vận chuyển, hàng hoá thứ \(i\) có khối lượng là \(b_i\) kilogam. Các hàng hoá này được vận chuyển lần lượt từ hàng hoá thứ nhất đến hàng hoá thứ \(n\) sao cho ở mỗi lượt vận chuyển một hàng hoá sẽ được vận chuyển bởi một trong số các thiết bị vận chuyển. Chi phí vận chuyển phụ thuộc vào việc chọn thiết bị để vận chuyển, thiết bị có khả năng vận chuyển càng lớn thì chi phí vận chuyển càng cao. Do đó để tối ưu chi phí, ở mỗi lượt vận chuyển người ta sẽ chọn thiết bị có khả năng vận chuyển vừa lớn hơn hoặc bằng khối lượng của hàng hoá cần vận chuyển để vận chuyển hàng hoá này. Một thiết bị vận chuyển có thể được chọn ở nhiều lượt vận chuyển.

Yêu cầu: Hãy lập trình xác định cách chọn các thiết bị vận chuyển để tối ưu chi phí.

Input

• Dòng thứ nhất ghi hai số nguyên dương \(m\) và \(n\).
• Dòng thứ hai ghi \(m\) số nguyên dương từ \(a_1\) đến \(a_m\), các số đôi một khác nhau, có giá trị không vượt quá \(10^9\) và được sắp xếp theo thứ tự tăng dần.
• Dòng thứ ba ghi \(n\) số nguyên dương \(b_1\) đến \(b_n\), các số có giá trị không vượt quá \(a_m\).

Output

• In ra \(n\) số, số thứ \(i\) cho biết thứ tự của thiết bị được chọn để vận chuyển hàng hoá thứ \(i\) tương ứng.

Scoring

• \(80\%\) số điểm có \(m, n \leq 10^2\).
• \(20\%\) số điểm có \(m, n \leq 10^5\).

Example

5 6
1 4 5 7 9
8 6 1 5 4 2

5 4 1 3 2 2

Một công ty xây dựng có \(N\) thanh sắt có độ dài là \(A_1, A_2, A_3, \dots, A_N\). Vì nhu cầu công việc, công ty yêu cầu công nhân làm cho \(N\) thanh sắt này có cùng một độ dài \(k\). Muốn làm được việc này thì với thanh sắt có độ dài \(A_i > k\), công nhân cần cắt đi một đoạn \(A_i - k\), với thanh sắt có độ dài \(A_i < k\), công nhân phải hàn nối thêm một đoạn \(k - A_i\). Tổng độ dài các đoạn cắt đi và nối thêm sẽ là: Tổng độ dài các đoạn sắt cắt đi hoặc nối thêm ở \(N\) thanh sắt.

Yêu cầu: Do công ty chưa quyết định về độ dài \(k\) cuối cùng nên công ty nhờ bạn viết một chương trình giúp công ty tính: Với \(M\) sự lựa chọn các giá trị \(k\) là: \(k_1, k_2, k_3, \dots, k_M\). Hãy tính Tổng độ dài các đoạn cắt đi và nối thêm cho từng giá trị \(k\).

Input

• Dòng đầu tiên ghi 2 số nguyên dương \(N\) và \(M\) (\(1 \le N, M \le 10^5\)).
• Dòng thứ 2: Ghi \(N\) số nguyên dương \(A_1, A_2, A_3, \dots, A_N\) (\(1 \le A_i \le 10^9, i = 1 \dots N\)).
• Dòng thứ 3: Ghi \(M\) số nguyên dương \(k_1, k_2, k_3, \dots, k_M\) (\(1 \le k_j \le 10^9, j = 1 \dots M\)).

Output

• Ghi ra Tổng độ dài các đoạn cắt đi và nối thêm tương ứng với từng sự lựa chọn \(k_1, k_2, k_3, \dots, k_M\), kết quả ghi trên một dòng cách nhau một dấu cách.

Scoring

• Có \(50\%\) số điểm ứng với các test có \(N, M \le 10^3; 1 \le A_i \le 10^9; 1 \le k_j \le 10^9\).
• Có \(50\%\) số điểm ứng với các test có \(N, M \le 10^5; 1 \le A_i \le 10^9; 1 \le k_j \le 10^9\).

Examples

4 3
1 3 4 2
1 2 5

6 4 10

4 1
2 2 2 2
2

0