문제
어떤 방에 n개의 물건이 있고, 각 물건은 특징을 가지고 있다. 각 특징은 예 또는 아니오로 대답할 수 있는 질문이다.
특징은 총 종류가 m개가 있다. 이러한 특징을 이용하면 이 방에 있는 모든 물건을 설명할 수 있다. 즉, 모든 물건은 길이가 일정한 불리언 수열로 나타낼 수 있다. 모든 물체는 다른 물체와 적어도 한 특징이 다르다.
상근이는 어떤 물체를 확인하려고 한다. 따라서, 그 물체의 특징을 알고 있는 사람에게 질문을 할 것이다. 모든 질문은 특징 중 하나이고, 모든 답변은 예 또는 아니오이다. 상근이는 답변을 들은 후에 다음 질문을 고를 수 있다.
상근이는 질문은 하나 할 때 마다 100원씩 내야 한다. 주머니 사정이 넉넉하지 않은 상근이는 돈을 가능한 적게 내려고 한다. 상근이는 모든 물체의 특징을 알고 있다. 하지만, 찾으려고 하는 물체의 특징은 알고 있지 못한다. 따라서, 상근이는 질문을 하기 전에 전략을 세울 수 있다.
물체의 특징이 주어졌을 때, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 구하는 프로그램을 작성하시오.
출력
각 테스트 케이스에 대해서, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 출력한다. 가능한 질문을 적게 해야 한다.
W3sicHJvYmxlbV9pZCI6IjM4ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWJiMzRcdWFjZTBcdWFjMWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzViNFx1YjVhNCBcdWJjMjlcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWJiM2NcdWFjNzRcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViYjNjXHVhYzc0XHVjNzQwIFx1ZDJiOVx1YzlkNVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMmI5XHVjOWQ1XHVjNzQwIFx1YzYwOCBcdWI2MTBcdWIyOTQgXHVjNTQ0XHViMmM4XHVjNjI0XHViODVjIFx1YjMwMFx1YjJmNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzljOFx1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMmI5XHVjOWQ1XHVjNzQwIFx1Y2QxZCBcdWM4ODVcdWI5NThcdWFjMDAgbVx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQyYjlcdWM5ZDVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHViYTc0IFx1Yzc3NCBcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJiM2NcdWFjNzRcdWM3NDQgXHVjMTI0XHViYTg1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIFx1YmIzY1x1YWM3NFx1Yzc0MCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjNzdjXHVjODE1XHVkNTVjIFx1YmQ4OFx1YjlhY1x1YzViOCBcdWMyMThcdWM1ZjRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWIyOTQgXHViMmU0XHViOTc4IFx1YmIzY1x1Y2NiNFx1YzY0MCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1ZDJiOVx1YzlkNVx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1YjRcdWI1YTQgXHViYjNjXHVjY2I0XHViOTdjIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhZGY4IFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM5YzhcdWJiMzhcdWM3NDAgXHVkMmI5XHVjOWQ1IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWIyZjVcdWJjYzBcdWM3NDAgXHVjNjA4IFx1YjYxMFx1YjI5NCBcdWM1NDRcdWIyYzhcdWM2MjRcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZjVcdWJjYzBcdWM3NDQgXHViNGU0XHVjNzQwIFx1ZDZjNFx1YzVkMCBcdWIyZTRcdWM3NGMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWM4XHViYjM4XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWQ1NjAgXHViNTRjIFx1YjljOFx1YjJlNCAxMDBcdWM2ZDBcdWM1MjkgXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOGZjXHViYTM4XHViMmM4IFx1YzBhY1x1YzgxNVx1Yzc3NCBcdWIxMDlcdWIxMDlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIzYzhcdWM3NDQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzgwMVx1YWM4YyBcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NDAgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzljOFx1YmIzOFx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWMxMzhcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYjNjXHVjY2I0XHVjNzU4IFx1ZDJiOVx1YzlkNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHVkNTU4XHViYTc0IFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWI5N2MgXHVhZDZjXHViY2M0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmI5XHVjOWQ1XHVjNzU4IFx1YWMxY1x1YzIxOCBtXHVhY2ZjIFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsdDsgbSAmbGU7IDExLCAwICZsdDsgbiAmbGU7IDEyOCkgXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJiM2NcdWNjYjRcdWM3NTggXHVkMmI5XHVjOWQ1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMmI5XHVjOWQ1XHVjNzQwIFx1YWUzOFx1Yzc3NFx1YWMwMCBtXHVjNzc4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVhYzAxIFx1YWMxMlx1Yzc0MCAxKFx1YzYwOCkgXHViNjEwXHViMjk0IDAoXHVjNTQ0XHViMmM4XHVjNjI0KVx1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHVkNTU4XHViYTc0IFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWI5N2MgXHVhZDZjXHViY2M0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1YzgwMVx1YWM4YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4ODIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUd2VudHkgUXVlc3Rpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIGNsb3NlZCB3b3JsZCBhbmQgYSBzZXQgb2YgZmVhdHVyZXMgdGhhdCBhcmUgZGVmaW5lZCBmb3IgYWxsIHRoZSBvYmplY3RzIGluIHRoZSB3b3JsZC4gRWFjaCBmZWF0dXJlIGNhbiBiZSBhbnN3ZXJlZCB3aXRoICZsZHF1bzt5ZXMmcmRxdW87IG9yICZsZHF1bztubyZyZHF1bzsuIFVzaW5nIHRob3NlIGZlYXR1cmVzLCB3ZSBjYW4gaWRlbnRpZnkgYW55IG9iamVjdCBmcm9tIHRoZSByZXN0IG9mIHRoZSBvYmplY3RzIGluIHRoZSB3b3JsZC4gSW4gb3RoZXIgd29yZHMsIGVhY2ggb2JqZWN0IGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIGZpeGVkLWxlbmd0aCBzZXF1ZW5jZSBvZiBib29sZWFucy4gQW55IG9iamVjdCBpcyBkaVx1ZmIwMGVyZW50IGZyb20gb3RoZXIgb2JqZWN0cyBieSBhdCBsZWFzdCBvbmUgZmVhdHVyZS48XC9wPlxyXG5cclxuPHA+WW91IHdvdWxkIGxpa2UgdG8gaWRlbnRpZnkgYW4gb2JqZWN0IGZyb20gb3RoZXJzLiBGb3IgdGhpcyBwdXJwb3NlLCB5b3UgY2FuIGFzayBhIHNlcmllcyBvZiBxdWVzdGlvbnMgdG8gc29tZW9uZSB3aG8ga25vd3Mgd2hhdCB0aGUgb2JqZWN0IGlzLiBFdmVyeSBxdWVzdGlvbiB5b3UgY2FuIGFzayBpcyBhYm91dCBvbmUgb2YgdGhlIGZlYXR1cmVzLiBIZVwvc2hlIGltbWVkaWF0ZWx5IGFuc3dlcnMgZWFjaCBxdWVzdGlvbiB3aXRoICZsZHF1bzt5ZXMmcmRxdW87IG9yICZsZHF1bztubyZyZHF1bzsgY29ycmVjdGx5LiBZb3UgY2FuIGNob29zZSB0aGUgbmV4dCBxdWVzdGlvbiBhZnRlciB5b3UgZ2V0IHRoZSBhbnN3ZXIgdG8gdGhlIHByZXZpb3VzIHF1ZXN0aW9uLjxcL3A+XHJcblxyXG48cD5Zb3Uga2luZGx5IHBheSB0aGUgYW5zd2VyZXIgMTAwIHllbiBhcyBhIHRpcCBmb3IgZWFjaCBxdWVzdGlvbi4gQmVjYXVzZSB5b3UgZG9uJnJzcXVvO3QgaGF2ZSBzdXJwbHVzIG1vbmV5LCBpdCBpcyBuZWNlc3NhcnkgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBxdWVzdGlvbnMgaW4gdGhlIHdvcnN0IGNhc2UuIFlvdSBkb24mcnNxdW87dCBrbm93IHdoYXQgaXMgdGhlIGNvcnJlY3QgYW5zd2VyLCBidXQgZm9ydHVuYXRlbHkga25vdyBhbGwgdGhlIG9iamVjdHMgaW4gdGhlIHdvcmxkLiBUaGVyZWZvcmUsIHlvdSBjYW4gcGxhbiBhbiBvcHRpbWFsIHN0cmF0ZWd5IGJlZm9yZSB5b3Ugc3RhcnQgcXVlc3Rpb25pbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBtdWx0aXBsZSBkYXRhc2V0cy4gRWFjaCBkYXRhc2V0IGJlZ2lucyB3aXRoIGEgbGluZSB3aGljaCBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMsIG0gYW5kIG46IHRoZSBudW1iZXIgb2YgZmVhdHVyZXMsIGFuZCB0aGUgbnVtYmVyIG9mIG9iamVjdHMsIHJlc3BlY3RpdmVseS4gWW91IGNhbiBhc3N1bWUgMCAmbHQ7IG0gJmxlOyAxMSBhbmQgMCAmbHQ7IG4gJmxlOyAxMjguIEl0IGlzIGZvbGxvd2VkIGJ5IG4gbGluZXMsIGVhY2ggb2Ygd2hpY2ggY29ycmVzcG9uZHMgdG8gYW4gb2JqZWN0LiBFYWNoIGxpbmUgaW5jbHVkZXMgYSBiaW5hcnkgc3RyaW5nIG9mIGxlbmd0aCBtIHdoaWNoIHJlcHJlc2VudCB0aGUgdmFsdWUgKCZsZHF1bzt5ZXMmcmRxdW87IG9yICZsZHF1bztubyZyZHF1bzspIG9mIGZlYXR1cmVzLiBUaGVyZSBhcmUgbm8gdHdvIGlkZW50aWNhbCBvYmplY3RzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG1pbmltaXplIHRoZSBtYXhpbXVtIG51bWJlciBvZiBxdWVzdGlvbnMgYnkgd2hpY2ggZXZlcnkgb2JqZWN0IGlzIGlkZW50aWZpYWJsZSBhbmQgb3V0cHV0IHRoZSByZXN1bHQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d
