BCNEPER spoj PTIT – Hoán vị kế tiếp

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCNEPER/

1. Đề bài BCNEPER spoj

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.

Ví dụ

Input:
3

1 123

2 279134399742

3 987 Output:

1 132

2 279134423799

3 BIGGEST

2. Hướng dẫn BCNEPER spoj PTIT – Hoán vị kế tiếp

– Gọi S[i] là phần tử thứ i dãy số.

– gọi vt là vị trí đầu tiên làm cho số tại đó nhỏ hơn số phía sau nó khi xét từ cuối dãy trở về đầu

VD: 5 4 1 2 0 thì vt là 3, do số S[3]=1 nhỏ hơn s[4]=2.

tuy nhiên nếu không tìm được vt nào thỏa mản thì số này chính là số lớn nhất, write “BIGGEST” và kết thúc.

– Tìm số đầu tiên lớn hơn số S[vt] khi xét từ cuối dãy về vt. gọi vị trí của số này là vt1.

– Đổi chỗ vt1 và vt

sau đó ghi ra các số từ 1->vt. và ghi các số còn lại theo chiều ngược lại từ length(s) trở về vt+1.

3. Code Tham khảo BCNEPER spoj PTIT – Hoán vị kế tiếp