Mật Lệnh từ Tháp Giấy của Thầy Quyết

Tại Học Viện Thuật Số, nơi những công thức toán học được xem như phép thuật cổ xưa, Thầy Quyết là người trông coi Tháp Giấy – một tòa tháp chứa vô số cuộn giấy phép có khả năng khuếch đại trí tuệ người học.

Trong một đêm trăng mờ, Thầy Quyết phát hiện một cuộn giấy cổ đại bị phong ấn đã lâu. Theo ghi chép, cuộn giấy này có diện tích bằng đúng một số nguyên dương ~n~, và để khai mở tri thức trong đó, người giữ tháp phải chia cuộn giấy thành những mảnh giấy hình vuông theo đúng nghi thức của Pháp Ấn Cổ.

Cuộn giấy đi kèm hai điều răn bí ẩn:

Điều Răn Thứ Nhất — Ấn Tiết Chế

Cuộn giấy phải được chia thành ít mảnh nhất có thể, vì mỗi đường cắt sẽ kích hoạt một tia chớp phép thuật, làm tiêu tốn năng lượng của Tháp Giấy.

Điều Răn Thứ Hai — Ấn Uy Danh

Trong tất cả các cách chia thỏa mãn điều răn thứ nhất, mảnh được cắt đầu tiên phải là mảnh lớn nhất có thể, vì đó là mảnh mang danh ấn mở cánh cổng tri thức.

Nhiệm Vụ Của Bạn – Người Tập Sự

Hãy xác định:

Cạnh của các mảnh vuông mà Thầy Quyết sẽ tạo ra theo nghi thức của Tháp Giấy.

Hoàn thành đúng, bạn sẽ được ghi danh vào Sổ Tập Sự Cấp Một. Làm sai… thì theo truyền thuyết, tòa tháp sẽ rung lên một tiếng bụp và bạn sẽ được giao quét hành lang tầng 7 trong một tuần.

Dữ liệu vào (Input)

• Một dòng duy nhất chứa số nguyên dương n (~1 \le n \le 10^3~) là diện tích của tờ giấy ban đầu.

Dữ liệu ra (Output)

• In ra một dòng duy nhất gồm độ dài cạnh của các mảnh giấy hình vuông tìm được.
• Các số cách nhau bởi dấu cách và phải sắp xếp theo thứ tự giảm dần (từ lớn đến bé).

Ví dụ minh họa

Ví dụ 1:

Ví dụ 2:

Sau chuỗi trận đầu mùa Premier League 2025-2026 bết bát khiến người hâm mộ phải "chui vào hang", thầy Quyết - một fan cứng của Manchester United - đã mất ngủ 7 ngày 7 đêm để tìm nguyên nhân.

Bằng kiến thức Thần số học uyên thâm, thầy nhận ra vấn đề không nằm ở huấn luyện viên, mà nằm ở "phong thủy" tuyến giữa. Thầy khẳng định: "MU đá kém là do thiếu sự kết hợp hoàn hảo giữa một số 6 (tiền vệ phòng ngự mỏ neo) và một số 8 (tiền vệ con thoi box-to-box)".

Theo lý thuyết của thầy, một đội hình "bất bại" phải được vận hành dựa trên các "Mã Gen Chiến Thắng". Một Mã Gen Chiến Thắng hợp lệ là một chuỗi ký tự chỉ bao gồm hai chữ số 6 và 8.

• Số 6 đại diện cho những pha tắc bóng dũng mãnh.
• Số 8 đại diện cho những đường chuyền kiến tạo đẳng cấp.
• Ví dụ: Mã 686 nghĩa là: Tắc bóng -> Chọc khe -> Tắc bóng.

Thầy Quyết muốn gửi bản kế hoạch này sang Anh. Tuy nhiên, tờ giấy A4 gửi đi chỉ đủ chỗ viết các Mã Gen có độ dài không quá ~N~ ký tự.

Yêu cầu: Thầy Quyết muốn liệt kê tất cả các Mã Gen Chiến Thắng có thể tạo ra (độ dài từ 1 đến ~N~) để HLV Amorim tha hồ lựa chọn. Hãy đếm xem có bao nhiêu mã như vậy?

Vì danh sách các vấn đề của MU dài như sớ Táo Quân, nên số lượng Mã Gen này cũng sẽ rất lớn. Hãy in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Dữ liệu vào (Input)

