Link Sub: http://www.spoj.com/PTIT/problems/PTIT138B/
Người Gửi: Dương Lee
- Problem:
Một buổi họp mặt đại gia đình nhân dịp cụ già Ted tròn 100 tuổi, người ta muốn sắp xếp con cháu của cụ theo thứ tự từ tuổi cao xuống thấp. Giả sử ta có thông tin về giấy khai sinh của từng người đó. Mỗi giấy khai sinh chỉ viết ba thông tin đơn giản gồm: Tên người cha, Tên người con, Tuổi của người cha lúc sinh con.
Hãy giúp đại gia đình trên tính ra tuổi của từng người con cháu cụ Ted và viết ra danh sách theo thứ tự từ tuổi cao xuống thấp.
Input
Dòng đầu ghi số bộ test (không quá 100). Với mỗi bộ test:
- Dòng đầu tiên ghi số X (0<X<100) là số người con cháu cần sắp xếp.
- Tiếp theo là X dòng, mỗi dòng ghi thông tin về một giấy khai sinh của từng người (thứ tự ngẫu nhiên) gồm 3 thành phần, mỗi thành phần cách nhau một khoảng trống:
- Tên người cha: không quá 20 ký tự và không chứa khoảng trống
- Tên người con: không quá 20 ký tự và không chứa khoảng trống
- Tuổi của người cha khi sinh con: 1 số nguyên dương, không quá 100.
Output
Với mỗi bộ test, in ra màn hình thứ tự bộ test (xem thêm trong bộ test ví dụ), sau đó lần lượt là từng người trong danh sách tuổi từ cao xuống thấp (không tính cụ Ted). Mỗi người viết ra hai thông tin: tên, một khoảng trống rồi đến tuổi của người đó.
Nếu hai người có cùng tuổi thì xếp theo thứ tự từ điển.
Example:
Với mỗi bộ test, in ra màn hình thứ tự bộ test (xem thêm trong bộ test ví dụ), sau đó lần lượt là từng người trong danh sách tuổi từ cao xuống thấp (không tính cụ Ted). Mỗi người viết ra hai thông tin: tên, một khoảng trống rồi đến tuổi của người đó.
Nếu hai người có cùng tuổi thì xếp theo thứ tự từ điển.
Input
2
1
Ted Bill 25
4
Ray James 40
James Beelzebub 17
Ray Mark 75
Ted Ray 20
Output:
DATASET 1
Bill 75
DATASET 2
Ray 80
James 40
Beelzebub 23
Mark 5
- Solution:
- Bài này ta đệ quy bắt đầu từ Ted và tìm khoảng cách giữa ông ta và các con. Với mỗi con tìm được thì lại coi đứa con đó là cha và đệ quy tiếp với khoảng cách tìm được. Khoảng cách tuổi khi trừ đi tuổi lúc sinh con là tuổi của con. - Cuối cùng là dùng hàm sort và in ra.