fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	private static final int SAFE = 1;
  11. 	private static final int DANGER = 2;
  12.  
  13. 	private static int guess(int[] flag, int floor, int remaining) {
  14. 		int least = -1, assume = -1;
  15. 		for(int i = flag.length - 1; i >= 0; --i) {
  16. 			if(flag[i] == DANGER) {
  17. 				assume = i - 1;
  18. 			}
  19. 		}
  20. 		for(int i = 0; i < flag.length; ++i) {
  21. 			if(flag[i] == SAFE) {
  22. 				least = i;
  23. 			}
  24. 		}
  25. 		if(assume == -1) {
  26. 			assume = flag.length - 1;
  27. 		}
  28. 		if(least == assume && least == floor) {
  29. 			return 0;
  30. 		}
  31. 		if(remaining == 0 || least == assume) {
  32. 			return -1;
  33. 		}
  34. 		int t1 = -1, t2 = -1;
  35. 		if(remaining > 1) {
  36. 			int mid = (least + assume + 1) / 2;
  37. 			if(mid <= floor) {
  38. 				flag[mid] = SAFE;
  39. 				int t = guess(flag, floor, remaining);
  40. 				if(t == -1) {
  41. 					t1 = -1;
  42. 				} else {
  43. 					t1 = 1 + t;
  44. 				}
  45. 				flag[mid] = 0;
  46. 			} else {
  47. 				flag[mid] = DANGER;
  48. 				int t = guess(flag, floor, remaining - 1);
  49. 				if(t == -1) {
  50. 					t2 = -1;
  51. 				} else {
  52. 					t2 = 1 + t;
  53. 				}
  54. 				flag[mid] = 0;
  55. 			}
  56. 		} else {
  57. 			int mid = least + 1;
  58. 			if(mid <= floor) {
  59. 				flag[mid] = SAFE;
  60. 				int t = guess(flag, floor, remaining);
  61. 				if(t == -1) {
  62. 					t1 = -1;
  63. 				} else {
  64. 					t1 = 1 + t;
  65. 				}
  66. 				flag[mid] = 0;
  67. 			} else {
  68. 				flag[mid] = DANGER;
  69. 				int t = guess(flag, floor, remaining - 1);
  70. 				if(t == -1) {
  71. 					t2 = -1;
  72. 				} else {
  73. 					t2 = 1 + t;
  74. 				}
  75. 				flag[mid] = 0;
  76. 			}
  77. 		}
  78. 		if(t1 == -1) {
  79. 			return t2;
  80. 		} else if(t2 == -1) {
  81. 			return t1;
  82. 		}
  83. 		return t1 > t2 ? t1 : t2;
  84. 	}
  85.  
  86. 	public static void main(String[] args) {
  87. 		for(int floor = 1; floor <= 100; ++floor) {
  88. 			int[] flag = new int[102];
  89. 			for(int i = 0; i < flag.length; ++i) {
  90. 				flag[i] = 0;
  91. 			}
  92. 			flag[0] = SAFE;
  93. 			flag[101] = DANGER;
  94. 			int times = guess(flag, floor, 2);
  95. 			System.out.println(floor + "=>" + times);
  96. 		}
  97. 	}
  98. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1=>3
2=>4
3=>5
4=>6
5=>7
6=>8
7=>9
8=>10
9=>11
10=>12
11=>13
12=>14
13=>15
14=>16
15=>17
16=>18
17=>19
18=>20
19=>21
20=>22
21=>23
22=>24
23=>25
24=>26
25=>27
26=>28
27=>29
28=>30
29=>31
30=>32
31=>33
32=>34
33=>35
34=>36
35=>37
36=>38
37=>39
38=>40
39=>41
40=>42
41=>43
42=>44
43=>45
44=>46
45=>47
46=>48
47=>49
48=>50
49=>50
50=>3
51=>4
52=>5
53=>6
54=>7
55=>8
56=>9
57=>10
58=>11
59=>12
60=>13
61=>14
62=>15
63=>16
64=>17
65=>18
66=>19
67=>20
68=>21
69=>22
70=>23
71=>24
72=>25
73=>26
74=>26
75=>4
76=>5
77=>6
78=>7
79=>8
80=>9
81=>10
82=>11
83=>12
84=>13
85=>14
86=>15
87=>15
88=>5
89=>6
90=>7
91=>8
92=>9
93=>9
94=>6
95=>7
96=>7
97=>7
98=>7
99=>7
100=>7
https://ideone.com/B7E85H
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!