Statistics

Problem Statement for "LogiciansAndBeer"

Problem Statement

Three logicians walk into a bar. The bartender asks them: "Do all of you want a beer?"
The first logician answers "I don't know."
The second logician answers "I don't know."
The third logician answers "Yes."
The bartender brings them three beers.


If you don't understand what's going on, here's an explanation of the joke:

In the joke, all three logicians clearly do want a beer, but they are also logicians. The first two logicians have to give the logically correct answer "I don't know", because the question asked whether everyone wants a beer and these logicians are not sure yet whether that's true. Only the third logician, after hearing the first two logicians, correctly deduces that everyone really wants a beer.


This problem is a generalized version of the above joke.

There are N perfectly logical logicians. Each logician either wants a beer or doesn't want a beer. Each logician only knows their own preference, they have no idea whether their friends want a beer.

The bartender asks them the same question as above: "Do all of you want a beer?" The logicians answer, one after another. Each logician considers their own preference and everything they heard before when formulating their statement. Each statement is one of "Yes", "No", and "I don't know".


You are given the statements made by the logicians: a String responses with N characters. The character '+' represents the answer "Yes", '-' represents "No", and '?' represents "I don't know".

First, determine whether responses represents a valid set of responses that could have been given by N logicians with some preferences. If it is not valid, return -1.

If responses represents a valid set of responses, imagine that you are the bartender. After hearing all the responses, you can make the conclusion that at least A and at most B of the logicians want a beer. Find and return the value of A.

Definition

Class:
LogiciansAndBeer
Method:
bringBeer
Parameters:
String
Returns:
int
Method signature:
int bringBeer(String responses)
(be sure your method is public)

Notes

  • The value of N is not given explicitly. You can determine it as the number of characters in responses.

Constraints

  • responses will contain between 1 and 50 characters, inclusive.
  • Each character in responses will be '+', '-', or '?'.

