시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB167574840.000%

문제

운동선수 유라의 코치 민혁이는 체력 측정을 위해서 유라에게 l 미터 달리기를 시키려고 한다. 유라는 v1 m/s 이상 v2 m/s 이하의 일정한 속력으로 달린다.

타이머를 이용하여 유라의 기록을 측정하려던 참에, 민혁이는 타이머를 갖고 오는 것을 잊어버렸다. 유라의 속력을 측정하는 것에 차질이 생긴 민혁이는 다른 방법을 이용하여 유라의 속력을 측정해야 한다.

민혁이는 특정 시점에 시작점과 도착점 사이의 특정 지역에 가서 유라가 이미 왔는지 확인할 수 있다. 이런 방식으로 몇 번 확인하다 보면 +-t/2 m/s의 오차 범위를 감안한 유라의 속력을 구할 수 있다.

민혁이가 특정 지점에 가서 유라의 도달 여부를 확인하는 데 최소 s초의 시간이 걸린다. 따라서 유라가 달리기를 시작한 후 s초 동안은 유라의 도달 여부를 확인할 수 없으며, 유라의 도달 여부를 확인한 후 그 다음 s초 동안 역시 유라의 도달 여부를 확인할 수 없다.

민혁이는 최악의 경우에도 최소한의 확인으로 유라의 속력을 측정하려고 한다. 민혁이를 도와 유라의 속력을 측정하는 전략을 짜는 프로그램을 작성하여라.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 c (1 ≤ c ≤ 100)가 주어진다.

두 번째 줄부터 c개의 줄에는 정수 l, v1, v2, t, s (1 ≤ l, v1, v2, t, s ≤ 109, v1 < v2)가 주어진다.

출력

각 테스트 케이스에 대해서 답을 한 줄에 하나씩 출력한다.

만약 민혁이가 오차 범위 내에서 유라의 속력을 구할 수 없다면 'impossible'을 출력한다. 그렇지 않은 경우 민혁이가 유라의 속력을 구하기 위한 최소 확인 수를 출력한다.

예제 입력 1

3
1000 1 30 1 1
60 2 10 2 5
59 2 10 2 5

예제 출력 1