• Một dòng duy nhất chứa số nguyên dương ~N~ (~1 \le N \le 10^{18}~) – Độ dài tối đa của Mã Gen mà thầy Quyết cho phép.

Dữ liệu ra (Output)

• Một số nguyên duy nhất là số lượng Mã Gen tìm được (lấy dư theo ~10^9 + 7~).

Ví dụ minh họa

Ví dụ 1:

Ví dụ 2:

Tuấn là một học sinh yêu thích Tin học. Gần đây, Tuấn nghe nói về sức mạnh của robot thông minh ChatGPT nên đã đố ChatGPT một bài toán như sau:

Cho số nguyên dương n. Tìm số lượng các số nguyên dương X nhỏ hơn n thỏa mãn: X và n là hai số nguyên tố cùng nhau (tức là Ước chung lớn nhất của X và n bằng 1).

Thật thú vị, khi Tuấn nhập ~n = 5~, ChatGPT đưa ra kết quả là: Có 4 số, cụ thể là các số 1, 2, 3, 4.

Yêu cầu: Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của ChatGPT với các số n lớn hơn nhé!

Dữ liệu vào (Input): Nhập từ bàn phím một số nguyên dương n ~(2 \le n \le 2 \times 10^9)~.

Kết quả ra (Output): In ra màn hình một số nguyên duy nhất là số lượng các số nguyên dương X nhỏ hơn n và nguyên tố cùng nhau với n.

Giới hạn:

• Có 50% số điểm: ~2 \le n \le 2000~
• Có 40% số điểm: ~2000 < n \le 2 \times 10^6~
• Có 10% số điểm: ~2 \times 10^6 < n \le 2 \times 10^9~

Ví dụ:

Cho 2 số nguyên dương N và M, viết chương trình tính tổng M chữ số tận cùng của N.

Dữ liệu vào (Input):

• Dòng 1: chứa duy nhất số nguyên dương N
• Dòng 2: chứa duy nhất số nguyên dương M

Kết quả ra (Output):

Tổng M chữ số tận cùng của N

Giới hạn:

• Có 60% số điểm ứng với: ~1 \le N \le 10^9~ và ~1 \le M \le \text{số chữ số của } N~.
• Có 40% số điểm ứng với: ~1 \le N \le 10^{200}~ và ~1 \le M \le \text{số chữ số của } N~.

Ví dụ:

Cho một xâu ký tự chỉ gồm các chữ cái tiếng Anh và khoảng trắng.
Hãy đếm xem trong xâu có bao nhiêu chữ cái khác nhau (không phân biệt chữ hoa, chữ thường).

• Input:
  • Dòng 1: xâu ký tự S (có thể chứa khoảng trắng, độ dài ≤ 255).
• Output:
  • Một số nguyên: số lượng chữ cái khác nhau xuất hiện trong S.

Ví dụ

Input 1

Hello World

Output 1

7

Giải thích: các chữ cái khác nhau (không phân biệt hoa thường) là: h, e, l, o, w, r, d.

Input 2

AAA bbb CCC

Output 2

3

Cho dãy số nguyên gồm N phần tử. Hãy tìm tổng lớn nhất của một đoạn con liên tiếp trong dãy.

• Input:
  • Dòng 1: số nguyên N (1 ≤ N ≤ 10^5).
  • Dòng 2: N số nguyên a[i] (|a[i]| ≤ 10^4).
• Output:
  • Một số nguyên: tổng lớn nhất của một đoạn con.

Ví dụ

Input 1

5
1 -2 3 4 -1

Output 1

7

Đoạn con có tổng lớn nhất là 3 4.

Input 2

4
-5 -2 -3 -4

Output 2

-2

Cho một số nguyên dương N (có thể rất lớn, lên đến 1000 chữ số), được cho dưới dạng xâu.
Hãy tính:

1. Tổng các chữ số của N.
2. Số chữ số chẵn của N.
3. Số chữ số lẻ của N.

• Input:
  • Dòng 1: xâu ký tự biểu diễn số nguyên dương N (không có dấu +/-).
• Output:
  • Ba số nguyên cách nhau một khoảng trắng: tổng chữ số, số chữ số chẵn, số chữ số lẻ.

