HASHIT - Hash it!

Your task is to calculate the result of the hashing process in a table of 101 elements, containing keys that are strings of length at most 15 letters (ASCII codes 'A',...,'z'). Implement the following operations:

  • find the index of the element defined by the key (ignore, if no such element),
  • insert a new key into the table (ignore insertion of the key that already exists),
  • delete a key from the table (without moving the others), by marking the position in table as empty (ignore non-existing keys in the table)

When performing find, insert and delete operations define the following function:
integer Hash(string key),
which for a string key=a1...an returns the value:
Hash(key)=h(key) mod 101, where
h(key)=19 *(ASCII(a1)*1+...+ASCII(an)*n).
Resolve collisions using the open addressing method, i.e. try to insert the key into the table at the first free position: (Hash(key)+j2+23*j) mod 101, for j=1,...,19. After examining of at least 20 table entries, we assume that the insert operation cannot be performed.

Input

t [the number of test cases <= 100]
n1 [the number of operations (one per line)[<= 1000]
ADD:string
[or]
DEL:string [other test cases, without empty lines betwee series]

Output

For every test case you have to create a new table, insert or delete keys, and write to the output:
the number of keys in the table [first line]
index:key [sorted by indices]

Example

Input:
1
11
ADD:marsz
ADD:marsz
ADD:Dabrowski
ADD:z
ADD:ziemii
ADD:wloskiej
ADD:do
ADD:Polski
DEL:od
DEL:do
DEL:wloskiej

Output:
5
34:Dabrowski
46:Polski
63:marsz
76:ziemii
96:z

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

hide comments
2016-01-14 15:33:54 Santosh Kumar Shaw
j can be 20. AC on the go.
2015-10-14 15:23:03 munjal
I am getting the WA. can any one post Test cases ... I tried with all test cases available in above posts. I am getting correct answer for them.
2015-08-17 21:07:39
it is a good problem .careful observation is needed while insertion and deletion of element in the hash table
2015-04-17 14:48:36 Binayaka
Consistently getting WA. Can somebody tell me what is the exact input and output format?
Input:
2
11
ADD:marsz
ADD:marsz
ADD:Dabrowski
ADD:z
ADD:ziemii
ADD:wloskiej
ADD:do
ADD:Polski
DEL:od
DEL:do
DEL:wloskiej
3
ADD:aac
ADD:aace
DEL:aac

Output:
5
34:Dabrowski
46:Polski
63:marsz
76:ziemii
96:z
1
86:aace
2015-03-09 19:30:24 opcode
Daniel Carvalho:
You mean:
Input:
1
3
ADD:aac
ADD:aace
DEL:aac
?
2015-03-05 13:16:50 Daniel Carvalho
A simple test case that can help you understand the problem. (The description can be a little bit problematic):
Input:
1
1
ADD:aac
ADD:aace
DEL:aac

Output:
1
86:aace
2014-12-18 18:55:00 agaurav77
Check before deletion and insertion. If not present already, then only insert. Seems silly to have a double check, but it would be really helpful. AC finally!
2014-12-10 15:11:04 Georeth Chow
There are too many hash table implementations. The spec is not clearly enough.
2014-10-14 15:57:12 Jakub ©afin
Question to the problemsetter: did you consider that "HASHIT" can be split as "HASH IT" and "HA SHIT"? :D
2014-10-05 22:13:59 Nishanth Vijayan
Great Question..Kudos to the problem setter.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.