이 게임에서 웜홀은 두 지역을 잇는 통로임. 편의상 시작점을 A지점이라 하고 웜홀의 반대편을 B지점이라 할게.


이 게임엔 여러 종류의 웜홀들이 있는데, 모든 웜홀들은 한번에 통과 가능한 질량 m과 웜홀이 붕괴되려면 필요한 질량 M이라는 수치가 있음. 통과 가능 질량 m과 붕괴에 필요한 질량 M은 웜홀의 종류마다 그 수치가 알려져있음. 근데 통과 가능 질량 m은 고정인 반면, 붕괴에 필요한 질량 M의 정확한 수치는 웜홀의 실제 instance마다 달라서 실제로는 알려진 수치와 +-10%의 오차가 있음. 이 오차는 후술할 방법으로 대략적으로 유추하는 것 외에는 알아낼 수 없음.


또 웜홀들은 잔여 질량 k가 0.1M ≤ k ≤ 0.5M을 만족할 때, 그리고 0 ≤ k ≤ 0.1M을 만족할 때 상태가 바뀌어서 이를 이용해 웜홀의 붕괴 필요 질량의 범위를 좁힐 수 있음.


그리고 붕괴 필요 질량 M은 전체 통과 가능 질량에 대한 상한이 아님. 즉 질량이 100 남은 웜홀을 질량이 300인 배로 통과하여 붕괴시키는게 가능하다는 얘기임.


이때 우리는 2~4대의 배를 이용해서 이 웜홀을 인위적으로 붕괴시키고싶음. 각 배들의 질량은 m-100로 동일하게 맞춰놓은 상태임. 단, 모든 배들은 질량을 m-100에서 m으로, m에서 m-100로 원할때마다 변경시킬 수 있음. 단 조건이 있는데, 모든 배들은 A지점에서 시작해 웜홀이 붕괴하기 전에 A 지점으로 모두 돌아와야 함.






예시) 웜홀 K346은 통과 가능 질량 m이 300이고, 붕괴 필요 질량 M은 2700 ~ 3300이다. 이때 질량이 200/300 중 가변적으로 선택 가능한 배들이 3대 있다.


만일 3대의 배가 A지점에서 B지점으로 모두 질량 300인채 통과하고, B지점에서 A지점으로 모두 질량 200인채 통과하였을때 상태가 바뀌지 않았다면, 우리는 웜홀의 실제 붕괴 질량이 3000 ≤ M ≤ 3300 임을 알 수 있다.






이때 내가 알고싶은건 두가지임.


1. 예시의 웜홀 K346을 예시의 조건에 따라 항상 안전하게 붕괴시키는 방법이 있는가?


2. 위 조건을 따라 웜홀을 붕괴시키는 것이 모든 m, M에 대해 가능한가? 가능하다면 웜홀을 붕괴시키는 방법을 찾는 일반적인 알고리즘이 존재하는가?




그냥 "대충 ~~한 방법을 쓰면 알아내는게 가능할 것 같다" 정도의 답이라도 괜찮으니까 도움좀 ㅠ










(수정) 사실 웜홀의 가짓수가 그렇게 다양하진 않아서 모든 M, m에 대해 일반화하는건 어렵기도 하고 쓸모가 없을거 같아서 질문을 더 좁혀볼게..


2* (M, m) = (3000, 300), (2000, 300)인 웜홀들을 붕괴시키는 안전한 방법이 있는가?