Ví dụ

Input

120345

Output

15 3 3

Trong một buổi thi Tin học, có N học sinh, mỗi em có một chiều cao.
Giám thị cần xếp các em đứng thành một hàng sao cho chiều cao không giảm dần từ trái sang phải.

Hãy in ra dãy chiều cao sau khi sắp xếp.

• Input:
  • Dòng 1: số nguyên N (1 ≤ N ≤ 10^5).
  • Dòng 2: N số nguyên h[i] (1 ≤ h[i] ≤ 2*10^9).
• Output:
  • Một dòng gồm N số, là dãy h[i] sau khi sắp xếp tăng dần.

Ví dụ

Input

5
150 160 155 145 160

Output

145 150 155 160 160

Cho một xâu S biểu diễn họ tên, có thể có nhiều khoảng trắng thừa (đầu, cuối, hoặc nhiều khoảng trắng giữa các từ), chữ cái có thể lẫn lộn hoa/thường.

Hãy chuẩn hóa họ tên theo quy tắc:

• Xóa khoảng trắng ở đầu và cuối xâu.
• Giữa các từ chỉ để một khoảng trắng.
• Chữ cái đầu mỗi từ viết hoa, các chữ cái còn lại viết thường.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 255).
• Output:
  • Một dòng duy nhất là xâu đã chuẩn hóa.

Ví dụ

Input

   nGuyeN   tHe   quYEt  

Output

Nguyen The Quyet

Cho dãy N số nguyên. Hãy tìm độ dài lớn nhất của một đoạn con liên tiếp có các phần tử tăng dần nghiêm ngặt.

• Input:
  • Dòng 1: số nguyên N (1 ≤ N ≤ 10^5).
  • Dòng 2: N số nguyên a[i] (|a[i]| ≤ 10^9).
• Output:
  • Một số nguyên: độ dài lớn nhất của đoạn con tăng dần.

Ví dụ

Input

7
1 2 2 3 4 1 2

Output

3

Giải thích: đoạn 2 3 4 có độ dài 3 là lớn nhất.

Một mật khẩu được coi là mạnh nếu thỏa mãn cả 4 điều kiện:

1. Độ dài từ 8 đến 20 ký tự.
2. Có ít nhất một chữ cái viết hoa.
3. Có ít nhất một chữ cái viết thường.
4. Có ít nhất một chữ số.

Cho xâu S, hãy kiểm tra xem đó có phải mật khẩu mạnh không.

• Input:
  • Dòng 1: xâu S (không có khoảng trắng, chỉ gồm chữ cái tiếng Anh và chữ số).
• Output:
  • In YES nếu S là mật khẩu mạnh, ngược lại in NO.

Ví dụ

Input 1

abcD1234

Output 1

YES

Input 2

abc123

Output 2

NO

Có N gói quà, gói thứ i có khối lượng a[i].
Một chiếc hộp có thể chứa tối đa khối lượng M.
Hãy xếp tất cả các gói quà vào ít hộp nhất, biết rằng mỗi hộp có thể chứa tối đa 2 gói quà.

Yêu cầu: In ra số lượng hộp ít nhất cần dùng.

• Input:
  • Dòng 1: N, M (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^9).
  • Dòng 2: N số nguyên a[i] (1 ≤ a[i] ≤ M).
• Output:
  • Một số nguyên: số hộp ít nhất.

Ví dụ

Input

5 10
3 5 3 9 4

Output

3

Cho một xâu S gồm nhiều từ, các từ cách nhau bởi một hoặc nhiều dấu cách.
Hãy đếm xem trong S có bao nhiêu từ khác nhau, không phân biệt chữ hoa và chữ thường.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 255).
• Output:
  • Một số nguyên: số từ khác nhau trong S.

Ví dụ

Input

Nguyen the Quyet   nguyen   The   quyet

Output

3

Cho một xâu S chỉ gồm các chữ cái tiếng Anh (hoa hoặc thường) và số nguyên dương K.
Hãy mã hóa S bằng cách dịch chuyển mỗi chữ cái sang phải K vị trí trong bảng chữ cái vòng tròn:

• Với chữ thường: a → b → … → z → a.
• Với chữ hoa: A → B → … → Z → A.

• Các ký tự không phải chữ cái (nếu có) giữ nguyên.

