Advertisement
Guest User

Untitled

a guest
Jul 7th, 2015
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.96 KB | None | 0 0
  1. using System;
  2. using System.Text;
  3.  
  4. namespace HASHIT
  5. {
  6. class MainClass
  7. {
  8. public static void Main (string[] args)
  9. {
  10. int t = Convert.ToInt32 (System.Console.ReadLine ());
  11.  
  12. for (int i = 0; i < t; i++)
  13. {
  14. string[] table = new string[101];
  15. int n = Convert.ToInt32 (System.Console.ReadLine ());
  16. for (int i2 = 0; i2 < n; i2++)
  17. {
  18. string line = System.Console.ReadLine ();
  19. string op = line.Substring (0, 3);
  20. string key = line.Substring (4);
  21. int ix = FindKey (table, key);
  22.  
  23. if (op == "ADD")
  24. {
  25. if (ix == -1)
  26. {
  27. ix = FindNextOpenAddress (table, Hash (key));
  28. if (ix >= 0)
  29. {
  30. table[ix] = key;
  31. }
  32. }
  33. }
  34. else
  35. {
  36. if (ix >= 0)
  37. {
  38. table[ix] = string.Empty;
  39. }
  40. }
  41. }
  42.  
  43. StringBuilder sb = new StringBuilder ();
  44. int count = 0;
  45. for (int j = 0; j < 101; j++)
  46. {
  47. if (!string.IsNullOrEmpty (table[j]))
  48. {
  49. count++;
  50. sb.AppendLine (j + ":" + table[j]);
  51. }
  52. }
  53. Console.WriteLine (count);
  54. Console.Write (sb.ToString ());
  55. }
  56. }
  57.  
  58. public static int Hash (string key)
  59. {
  60. int ret = 0;
  61. ret = h (key) % 101;
  62. return ret;
  63. }
  64.  
  65. public static int h (string key)
  66. {
  67. int ret = 0;
  68. int cnt = key.Length;
  69. for (int i = 0; i < cnt; i++)
  70. {
  71. ret += (int)key[i] * (i + 1);
  72. }
  73. return ret * 19;
  74. }
  75.  
  76. public static int FindKey (string[] table, string key)
  77. {
  78. int ix = Hash (key);
  79. if (table[ix] == key)
  80. return ix;
  81. for (int j = 1; j < 20; j++)
  82. {
  83. int newix = (ix + j * j + 23 * j) % 101;
  84. if (table[newix] == key)
  85. {
  86. return newix;
  87. }
  88. }
  89. return -1;
  90. }
  91.  
  92. public static int FindNextOpenAddress (string[] table, int ix)
  93. {
  94. if (string.IsNullOrEmpty (table[ix]))
  95. return ix;
  96. for (int j = 1; j < 20; j++)
  97. {
  98. int newix = (ix + j * j + 23 * j) % 101;
  99. if (string.IsNullOrEmpty (table[newix]))
  100. {
  101. return newix;
  102. }
  103. }
  104. return -1;
  105. }
  106. }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement