Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBHV - Hoán vị chữ cái

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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


Được gửi lên bởi:special_one
Ngày:2008-06-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Lê Minh Hoàng

hide comments
2016-07-03 05:39:41
#include <bits/stdc++.h>
using namespace std;
const int maxsl = 362880;
char s[10];
char x[9];
int n, m;
std::map <char,int> D;
char a[9];
bool Free[9];
void QSort(int l , int r)
{
int i, j;
char key;
i = l; j = r; key = s[(l+r)/2];
while ( i <= j)
{
while ( s[i] < key) i++;
while ( s[j] > key) j--;
if ( i <= j)
{
swap(s[i], s[j]);
i++; j--;
}
}
if ( i < r) QSort(i,r);
if ( l < j) QSort(l,j);
}
int giaithua(int i)
{
if ( i == 0) return 1;
int tmp = 1;
for ( int j = 2; j <= i ; j++) tmp = tmp*j;
return (tmp);
}
void thu(int i)
{
int j;
for ( j = 0 ; j <= n - 1; j++)
if ( Free[j])
{
x[i] = s[j]; Free[j] = false;
if ( (i == n - 1 ) && (strcmp(x,a) == 1))
{
printf("%s\n",x);
//cout << x << endl;
//cout << x;
strcpy(a,x);
}
else thu( i + 1);
Free[j] = true;
}
}
int main()
{
scanf("%s",&s);
n = strlen(s);
QSort(0,n-1);
memset(Free , true, sizeof(Free));
for ( char ch = 'A'; ch <= 'Z'; ch++) D[ch] = 0;
for (int i = 0 ; i <= n - 1; i++) D[s[i]] ++;
int tmp = 1;
for ( char ch = 'A'; ch <= 'Z'; ch++) tmp = tmp*giaithua(D[ch]);
cout << giaithua(n)/tmp << endl;
//a = ""; m = 0;
thu(0);
return 0;
}
Sai o dau AE oi
2016-05-04 14:29:15 Phạm Huỳnh Nhật
t111 Tài liệu chuyên tin
2016-01-21 13:45:39 Lê Thanh Phú
thuat toan giong nhau: dem roi quay lui in.
c++ thi TLE
Pas thi AC
KDL string trong c++ cham hon chang?
2015-11-30 15:28:10
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/11/30/hoan-vi-chu-cai-qbhv/
2015-10-11 19:08:25 Vũ Quang Thịnh
Code lại như code cũ, TLE =)))))
2015-09-08 14:16:25
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-07-28 11:02:37 [Nghien] Le Long
Tính số hv dùng công thức có mỗi cái đệ quy 9! mà cx TLE là sao???
2015-05-17 16:40:22 there's no salvation for me...
á đù, nộp lần đầu tle , lần sau cop nguyên code thì AC @@
2015-01-21 16:00:59 lucky++
tính số hoán vị lặp theo công thức, sau đó quay lui in nghiệm.
2014-07-02 16:45:58 Con Bò Huyền Thoại
chỉ cần sort, tìm k, quay lui là AC rồi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.