• Input:

  • Dòng 1: xâu S (độ dài ≤ 255).
  • Dòng 2: số nguyên K (1 ≤ K ≤ 10^9).
• Output:
  • Một dòng là xâu sau khi mã hóa.

Ví dụ

Input

AbZz
3

Output

DeCc

Giải thích:

• A → D, b → e, Z → C, z → c.

Cho một xâu S gồm các từ cách nhau bởi một hoặc nhiều dấu cách.
Hãy in ra độ dài của từ dài nhất trong S.

• Input:
  • Dòng 1: xâu S (độ dài ≤ 255).
• Output:
  • Một số nguyên: độ dài từ dài nhất.

Ví dụ

Input

Hoc lap trinh Cplusplus that thu vi

Output

9

Giải thích: từ dài nhất là Cplusplus có 9 ký tự.

Trong khi học về số học, Nam tình cờ phát hiện ra một loại số có tính chất đặc biệt.
Một số nguyên dương được gọi là số đặc biệt nếu nó có chính xác 3 ước nguyên dương.

Ví dụ:

• Số 4 có 3 ước nguyên dương là 1, 2, 4 nên là số đặc biệt.
• Số 6 có 4 ước nguyên dương là 1, 2, 3, 6 nên không phải số đặc biệt.

Yêu cầu

Cho một dãy gồm N số nguyên dương ~a_1, a_2, \dots, a_N~.
Với mỗi số ~a_i~, hãy tìm số đặc biệt nhỏ nhất ~b_i~ sao cho ~b_i ≥ a_i~.

Dữ liệu vào (Input)

• Dòng 1: một số nguyên dương ~N (1 ≤ N ≤ 10^6)~ – số lượng phần tử của dãy.
• Dòng 2: N số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~ cách nhau bởi một khoảng trắng.

Kết quả (Output)

• In ra một dòng duy nhất gồm N số nguyên ~b_1, b_2, \dots, b_N~ thỏa mãn yêu cầu, các số cách nhau bởi đúng một khoảng trắng.

Ví dụ

Input 1

3
6 3 20

Output 1

9 4 25

Input 2

5
1 10 5 100 7

Output 2

4 25 9 121 9

Cho hai số nguyên không âm A và B, mỗi số có thể có tới 1000 chữ số.
Hãy tính A + B và in kết quả.

• Input:
  • Dòng 1: xâu A.
  • Dòng 2: xâu B.
• Output:
  • Một dòng là A + B (không có số 0 thừa ở đầu).

Ví dụ

Input

12345678901234567890
9876543210

Output

12345688777777780100

Hội thi Olympic Khoa học viên tưởng là hội thi thường niên diễn ra giữa các trường Trung học cơ sở trên cả nước. Ngoài nội dung thi kiến thức học sinh giỏi, ban tổ chức còn có nội dung thi vận động dành cho các bạn học sinh. Năm nay, hội thi được tổ chức tại trường Ngôi Sao - thành phố XYZ. Ban tổ chức có một trò chơi vận động mới đó là cuộc thi xếp tháp dành cho các đội chơi.

Mỗi đội chơi được ban tổ chức cung cấp n khối hộp, và các đội phải xếp thành các tòa tháp thỏa mãn các yêu cầu sau:

• Mỗi đội nhận khối hộp đầu tiên và tạo tháp đầu tiên.
• Khi nhận được một khối hộp, các đội phải xếp luôn vào một tháp đã có hoặc tạo một tháp mới, sau đó mới được nhận khối hộp tiếp theo từ ban tổ chức.
• Các tòa tháp phải thỏa mãn điều kiện: khối hộp ở trên có thể tích không lớn hơn khối hộp ở ngay dưới nó.
• Không được chuyển khối hộp từ tòa tháp này sang tòa tháp khác.
• Mỗi đội cần phải xếp được càng ít tòa tháp càng tốt.

Nhiệm vụ của bạn là xác định số tòa tháp ít nhất có thể tạo thành.

Input

• Dòng đầu tiên chứa một số nguyên dương n là số lượng khối hộp.
• Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (ai <= 10^9) là thể tích của các khối hộp.

Output

• In ra một số nguyên duy nhất là số lượng tòa tháp ít nhất có thể tạo thành.

Ví dụ

Input

5
3 8 5 2 2

Output

2