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

hide comments
Raman Shukla: 2014-07-02 14:49:05

Congrats Arpit Uppal... U deserve it...

Last edit: 2014-07-17 23:30:33
Arpit Uppal: 2014-07-02 14:17:57

just do as the problem says :) my 300th classical on spoj :)

Raj Mehta: 2013-12-21 13:49:34

@Syaorann i did as u said still WA
<snip>

can u let me knw test case for which its failing

Last edit: 2022-08-09 22:39:16
Syaorann: 2013-01-24 11:35:44

just simply write the program like what it said.no other thing need to take into consideration,and u can AC it

Siddharth Bora: 2012-08-10 13:34:52

Important: To note that the open-addressing method calculates hashes j=1...19 on the original hash and not on the previous hash.

Aman Gupta: 2012-07-19 10:33:16

my solution works on ideone but here it is repeatedly giving NZEC
can someone please help?
<snip>

EDIT: You should use forum.

Last edit: 2022-08-09 22:39:23
Giovanni Botta: 2011-09-14 21:04:53

Is the open addressing performed by adding j^2+23*j to the previous hash code or to the original hash code h(.)?

i.e., what if I have this input (each string hashes to 42)?

1
21
ADD:B
ADD:XZ
ADD:ZY
ADD:bU
ADD:dT
ADD:fS
ADD:hR
ADD:jQ
ADD:lP
ADD:nO
ADD:pN
ADD:rM
ADD:tL
ADD:vK
ADD:xJ
ADD:zI
ADD:AEY
ADD:AHW
ADD:AKU
ADD:ANS
ADD:AQQ

Last edit: 2011-09-15 17:13:39
asqwzxdfercv: 2011-05-29 11:45:37

"After examining of at least 20 table entries"
This includes the original hash + j=1..19

took me some time to realize this

Jeevan K. S. Chalam: 2011-05-26 16:41:20

Done :)

Last edit: 2011-05-28 09:00:22
kiransk: 2011-04-14 10:33:16

input with string length ZERO allowed?
eg: are these valid
ADD:
DEL:


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:-