SBANK - Sorting Bank Accounts

In one of the internet banks thousands of operations are being performed every day. Since certain customers do business more actively than others, some of the bank accounts occur many times in the list of operations. Your task is to sort the bank account numbers in ascending order. If an account appears twice or more in the list, write the number of repetitions just after the account number. The format of accounts is as follows: 2 control digits, an 8-digit code of the bank, 16 digits identifying the owner (written in groups of four digits), for example (at the end of each line there is exactly one space):

30 10103538 2222 1233 6160 0142 

Banks are real-time institutions and they need FAST solutions. If you feel you can meet the challenge within a very stringent time limit, go ahead! A well designed sorting algorithm in a fast language is likely to succeed.

Input

t [the number of tests <= 5]
n [the number of accounts<= 100 000]
[list of accounts]
[empty line]
[next test cases]

Output

[sorted list of accounts with the number of repeated accounts]
[empty line]
[other results]

Example

Input:
2
6
03 10103538 2222 1233 6160 0142 
03 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 

5
30 10103538 2222 1233 6160 0144 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0145 
30 10103538 2222 1233 6160 0146 
30 10103538 2222 1233 6160 0143 

Output:
03 10103538 2222 1233 6160 0141 1
03 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0141 2
30 10103538 2222 1233 6160 0142 2

30 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0143 1
30 10103538 2222 1233 6160 0144 1
30 10103538 2222 1233 6160 0145 1
30 10103538 2222 1233 6160 0146 1

Added by:mima
Date:2004-06-01
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:-

hide comments
2015-08-28 15:08:36 ABHIJEET
very easy use of stl.. use getline in c++
2015-07-27 16:00:48 Vipul Sarin
Marek Ch is right. The problem description is incorrect. If an account appears once, then the number of repetitions must be printed as 1 in the answer.
2015-07-26 14:37:07
is it necessary to input space between control digit ,bank code and owner id?
2015-07-19 21:25:18 Marek Ch.
There is an error in the problem description/sample data:

"If an account appears twice or more in the list, write the number of repetitions just after the account number."
and
"30 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0143 1
30 10103538 2222 1233 6160 0144 1
30 10103538 2222 1233 6160 0145 1
30 10103538 2222 1233 6160 0146 1"
don't match. In the last case each of the account numbers appears once yet the number of repetitions are printed out.
2015-07-16 04:38:50 chinmay rakshit
implementation of red black tree sorting....
2015-06-24 16:06:08 Kshitij Garg
Implemented with a BST , Direct application :D
2015-05-31 05:40:08
runtime error too
2015-05-26 14:41:39 Kriti Joshi
Can I assume the 8 digit bank number to be const for all entries??
2015-02-21 19:03:41 Abhay
The time for best solutions is very less compared to mine. Will someone point me to the technique used in the best solutions?

Thanks

Edit: Thanks vamsi

re(vamsi):
1. Try to use most suitable data structure.
2. Judging by your run time(which is slower than many Python solutions), sort function you are using is slow.


Last edit: 2015-03-06 16:54:15
2014-12-05 22:10:13 numerix
@mjh: If you need help with your code use the forum and post your code there.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.