5
3
impossible
W3sicHJvYmxlbV9pZCI6IjEwNzkwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmVjXHViOWFjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2YjRcdWIzZDlcdWMxMjBcdWMyMTggXHVjNzIwXHViNzdjXHVjNzU4IFx1Y2Y1NFx1Y2U1OCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjY2I0XHViODI1IFx1Y2UyMVx1YzgxNVx1Yzc0NCBcdWM3MDRcdWQ1NzRcdWMxMWMmbmJzcDtcdWM3MjBcdWI3N2NcdWM1ZDBcdWFjOGMgbCZuYnNwO1x1YmJmOFx1ZDEzMCBcdWIyZWNcdWI5YWNcdWFlMzBcdWI5N2MmbmJzcDtcdWMyZGNcdWQwYTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3MjBcdWI3N2NcdWIyOTQgdjxzdWI+MTxcL3N1Yj4gbVwvcyBcdWM3NzRcdWMwYzEgdjxzdWI+MjxcL3N1Yj4gbVwvcyBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzdjXHVjODE1XHVkNTVjIFx1YzE4ZFx1YjgyNVx1YzczY1x1Yjg1YyBcdWIyZWNcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDBjMFx1Yzc3NFx1YmEzOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjNzIwXHViNzdjXHVjNzU4IFx1YWUzMFx1Yjg1ZFx1Yzc0NCBcdWNlMjFcdWM4MTVcdWQ1NThcdWI4MjRcdWIzNTggXHVjYzM4XHVjNWQwLCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVkMGMwXHVjNzc0XHViYTM4XHViOTdjIFx1YWMxNlx1YWNlMCBcdWM2MjRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc4YVx1YzViNFx1YmM4NFx1YjgzOFx1YjJlNC4gXHVjNzIwXHViNzdjXHVjNzU4IFx1YzE4ZFx1YjgyNVx1Yzc0NCBcdWNlMjFcdWM4MTVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNWQwIFx1Y2MyOFx1YzljOFx1Yzc3NCBcdWMwZGRcdWFlMzQgXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YzcyMFx1Yjc3Y1x1Yzc1OCBcdWMxOGRcdWI4MjVcdWM3NDQgXHVjZTIxXHVjODE1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1ZDJiOVx1YzgxNSBcdWMyZGNcdWM4MTBcdWM1ZDAgXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1YjNjNFx1Y2MyOVx1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVkMmI5XHVjODE1IFx1YzljMFx1YzVlZFx1YzVkMCBcdWFjMDBcdWMxMWMgXHVjNzIwXHViNzdjXHVhYzAwIFx1Yzc3NFx1YmJmOCBcdWM2NTRcdWIyOTRcdWM5YzAgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHViYTg3IFx1YmM4OCBcdWQ2NTVcdWM3NzhcdWQ1NThcdWIyZTQgXHViY2Y0XHViYTc0ICstdFwvMiBtXC9zXHVjNzU4Jm5ic3A7XHVjNjI0XHVjYzI4IFx1YmM5NFx1YzcwNFx1Yjk3YyBcdWFjMTBcdWM1NDhcdWQ1NWMmbmJzcDtcdWM3MjBcdWI3N2NcdWM3NTggXHVjMThkXHViODI1XHVjNzQ0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWFjMDAgXHVkMmI5XHVjODE1Jm5ic3A7XHVjOWMwXHVjODEwXHVjNWQwIFx1YWMwMFx1YzExYyBcdWM3MjBcdWI3N2NcdWM3NTggXHViM2M0XHViMmVjIFx1YzVlY1x1YmQ4MFx1Yjk3YyBcdWQ2NTVcdWM3NzhcdWQ1NThcdWIyOTQgXHViMzcwIFx1Y2Q1Y1x1YzE4YyBzXHVjZDA4XHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3MjBcdWI3N2NcdWFjMDAgXHViMmVjXHViOWFjXHVhZTMwXHViOTdjIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWQ2YzQgc1x1Y2QwOCBcdWIzZDlcdWM1NDhcdWM3NDAgXHVjNzIwXHViNzdjXHVjNzU4Jm5ic3A7XHViM2M0XHViMmVjIFx1YzVlY1x1YmQ4MFx1Yjk3YyBcdWQ2NTVcdWM3NzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVjNzIwXHViNzdjXHVjNzU4IFx1YjNjNFx1YjJlYyBcdWM1ZWNcdWJkODBcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTVjIFx1ZDZjNCBcdWFkZjggXHViMmU0XHVjNzRjIHNcdWNkMDggXHViM2Q5XHVjNTQ4Jm5ic3A7XHVjNWVkXHVjMmRjIFx1YzcyMFx1Yjc3Y1x1Yzc1OCBcdWIzYzRcdWIyZWMgXHVjNWVjXHViZDgwXHViOTdjIFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjNjNCZuYnNwO1x1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWQ2NTVcdWM3NzhcdWM3M2NcdWI4NWMgXHVjNzIwXHViNzdjXHVjNzU4IFx1YzE4ZFx1YjgyNVx1Yzc0NCBcdWNlMjFcdWM4MTVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiZmNcdWQ2MDFcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzcyMFx1Yjc3Y1x1Yzc1OCBcdWMxOGRcdWI4MjVcdWM3NDQgXHVjZTIxXHVjODE1XHVkNTU4XHViMjk0IFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWM5ZGNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBjJm5ic3A7KDEgJmxlOyBjICZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIGNcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCZuYnNwO2wsIHY8c3ViPjE8XC9zdWI+LCB2PHN1Yj4yPFwvc3ViPiwgdCwmbmJzcDtzICgxICZsZTsgbCwgdjxzdWI+MTxcL3N1Yj4sIHY8c3ViPjI8XC9zdWI+LCB0LCBzICZsZTsgMTA8c3VwPjk8XC9zdXA+LCB2PHN1Yj4xPFwvc3ViPiZuYnNwOyZsdDsgdjxzdWI+MjxcL3N1Yj4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViMmY1XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkJm5ic3A7XHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIFx1YzYyNFx1Y2MyOCBcdWJjOTRcdWM3MDQgXHViMGI0XHVjNWQwXHVjMTFjJm5ic3A7XHVjNzIwXHViNzdjXHVjNzU4IFx1YzE4ZFx1YjgyNVx1Yzc0NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAmIzM5O2ltcG9zc2libGUmIzM5O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwJm5ic3A7XHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIFx1YzcyMFx1Yjc3Y1x1Yzc1OCBcdWMxOGRcdWI4MjVcdWM3NDQgXHVhZDZjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVkNjU1XHVjNzc4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA3OTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaXBlIFN0cmVhbSIsImRlc2NyaXB0aW9uIjoiPHA+WW91ciBob21ldG93biBoYXMgaGlyZWQgc29tZSBjb250cmFjdG9ycyAmbmRhc2g7IGluY2x1ZGluZyB5b3UhICZuZGFzaDsgdG8gbWFuYWdlIGl0cyBtdW5pY2lwYWwgcGlwZSBuZXR3b3JrLiBUaGV5IGJ1aWx0IHRoZSBuZXR3b3JrLCBhdCBncmVhdCBleHBlbnNlLCB0byBzdXBwbHkgRmx1YmJlciB0byBldmVyeSBob21lIGluIHRvd24uIFVuZm9ydHVuYXRlbHksIG5vYm9keSBoYXMgZm91bmQgYSB1c2UgZm9yIEZsdWJiZXIgeWV0LCBidXQgbmV2ZXIgbWluZC4gSXQgd2FzIGEgRmx1YmJlciBuZXR3b3JrIG9yIGEgZmlyZSBkZXBhcnRtZW50LCBhbmQgaG9uZXN0bHksIGhvdXNlcyBidXJuIGRvd24gc28gcmFyZWx5LCBhIGZpcmUgZGVwYXJ0bWVudCBoYXJkbHkgc2VlbXMgbmVjZXNzYXJ5LjxcL3A+XHJcblxyXG48cD5JbiB0aGUgcG9zc2libGUgZXZlbnQgdGhhdCBzb21lYm9keSBzb21ld2hlcmUgZGVjaWRlcyB0aGV5IHdhbnQgc29tZSBGbHViYmVyLCB0aGV5IHdvdWxkIGxpa2UgdG8ga25vdyBob3cgcXVpY2tseSBpdCB3aWxsIGZsb3cgdGhyb3VnaCB0aGUgcGlwZXMuIE1lYXN1cmluZyBpdHMgcmF0ZSBvZiBmbG93IGlzIHlvdXIgam9iLjxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSBhY2Nlc3MgdG8gb25lIG9mIHRoZSBwaXBlcyBjb25uZWN0ZWQgdG8gdGhlIG5ldHdvcmsuIFRoZSBwaXBlIGlzIGwgbWV0ZXJzIGxvbmcsIGFuZCB5b3UgY2FuIHN0YXJ0IHRoZSBmbG93IG9mIEZsdWJiZXIgdGhyb3VnaCB0aGlzIHBpcGUgYXQgYSB0aW1lIG9mIHlvdXIgY2hvb3NpbmcuIFlvdSBrbm93IHRoYXQgaXQgZmxvd3Mgd2l0aCBhIGNvbnN0YW50IHJlYWwtdmFsdWVkIHNwZWVkLCB3aGljaCBpcyBhdCBsZWFzdCB2PHN1Yj4xPFwvc3ViPiBtZXRlcnNcL3NlY29uZCBhbmQgYXQgbW9zdCB2PHN1Yj4yPFwvc3ViPiBtZXRlcnNcL3NlY29uZC4gWW91IHdhbnQgdG8gZXN0aW1hdGUgdGhpcyBzcGVlZCB3aXRoIGFuIGFic29sdXRlIGVycm9yIG9mIGF0IG1vc3QgdFwvMiBtZXRlcnNcL3NlY29uZC48XC9wPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgdGhlIHBpcGUgaXMgb3BhcXVlLCBzbyB0aGUgb25seSB0aGluZyB5b3UgY2FuIGRvIGlzIHRvIGtub2NrIG9uIHRoZSBwaXBlIGF0IGFueSBwb2ludCBhbG9uZyBpdHMgbGVuZ3RoLCB0aGF0IGlzLCBpbiB0aGUgY2xvc2VkIHJlYWwtdmFsdWVkIHJhbmdlIFswLCBsXS4gTGlzdGVuaW5nIHRvIHRoZSBzb3VuZCBvZiB0aGUga25vY2sgd2lsbCB0ZWxsIHlvdSB3aGV0aGVyIG9yIG5vdCB0aGUgRmx1YmJlciBoYXMgcmVhY2hlZCB0aGF0IHBvaW50LiBZb3UgYXJlIG5vdCBpbmZpbml0ZWx5IGZhc3QuIFlvdXIgZmlyc3Qga25vY2sgbXVzdCBiZSBhdCBsZWFzdCBzIHNlY29uZHMgYWZ0ZXIgc3RhcnRpbmcgdGhlIGZsb3csIGFuZCB0aGVyZSBtdXN0IGJlIGF0IGxlYXN0IHMgc2Vjb25kcyBiZXR3ZWVuIGtub2Nrcy48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIGEgc3RyYXRlZ3kgdGhhdCB3aWxsIHJlcXVpcmUgdGhlIGZld2VzdCBrbm9ja3MsIGluIHRoZSB3b3JzdCBjYXNlLCB0byBlc3RpbWF0ZSBob3cgZmFzdCB0aGUgRmx1YmJlciBpcyBmbG93aW5nLiBOb3RlIHRoYXQgaW4gc29tZSBjYXNlcyB0aGUgZGVzaXJlZCBlc3RpbWF0aW9uIG1pZ2h0IGJlIGltcG9zc2libGUgKGZvciBleGFtcGxlLCBpZiB0aGUgRmx1YmJlciByZWFjaGVzIHRoZSBlbmQgb2YgdGhlIHBpcGUgdG9vIHF1aWNrbHkpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgYyAoMSAmbGU7IGMgJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggb2YgdGhlIG5leHQgYyBsaW5lcyBkZXNjcmliZXMgb25lIHRlc3QgY2FzZS4gRWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgdGhlIGZpdmUgaW50ZWdlcnMgbCwgdjxzdWI+MTxcL3N1Yj4sIHY8c3ViPjI8XC9zdWI+LCB0IGFuZCBzICgxICZsZTsgbCwgdjxzdWI+MTxcL3N1Yj4sIHY8c3ViPjI8XC9zdWI+LCB0LCBzICZsZTsgMTA8c3VwPjk8XC9zdXA+IGFuZCB2PHN1Yj4xPFwvc3ViPiAmbHQ7IHY8c3ViPjI8XC9zdWI+KSwgd2hpY2ggYXJlIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgdGhlIG1pbmltYWwgbnVtYmVyIG9mIGtub2NrcyByZXF1aXJlZCB0byBlc3RpbWF0ZSB0aGUgZmxvdyBzcGVlZCBpbiB0aGUgd29yc3QgY2FzZS4gSWYgaXQgbWlnaHQgYmUgaW1wb3NzaWJsZSB0byBtZWFzdXJlIHRoZSBmbG93IHNwZWVkIGFjY3VyYXRlbHkgZW5vdWdoLCBkaXNwbGF5IGltcG9zc2libGUgaW5zdGVhZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > World Finals > ACM-ICPC World Finals 2015 G번