Link Sub: http://www.spoj.com/PTIT/problems/PTIT127G/
Người Gửi: Darkness
- Problem:
Cho đoạn văn có N dòng, mỗi dòng chỉ chứa các chữ số và chữ cái in thuờng trong bảng chữ cái tiếng Anh. Nhiệm vụ của bạn là tìm tất cả các số trong đoạn văn và in chúng ra thành một dãy số không giảm. Để cho đơn giản, các số có các chữ số 0 bắt đầu sẽ xóa bỏ các chữ số 0 ở đầu. Các số được xác định duy nhất bằng cách quét qua đoạn văn và luôn lấy số lượng các chữ số lớn nhất có thể. Ví dụ: Các số 01a2b3456cde478 là 1, 2, 478, 3456.
Input
Dòng 1 chứa số nguyên N (1 ≤ N ≤ 100), là số dòng của đoạn văn.
N dòng tiếp theo, mỗi dòng chứa một chuỗi các chữ số và chữ cái in thuờng trong tiếng Anh. Mỗi dòng tối đa 100 kí tự.
Output
Gồm M dòng (M là số các số tìm được trong đoạn văn). Mỗi dòng chứa 1 số lấy từ đoạn văn. Các số được sắp xếp theo thứ tự không giảm.
Chú ý: M luôn không quá 500.
Example:
Gồm M dòng (M là số các số tìm được trong đoạn văn). Mỗi dòng chứa 1 số lấy từ đoạn văn. Các số được sắp xếp theo thứ tự không giảm.
Chú ý: M luôn không quá 500.
Input
2
lo3za4
01
Output:
1
3
4
Input
4
43silos0
zita002
le2sim
231233
Output:
0
2
2
43
231233
Input
4
01bond
02james007
03bond
04austinpowers000
Output:
0
1
2
3
4
7
- Solution:
Sử lí string:
- Tách các xâu dạng số;
- Sắp xếp (+so sánh xâu): Lưu ý khi so sánh: phải cùng chiều dài thì sring mới so sánh được như dạng số; (Sắp xếp dưới đây sử dụng thư viện có sẵn là: heap sort) Input
4
43silos0
zita002
le2sim
231233
Output:
0
2
2
43
231233
Input
4
01bond
02james007
03bond
04austinpowers000
Output:
0
1
2
3
4
7
- In ra (+chuẩn hóa: xóa số 0 ở đầu); Bonus: Code dưới đây xử lí so sánh xâu (không chuyển dạng số)
- Code:
C++:
https://ideone.com/mmUYIF
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct xau
{
string x;
} typedef xau;
int ssXau (xau a, xau b)
{
//Make same as length =102;
while (a.x.length()!=102) a.x='0'+a.x;
while (b.x.length()!=102) b.x='0'+b.x;
for (int i=0; i<102; i++)
{
int ai=a.x[i]-'0';
int bi=b.x[i]-'0';
if (ai>bi) return 0;
if (ai<bi) return 1;
}
return 1;
}
string chXau (string a) //chuan hoa Xau
{
int vt=-1;
for (int i=0; i<a.length(); i++)
{
if (a[i]!='0')
{
vt=i;
break;
}
}
if (vt==-1) return "0";
else if (vt!=0)
{
string tg="";
for (int i=vt; i<a.length(); i++) tg+=a[i];
return tg;
} else return a;
}
int main ()
{
//IN;
int N;
cin>>N;
string s;
xau SX[502];
int sl=0;
for (int k=1; k<=N; k++)
{
cin>>s;
//OUT;
for (int i=0; i<s.length(); i++)
{
if ('0'<=s[i] && s[i]<='9')
{
string tg="";
for (int j=i; j<s.length(); j++)
{
i=j;
if ('9'<s[j] || s[j]<'0') break;
else tg+=s[j];
}
sl++;
SX[sl].x=tg;
}
}
}
// Sap xep;
sort (SX+1, SX+sl+1, ssXau);
for (int i=1; i<=sl; i++)
{
cout<<chXau (SX[i].x)<<endl;
}
return 0;
}