만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

김밥천국의 계단

면접 대비

시간 제한1초메모리 제한512 MB

요약
민희가 정확히 K번의 행동으로 N번째 계단에 도달할 수 있는지 판별합니다. 계단 i에서 두드리면 i + floor(i/2)번째 계단으로 이동합니다.
난이도

보통10점 중 5점

유형
BFS, 최단 경로
정답자
아직 제출이 없습니다

문제

민희는 미니김밥으로 유명한 천국에 가려고 합니다.

천국 문 앞에는 무한히 많은 계단이 있습니다. 가장 아래 계단의 번호는 0번이고, 위로 올라갈수록 번호가 1씩 커집니다. 그중 NN번째 계단 옆에 김밥 가게가 있습니다.

민희는 매번 다음 두 행동 중 하나를 선택해서 총 KK번 행동할 수 있습니다. 정확히 KK번째 행동에서 NN번째 계단에 도달하면 미니김밥을 먹을 수 있습니다.

  1. 계단 한 칸을 올라갑니다.
  2. 집에서 가지고 온 지팡이를 계단에 두드립니다. ii번째 계단에서 지팡이를 두드리면 i+⌊i2⌋i +\left \lfloor \cfrac{i}{2} \right \rfloor번째 계단으로 순간이동합니다.

민희는 현재 0번째 계단에 있습니다. 민희가 미니김밥을 먹을 수 있는지 구해 봅시다.

입력

첫 번째 줄에 계단 개수 NN과 계단을 오르는 횟수 KK가 주어집니다. (1≤N,K≤1 000 000)(1 \leq N, K \leq 1\,000\,000)

출력

민희가 NN개의 계단을 KK번 만에 올라 미니김밥을 먹을 수 있으면 minigimbob을, 그러지 못해 물만 마신다면 water을 출력합니다.

힌트

⌊x⌋\left \lfloor x \right \rfloor는 xx보다 작거나 같은 가장 큰 정수를 의미합니다.

예제2

  1. 예제 1

    입력
    5 2
    
    예상 출력
    water
    
  2. 예제 2

    입력
    42 10
    
    예상 출력
    minigimbob