시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 8 8 80.000%

문제

구글은 실리콘밸리 중심가 101번 고속도로가 통과하는 곳에 다음과 같은 광고판을 달았다.

"{first 10-digit prime found in consecutive digits of e}.com"

구글의 채용 방법에 크게 감동한 구강 청정제 회사 가글에서는 다음과 같은 문제로 사람을 뽑으려고 한다.

{어떤 유리수를 7진법으로 나타낸 뒤, 소수점 B번째 자리부터 E번째 자리까지}.com

예를 들어, 1/510를 7진법으로 나타내면 0.12541...7, 33/410는 11.15151...7, 6/4910은 0.06000...7이다.

유리수가 주어졌을 때, 이 유리수의 소수점 B번째 자리부터 E번째 자리까지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 N, D, B, E가 10진수로 한 줄에 하나씩 주어진다. N과 D는 유리수의 분자와 분모이고, 0 ≤ N ≤ 5,000, 1 ≤ D ≤ 5,000을 만족한다. B와 E는 구해야 하는 수의 범위이다. 0 ≤ B,E ≤ 250, 0 ≤ (E-B) ≤ 20을 만족한다. 소수점 0번째 자리는 소수점 바로 오른쪽에 있는 수이다.

출력

각 테스트 케이스에 대해서, 다음과 같이 출력한다.

Problem set k: N / D, base 7 digits B through E: result

k는 테스트 케이스 번호, result는 계산한 값, 다른 값은 입력에 주어진 값이다.

예제 입력 1

4
1 5 0 0
6 49 1 3
33 4 2 7
511 977 122 126

예제 출력 1

