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
|
Varkha Sharma:
2018-02-03 15:40:00
1
|
|
zhaoweicheng98:
2017-10-14 10:17:05
Try this test case:
|
|
Saif :
2017-06-16 13:59:08
Use this test case:
|
|
kspoj:
2017-06-16 08:57:40
Guys, I'm stuck, my code is running fine with most spoj toolkit testcases... But I'm getting WA...
|
|
rishi_devan:
2017-05-01 14:40:08
Straightforward ! |
|
cake_is_a_lie:
2017-03-06 14:46:25
Not double inserting existing items can become problematic after deletions, so be careful! Cost me a lot of WAs. |
|
vengatesh15:
2017-02-13 08:47:28
There should be a blank line after every test case .. that cost me 2WA |
|
samnik:
2017-02-12 07:41:58
can anyone help me working for test cases but still getting WA
|
|
Bartosz:
2016-10-23 13:15:46
Empty string is also considered to be a valid key, and it have to be put on the position 0. It cost me few WAs to realize that. Last edit: 2016-10-23 13:43:45 |
|
gautam:
2016-08-06 15:40:10
yeah....ac.....!!!! |
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: | - |