9766. Hoán Vị Kế Tiếp | Lập Trình C/C++

Menu Bỏ qua nội dung

• Cơ bản
• Quy luật toán học
• Quay lui
• Quy hoạch động
• Đệ quy
• Ôtômat
• Cấu trúc cây
• Tham lam
• Xử lý xâu
• Hình giải tích
• Đồ Thị
• Mảng đánh dấu
• Vét cạn
• Đếm
• BFS và DFS
• Stack

Trong bài này, bạn hãy viết chương trình nhận vào một chuỗi (có thể khá dài) các ký tự số và đưa ra màn hình hoán vị kế tiếp của các ký tự số đó (với ý nghĩa là hoán vị có giá trị lớn hơn tiếp theo nếu ta coi chuỗi đó là một giá trị số nguyên).

Chú ý: Các ký tự số trong dãy có thể trùng nhau.

Ví dụ:

123 -> 132

279134399742 -> 279134423799

Cũng có trường hợp sẽ không thể có hoán vị kế tiếp. Ví dụ như khi đầu vào là chuỗi 987.

Dữ liệu vào

Dòng đầu tiên ghi số nguyên  t là số bộ test (1 ≤ t ≤ 1000).  Mỗi bộ test có một dòng, đầu tiên là số thứ tự bộ test, một dấu cách, sau đó là chuỗi các ký tự số, tối đa 80 phần tử.

Dữ liệu ra

Với mỗi bộ test hãy đưa ra một dòng gồm thứ tự bộ test, một dấu cách, tiếp theo đó là hoán vị kế tiếp hoặc chuỗi “BIGGEST” nếu không có hoán vị kế tiếp.

Example

Input:

3

1 123

2 279134399742

3 987

Output:

1 132

2 279134423799

3 BIGGEST

Ý tưởng: Thuật toán leo dốc 2 lần tìm hoán vị kế tiếp

Ví dụ với dãy 279134399742

• Bước 1: Đi ngược từ cuối dãy về dầu cứ tăng thì đi tiếp tới đỉnh dốc đó là 99742 được phần tử i là đỉnh lùi thêm 1 bước về tới số a[i] = 3.

• Bước 2: Leo dốc lần nữa đi từ cuối dãy tới khi lớn gặp phần tử đầu tiên lớn hơn a[i] thì dừng ở đây dừng tại vị trí 42
• Bước 3: hoán vị a[i]=3 và a[j]=4 cho nhau được dãy mới 279134499732
• Bước 4: Đảo ngược lại dãy từ a[i+1] tới hết a[n] tức là đảo phần 99732 -> 23799 ta thu được dãy 279134423799

Nguồn

http://www.spoj.com/PTIT/problems/BCNEPER/

Code

http://ideone.com/EG26pU

Thích Đang tải... Điều hướng bài viết ← 9763. Bảng tính Excel 9767. Partition thuận nghịch đệ quy →

Bình luận về bài viết này

Δ

• Bình luận
• Đăng lại
• Theo dõi Đã theo dõi
  • Lập trình C/C++
  Đã có 26 người theo dõi Theo dõi ngay
  • Đã có tài khoản WordPress.com? Đăng nhập.
• • Lập trình C/C++
  • Theo dõi Đã theo dõi
  • Đăng ký
  • Đăng nhập
  • URL rút gọn
  • Báo cáo nội dung
  • Xem toàn bộ bài viết
  • Quản lý theo dõi
  • Ẩn menu

%d Tạo trang giống vầy với WordPress.comHãy bắt đầu