Examples

  1. "??+"

    Returns: 3

    The responses from the original joke. The only possibility is that all three of them want beer.

  2. "????-"

    Returns: 4

    Here the only possibility is that the first four logicians do want a beer but the last one does not.

  3. "-+-+-+"

    Returns: -1

    These responses are impossible, they contradict each other. In particular, the second logician cannot give the answer "Yes" (meaning "everyone wants a beer") when the first logician already said "No" (meaning that there is someone who doesn't want a beer).

  4. "?-----"

    Returns: 1

    Now there are many possibilities. For example: It's possible that only the second logician does not want beer and all five others do. It's also possible that only the first and the fourth logicians want beer. And it's also possible that only the first logician wants beer. The bartender's correct conclusion after hearing one "I don't know" followed by five "No"s is that the number of wanted beers is somewhere between A=1 and B=5, inclusive.

  5. "+"

    Returns: 1

  6. "-"

    Returns: 0

  7. "?"

    Returns: -1

  8. "++"

    Returns: -1

  9. "+-"

    Returns: -1

  10. "+?"

    Returns: -1

  11. "-+"

    Returns: -1

  12. "--"

    Returns: 0

  13. "-?"

    Returns: -1

  14. "?+"

    Returns: 2

  15. "?-"

    Returns: 1

  16. "??"

    Returns: -1

  17. "+++"

    Returns: -1

  18. "++-"

    Returns: -1

  19. "++?"

    Returns: -1

  20. "+-+"

    Returns: -1

  21. "+--"

    Returns: -1

  22. "+-?"

    Returns: -1

  23. "+?+"

    Returns: -1

  24. "+?-"

    Returns: -1

  25. "+??"

    Returns: -1

  26. "-++"

    Returns: -1

  27. "-+-"

    Returns: -1

  28. "-+?"

    Returns: -1

  29. "--+"

    Returns: -1

  30. "---"

    Returns: 0

  31. "--?"

    Returns: -1

  32. "-?+"

    Returns: -1

  33. "-?-"

    Returns: -1

  34. "-??"

    Returns: -1

  35. "?++"

    Returns: -1

  36. "?+-"

    Returns: -1

  37. "?+?"

    Returns: -1

  38. "?-+"

    Returns: -1

  39. "?--"

    Returns: 1

  40. "?-?"

    Returns: -1

  41. "??+"

    Returns: 3

  42. "??-"

    Returns: 2

  43. "???"

    Returns: -1

  44. "++++"

    Returns: -1

  45. "+++-"

    Returns: -1

  46. "+++?"

    Returns: -1

  47. "++-+"

    Returns: -1

  48. "++--"

    Returns: -1

  49. "++-?"

    Returns: -1

  50. "++?+"

    Returns: -1

  51. "++?-"

    Returns: -1

  52. "++??"

    Returns: -1

  53. "+-++"

    Returns: -1

  54. "+-+-"

    Returns: -1

  55. "+-+?"

    Returns: -1

  56. "+--+"

    Returns: -1

  57. "+---"

    Returns: -1

  58. "+--?"

    Returns: -1

  59. "+-?+"

    Returns: -1

  60. "+-?-"

    Returns: -1

  61. "+-??"

    Returns: -1

  62. "+?++"

    Returns: -1

  63. "+?+-"

    Returns: -1

  64. "+?+?"

    Returns: -1

  65. "+?-+"

    Returns: -1

  66. "+?--"

    Returns: -1

  67. "+?-?"

    Returns: -1

  68. "+??+"

    Returns: -1

  69. "+??-"

    Returns: -1

  70. "+???"

    Returns: -1

  71. "-+++"

    Returns: -1

  72. "-++-"

    Returns: -1

  73. "-++?"

    Returns: -1

  74. "-+-+"

    Returns: -1

  75. "-+--"

    Returns: -1

  76. "-+-?"

    Returns: -1

  77. "-+?+"

    Returns: -1

  78. "-+?-"

    Returns: -1

  79. "-+??"

    Returns: -1

  80. "--++"

    Returns: -1

  81. "--+-"

    Returns: -1

  82. "--+?"

    Returns: -1

  83. "---+"

    Returns: -1

  84. "----"

    Returns: 0

  85. "---?"

    Returns: -1

  86. "--?+"

    Returns: -1

  87. "--?-"

    Returns: -1

  88. "--??"

    Returns: -1

  89. "-?++"

    Returns: -1

  90. "-?+-"

    Returns: -1

  91. "-?+?"

    Returns: -1

  92. "-?-+"

    Returns: -1

  93. "-?--"

    Returns: -1

  94. "-?-?"

    Returns: -1

  95. "-??+"

    Returns: -1

  96. "-??-"

    Returns: -1

  97. "-???"

    Returns: -1

  98. "?+++"

    Returns: -1

  99. "?++-"

    Returns: -1

  100. "?++?"

    Returns: -1

  101. "?+-+"

    Returns: -1

  102. "?+--"

    Returns: -1

  103. "?+-?"

    Returns: -1

  104. "?+?+"

    Returns: -1

  105. "?+?-"

    Returns: -1

  106. "?+??"

    Returns: -1

  107. "?-++"

    Returns: -1

  108. "?-+-"

    Returns: -1

  109. "?-+?"

    Returns: -1

  110. "?--+"

    Returns: -1

  111. "?---"

    Returns: 1

  112. "?--?"

    Returns: -1

  113. "?-?+"

    Returns: -1

  114. "?-?-"

    Returns: -1

  115. "?-??"

    Returns: -1

  116. "??++"

    Returns: -1

  117. "??+-"

    Returns: -1

  118. "??+?"

    Returns: -1

  119. "??-+"

    Returns: -1

  120. "??--"

    Returns: 2

  121. "??-?"

    Returns: -1

  122. "???+"

    Returns: 4

  123. "???-"

    Returns: 3

  124. "????"

    Returns: -1

  125. "---------------------------------------------"

    Returns: 0

  126. "?--------------------------------------------"

    Returns: 1

  127. "???????--------------------------------------"

    Returns: 7

  128. "?????????????--------------------------------"

    Returns: 13

  129. "???????????????????????????????????????????--"

    Returns: 43

  130. "????????????????????????????????????????????-"

    Returns: 44

  131. "----------------------------------------------"

    Returns: 0

  132. "?---------------------------------------------"

    Returns: 1

  133. "???????---------------------------------------"

    Returns: 7

  134. "?????????????---------------------------------"

    Returns: 13

  135. "????????????????????????????????????????????--"

    Returns: 44

  136. "?????????????????????????????????????????????-"

    Returns: 45

  137. "-----------------------------------------------"

    Returns: 0

  138. "?----------------------------------------------"

    Returns: 1

  139. "???????----------------------------------------"

    Returns: 7

  140. "?????????????----------------------------------"

    Returns: 13

  141. "?????????????????????????????????????????????--"

    Returns: 45

  142. "??????????????????????????????????????????????-"

    Returns: 46

  143. "------------------------------------------------"

    Returns: 0

  144. "?-----------------------------------------------"

    Returns: 1

  145. "???????-----------------------------------------"

    Returns: 7

  146. "?????????????-----------------------------------"

    Returns: 13

  147. "??????????????????????????????????????????????--"

    Returns: 46

  148. "???????????????????????????????????????????????-"

    Returns: 47

  149. "-------------------------------------------------"

    Returns: 0

  150. "?------------------------------------------------"

    Returns: 1

  151. "???????------------------------------------------"

    Returns: 7

  152. "?????????????------------------------------------"

    Returns: 13

  153. "???????????????????????????????????????????????--"

    Returns: 47

  154. "????????????????????????????????????????????????-"

    Returns: 48

  155. "--------------------------------------------------"

    Returns: 0

  156. "?-------------------------------------------------"

    Returns: 1

  157. "???????-------------------------------------------"

    Returns: 7

  158. "?????????????-------------------------------------"

    Returns: 13

  159. "????????????????????????????????????????????????--"

    Returns: 48

  160. "?????????????????????????????????????????????????-"

    Returns: 49

  161. "????????????????????????????????????????????+"

    Returns: 45

  162. "???????????????????????????????????????????++"

    Returns: -1

  163. "???????????????????????????????????????????+-"

    Returns: -1

  164. "???????????????????????????????????????????+?"

    Returns: -1

  165. "???????????????????????????????????????????-?"

    Returns: -1

  166. "???????????????????????????????????????????-+"

    Returns: -1

  167. "?????????????????????????????????????????????+"

    Returns: 46

  168. "????????????????????????????????????????????++"

    Returns: -1

  169. "????????????????????????????????????????????+-"

    Returns: -1

  170. "????????????????????????????????????????????+?"

    Returns: -1

  171. "????????????????????????????????????????????-?"

    Returns: -1

  172. "????????????????????????????????????????????-+"

    Returns: -1

  173. "??????????????????????????????????????????????+"

    Returns: 47

  174. "?????????????????????????????????????????????++"

    Returns: -1

  175. "?????????????????????????????????????????????+-"

    Returns: -1

  176. "?????????????????????????????????????????????+?"

    Returns: -1

  177. "?????????????????????????????????????????????-?"

    Returns: -1

  178. "?????????????????????????????????????????????-+"

    Returns: -1

  179. "???????????????????????????????????????????????+"

    Returns: 48

  180. "??????????????????????????????????????????????++"

    Returns: -1

  181. "??????????????????????????????????????????????+-"

    Returns: -1

  182. "??????????????????????????????????????????????+?"

    Returns: -1

  183. "??????????????????????????????????????????????-?"

    Returns: -1

  184. "??????????????????????????????????????????????-+"

    Returns: -1

  185. "????????????????????????????????????????????????+"

    Returns: 49

  186. "???????????????????????????????????????????????++"

    Returns: -1

  187. "???????????????????????????????????????????????+-"

    Returns: -1

  188. "???????????????????????????????????????????????+?"

    Returns: -1

  189. "???????????????????????????????????????????????-?"

    Returns: -1

  190. "???????????????????????????????????????????????-+"

    Returns: -1

  191. "?????????????????????????????????????????????????+"

    Returns: 50

  192. "????????????????????????????????????????????????++"

    Returns: -1

  193. "????????????????????????????????????????????????+-"

    Returns: -1

  194. "????????????????????????????????????????????????+?"

    Returns: -1

  195. "????????????????????????????????????????????????-?"

    Returns: -1

  196. "????????????????????????????????????????????????-+"

    Returns: -1

  197. "-?-?--?--"

    Returns: -1

  198. "-?+++--??+-?-++??"

    Returns: -1

  199. "++?-??-?-??++?+"

    Returns: -1

  200. "+-?-??"

    Returns: -1

  201. "?+?-+-?+-"

    Returns: -1

  202. "?-+?--??+--?--??+?+?+---??+"

    Returns: -1

  203. "+??++-??"

    Returns: -1

  204. "--+?-????-??-+?++--?++-++++??-?"

    Returns: -1

  205. "--+?+-+-+"

    Returns: -1

  206. "++??-+-?"

    Returns: -1

  207. "?+++?-?+"

    Returns: -1

  208. "?+-+++-+?-+???+??-??+?-"

    Returns: -1

  209. "+----?-?"

    Returns: -1

  210. "?+-?"

    Returns: -1

  211. "-??+-?-?"

    Returns: -1

  212. "--+-+"

    Returns: -1

  213. "?---?????+?+?-+-?--"

    Returns: -1

  214. "????"

    Returns: -1

  215. "?--?+??++?---"

    Returns: -1

  216. "++??--+-?+-?--+-+-?----?++?"

    Returns: -1

  217. "+--?-?--"

    Returns: -1

  218. "++----"

    Returns: -1

  219. "-?+??-"

    Returns: -1

  220. "??+??-++?+?+--++-+?-+?+?+?-+--"

    Returns: -1

  221. "?-?+?-++--?+?+?---?+-??--?+--+"

    Returns: -1

  222. "-??+--+"

    Returns: -1

  223. "-?+?+??+"

    Returns: -1

  224. "?-??+?+-?+-?+-?-+?-?+??-"

    Returns: -1

  225. "++?+++"

    Returns: -1

  226. "?+?++"

    Returns: -1

  227. "??????"

    Returns: -1

  228. "???????"

    Returns: -1

  229. "+????"

    Returns: -1

  230. "???-?"

    Returns: -1

  231. "??++-"

    Returns: -1

  232. "?????????"

    Returns: -1

  233. "??-??"

    Returns: -1

  234. "?????"

    Returns: -1

  235. "???+++??"

    Returns: -1

  236. "?????????????????????????????????????++++++++++++"

    Returns: -1

  237. "+???+"

    Returns: -1

  238. "????????"

    Returns: -1

  239. "??--+"

    Returns: -1

  240. "????+"

    Returns: 5

  241. "???????????????????????????????--?????----"

    Returns: -1

  242. "?????+++++"

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: