종만이의 절친한 친구인 Jack은 한국의 Smart Guy 종만에게 아래와 같은 질문을 해왔다. Jack은 얼마 전 다양한 크기의 원기둥 모양의 (높이는 모두동일) 장난감들과 그 장난감들을 쌓아둘 수 있는 보관함을 구입했다. 장난감들 위에는 1부터 N번까지 번호가 붙여져 있어서, Jack은 1번부터 차례로 N번까지 그 보관함에 넣어두려 한다.

보관함에는 최대 M개까지의 원기둥 장난감을 저장해 둘 수 있는데, 보관함 모양이 랜덤하게 생겼다. 그래서 반지름이 R인 원기둥 장난감을 위에서 똑바로 떨어트리면, 밑으로 죽- 떨어지다가, 바닥까지 닿거나, 혹은 바로 이전에 쌓인 원기둥 위에 닿거나, 혹은 중간에 반지름이 커서 통과할 수 없게 되어 걸리거나 하는 식으로 저장되게 된다.

예를 들어 3개의 원기둥이 있고, 각각 순서대로 반지름 길이가 3 2 5 라고 하고, 보관함은 바닥부터 반지름이 3, 2, 6, 3, 4, 6, 5 (이하)인 원기둥들을 저장할 수 있다고 하자.

위 예와 같이, 처음에 1번 원기둥을 떨어뜨리면 높이 3인 곳에 멈추게 된다. 왜냐면 그 아래는 반지름 길이가 2 이하인 원기둥만 통과할 수 있기 때문이다. 두 번째 원기둥은 반지름이 2라서 작으므로, 이전에 떨어뜨린 3번 원기둥 위에 정지하게 된다. 5번 원기둥은 그림과 같이 위에서 두 번째 칸에 멈추게 된다. Jack이 알고 싶은 것은, 자신의 N개의 원기둥이 모두 보관될 수 있는지, 있다면 N번 원기둥은 위에서 몇 번째 칸에 멈추게 되는지 알고 싶다. 불가능 하다면 0 번째 칸에 멈춘다고 생각하자. (0번째 칸은, 보관함의 범위를 벗어난다) 종만이는 귀찮은 나머지 절친한 친구인 당신에게 Jack의 궁금증을 풀어주는 프로그램을 작성해달라고 부탁했다. 문제를 풀어보자.

#1306 upload 30 done 10 how_to_reg 10

jack timer 1s memory 64MB

#1306

jack 1s 64MB