Chatbox

Các bạn vui lòng dùng từ ngữ lịch sự và có văn hóa,sử dụng Tiếng Việt có dấu chuẩn. Chúc các bạn vui vẻ!
12/12/2013 23:12 # 1
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
2783. Hoán vị chữ cái


2783. Hoán vị chữ cái

Mã bài: QBHV

 

Cho một xâu S chỉ gồm các chữ cái in hoa, 1 <= độ dài <= 9.

Yêu cầu:

1: Có bao nhiêu cách hoán vị các chữ cái của xâu S

2: Liệt kê các hoán vị đó theo thứ tự từ điển

Input

Gồm 1 dòng duy nhất chứa xâu S

Output

Dòng 1: Ghi số lượng hoán vị tìm được (K)

K dòng tiếp theo, mỗi dòng ghi một xâu hoán vị của xâu S theo đúng thứ tự từ điển

Example

Input:
ABAB
Output:
6
AABB
ABAB
ABBA
BAAB
BABA
BBAA


======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
12/12/2013 23:12 # 2
BabyCoder
Cấp độ: 1 - Kỹ năng: 1

Kinh nghiệm: 4/10 (40%)
Kĩ năng: 1/10 (10%)
Ngày gia nhập: 12/12/2013
Bài gởi: 4
Được cảm ơn: 1
2783. Hoán vị chữ cái


Bài này dùng hàm có sẵn của C++ để sinh ra hoán vị kế tiếp, ở đây bạn có thể nhờ nó sinh để đếm đực số hoán vị nhưng sẽ bị TLE, nên mình làm như sau

#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
using namespace std;
int main()
{
   char s[50];
   scanf("%s", s);
   int n = strlen(s), res = 1;
   sort(s, s+n);
   int c[26];
   memset(c, 0, sizeof c);
   for (int i=0;i<n;++i) 
c[s[i]-'A']++;
   for (int i=0;i<n;++i) 
    res *= i+1;
   for (int j=0;j<26;++j)
   {
for (int i=0;i<c[j];++i)
{
    res /= i+1;
    }
   }
   printf("%d\n", res);
   do
   { 
printf("%s\n", s); 
   } 
   while(next_permutation(s, s+n));
   return 0;
}
 



 
Copyright© Đại học Duy Tân 2010 - 2019