Problem set 1: 1 / 5, base 7 digits 0 through 0: 1
Problem set 2: 6 / 49, base 7 digits 1 through 3: 600
Problem set 3: 33 / 4, base 7 digits 2 through 7: 151515
Problem set 4: 511 / 977, base 7 digits 122 through 126: 12425
W3sicHJvYmxlbV9pZCI6IjQ2MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWFlMDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWQ2Y1x1YWUwMFx1Yzc0MCBcdWMyZTRcdWI5YWNcdWNmNThcdWJjMzhcdWI5YWMgXHVjOTExXHVjMmVjXHVhYzAwIDEwMVx1YmM4OCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWFjMDAgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1YWNmM1x1YzVkMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWQxMVx1YWNlMFx1ZDMxMFx1Yzc0NCBcdWIyZWNcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPiZxdW90O3tmaXJzdCAxMC1kaWdpdCBwcmltZSBmb3VuZCBpbiBjb25zZWN1dGl2ZSBkaWdpdHMgb2YgZX0uY29tJnF1b3Q7PFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlx1YWQ2Y1x1YWUwMFx1Yzc1OCBcdWNjNDRcdWM2YTkgXHViYzI5XHViYzk1XHVjNWQwIFx1ZDA2Y1x1YWM4YyBcdWFjMTBcdWIzZDlcdWQ1NWMgXHVhZDZjXHVhYzE1IFx1Y2NhZFx1YzgxNVx1YzgxYyBcdWQ2OGNcdWMwYWMgXHVhYzAwXHVhZTAwXHVjNWQwXHVjMTFjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYjM4XHVjODFjXHViODVjIFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWJmNTFcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48YmxvY2txdW90ZT57XHVjNWI0XHViNWE0IFx1YzcyMFx1YjlhY1x1YzIxOFx1Yjk3YyA3XHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWI0YTQsIFx1YzE4Y1x1YzIxOFx1YzgxMCBCXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YmQ4MFx1ZDEzMCBFXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMH0uY29tPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDFcLzU8c3ViPjEwPFwvc3ViPlx1Yjk3YyA3XHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3NCAwLjEyNTQxLi4uPHN1Yj43PFwvc3ViPiwgMzNcLzQ8c3ViPjEwPFwvc3ViPlx1YjI5NCAxMS4xNTE1MS4uLjxzdWI+NzxcL3N1Yj4sIDZcLzQ5PHN1Yj4xMDxcL3N1Yj5cdWM3NDAgMC4wNjAwMC4uLjxzdWI+NzxcL3N1Yj5cdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcyMFx1YjlhY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjNzIwXHViOWFjXHVjMjE4XHVjNzU4IFx1YzE4Y1x1YzIxOFx1YzgxMCBCXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YmQ4MFx1ZDEzMCBFXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IE4sIEQsIEIsIEVcdWFjMDAgMTBcdWM5YzRcdWMyMThcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVhY2ZjIERcdWIyOTQgXHVjNzIwXHViOWFjXHVjMjE4XHVjNzU4IFx1YmQ4NFx1Yzc5MFx1YzY0MCBcdWJkODRcdWJhYThcdWM3NzRcdWFjZTAsIDAgJmxlOyBOICZsZTsgNSwwMDAsIDEgJmxlOyBEICZsZTsgNSwwMDBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LiBCXHVjNjQwIEVcdWIyOTQgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM3NTggXHViYzk0XHVjNzA0XHVjNzc0XHViMmU0LiAwICZsZTsgQixFICZsZTsgMjUwLCAwICZsZTsgKEUtQikgJmxlOyAyMFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuIFx1YzE4Y1x1YzIxOFx1YzgxMCAwXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YjI5NCBcdWMxOGNcdWMyMThcdWM4MTAgXHViYzE0XHViODVjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcblByb2JsZW0gc2V0IGs6IE4gXC8gRCwgYmFzZSA3IGRpZ2l0cyBCIHRocm91Z2ggRTogcmVzdWx0PFwvcHJlPlxyXG5cclxuPHA+a1x1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOCwgcmVzdWx0XHViMjk0IFx1YWNjNFx1YzBiMFx1ZDU1YyBcdWFjMTIsIFx1YjJlNFx1Yjk3OCBcdWFjMTJcdWM3NDAgXHVjNzg1XHViODI1XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDYyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbnNlY3V0aXZlIERpZ2l0cyIsImRlc2NyaXB0aW9uIjoiPHA+QXMgYSByZWNydWl0aW5nIHBsb3ksIEdvb2dsZSBvbmNlIHBvc3RlZCBiaWxsYm9hcmRzIGluIEhhcnZhcmQgU3F1YXJlIGFuZCBpbiB0aGUgU2lsaWNvbiBWYWxsZXkgYXJlYSBqdXN0IHN0YXRpbmcgJmxkcXVvO3tmaXJzdCAxMC1kaWdpdCBwcmltZSBmb3VuZCBpbiBjb25zZWN1dGl2ZSBkaWdpdHMgb2YgZX0uY29tJnJkcXVvOy4gSW4gb3RoZXIgd29yZHMsIGZpbmQgdGhhdCAxMC1kaWdpdCBzZXF1ZW5jZSBhbmQgdGhlbiBjb25uZWN0IHRvIHRoZSB3ZWIgc2l0ZSAmbWRhc2g7IGFuZCBmaW5kIG91dCB0aGF0IEdvb2dsZSBpcyB0cnlpbmcgdG8gaGlyZSBwZW9wbGUgd2hvIGNhbiBzb2x2ZSBhIHBhcnRpY3VsYXIga2luZCBvZiBwcm9ibGVtLjxcL3A+XHJcblxyXG48cD5Ob3QgdG8gYmUgb3V0ZG9uZSwgR2FnZ2xlIChhIGxvb3N5LWdvb3N5IGZ1enp5IGxvZ2ljIHNlYXJjaCBmaXJtKSwgaGFzIGRldmlzZWQgaXRzIG93biByZWNydWl0aW5nIHByb2JsZW0uIENvbnNpZGVyIHRoZSBiYXNlIDcgZXhwYW5zaW9uIG9mIGEgcmF0aW9uYWwgbnVtYmVyLiBGb3IgZXhhbXBsZSwgdGhlIGZpcnN0IGZldyBkaWdpdHMgb2YgdGhlIGJhc2UgNyBleHBhbnNpb24gb2YgMVwvNTxzdWI+MTA8XC9zdWI+ID0gMC4xMjU0MS4uLjxzdWI+NzxcL3N1Yj4sIDMzXC80PHN1Yj4xMDxcL3N1Yj4gPSAxMS4xNTE1MS4uLjxzdWI+NzxcL3N1Yj4sIGFuZCA2XC80OTxzdWI+MTA8XC9zdWI+ID0gMC4wNjAwMC4uLjxzdWI+NzxcL3N1Yj4sIEZyb20gdGhpcyBleHBhbnNpb24sIGZpbmQgdGhlIGRpZ2l0cyBpbiBhIHBhcnRpY3VsYXIgcmFuZ2Ugb2YgcG9zaXRpb25zIHRvIHRoZSByaWdodCBvZiB0aGUgJnF1b3Q7ZGVjaW1hbCZxdW90OyBwb2ludDxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgcHJvYmxlbSBzZXRzIGluIHRoZSBmaWxlLiBFYWNoIHByb2JsZW0gc2V0IGlzIHNwZWNpZmllZCBieSBmb3VyIGJhc2UgMTAgbnVtYmVycyBvbiBhIHNpbmdsZSBsaW5lLCBuIGQgYiBlLCB3aGVyZSBuIGFuZCBkIGFyZSB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBvZiB0aGUgcmF0aW9uYWwgbnVtYmVyIGFuZCAwICZsZTsgbiAmbGU7IDUsMDAwIGFuZCAxICZsZTsgZCAmbGU7IDUsMDAwLiBiIGFuZCBlIGFyZSB0aGUgYmVnaW5uaW5nIGFuZCBlbmRpbmcgcG9zaXRpb25zIGZvciB0aGUgZGVzaXJlZCByYW5nZSBvZiBkaWdpdHMsIHdpdGggMCAmbGU7IGIsZSAmbGU7IDI1MCBhbmQgMCAmbGU7IChlLWIpICZsZTsgMjAuIE5vdGUgdGhhdCAwIGlzIHRoZSBwb3NpdGlvbiBpbW1lZGlhdGVseSB0byB0aGUgcmlnaHQgb2YgdGhlIGRlY2ltYWwgcG9pbnQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RWFjaCBwcm9ibGVtIHNldCB3aWxsIGJlIG51bWJlcmVkIChiZWdpbm5pbmcgYXQgb25lKSBhbmQgd2lsbCBnZW5lcmF0ZSBhIHNpbmdsZSBsaW5lOjxcL3A+XHJcblxyXG48cHJlPlxyXG5Qcm9ibGVtIHNldCBrOiBuIFwvIGQsIGJhc2UgNyBkaWdpdHMgYiB0aHJvdWdoIGU6IHJlc3VsdDxcL3ByZT5cclxuXHJcbjxwPndoZXJlIGsgaXMgcmVwbGFjZWQgYnkgdGhlIHByb2JsZW0gc2V0IG51bWJlciwgcmVzdWx0IGlzIHlvdXIgY29tcHV0ZWQgcmVzdWx0LCBhbmQgdGhlIG90aGVyIHZhbHVlcyBhcmUgdGhlIGNvcnJlc3BvbmRpbmcgaW5wdXQgdmFsdWVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Mid-Central Regional > 2005 Mid-Central Regional Programming Contest G번