시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB107676354497258.323%

문제

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

[그림]

자연수 n에 대해 n ≥ 1의 삼각수 Tn는 명백한 공식이 있다.

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

  • 4 = T1 + T2
  • 5 = T1 + T1 + T2
  • 6 = T2 + T2 or 6 = T3
  • 10 = T1 + T2 + T3 or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

예제 입력 1

3
10
20
1000

예제 출력 1

1
0
1
W3sicHJvYmxlbV9pZCI6IjEwNDQ4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzIwXHViODA4XHVjZTc0IFx1Yzc3NFx1Yjg2MCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGJjXHVhYzAxXHVjMjE4IFQ8c3ViPm48XC9zdWI+KG4gJmdlOyAxKVx1YjI5NCBbXHVhZGY4XHViOWJjXVx1YzVkMFx1YzExY1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVhZTMwXHVkNTU4XHVkNTU5XHVjODAxXHVjNzNjXHViODVjIFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWJhYThcdWM1OTFcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YWMxNlx1YjI5NCBcdWM4MTBcdWI0ZTRcdWM3NTggXHViYWE4XHVjNzRjXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9ldXJla2EucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPltcdWFkZjhcdWI5YmNdPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzVmMFx1YzIxOCBuXHVjNWQwIFx1YjMwMFx1ZDU3NCBuICZnZTsgMVx1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMTggVDxzdWI+bjxcL3N1Yj5cdWIyOTQgXHViYTg1XHViYzMxXHVkNTVjIFx1YWNmNVx1YzJkZFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlQ8c3ViPm48XC9zdWI+ID0gMSArIDIgKyAzICsgLi4uICsgbiA9IG4obisxKVwvMjxcL3A+XHJcblxyXG48cD4xNzk2XHViMTQ0LCBcdWFjMDBcdWM2YjBcdWMyYTRcdWIyOTQgXHViYWE4XHViNGUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDAgM1x1YWMxY1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1Yzk5ZFx1YmE4NVx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCw8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT40ID0gVDxzdWI+MTxcL3N1Yj4gKyBUPHN1Yj4yPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT41ID0gVDxzdWI+MTxcL3N1Yj4gKyBUPHN1Yj4xPFwvc3ViPiArIFQ8c3ViPjI8XC9zdWI+PFwvbGk+XHJcblx0PGxpPjYgPSBUPHN1Yj4yPFwvc3ViPiArIFQ8c3ViPjI8XC9zdWI+IG9yIDYgPSBUPHN1Yj4zPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT4xMCA9IFQ8c3ViPjE8XC9zdWI+ICsgVDxzdWI+MjxcL3N1Yj4gKyBUPHN1Yj4zPFwvc3ViPiBvciAxMCA9IFQ8c3ViPjQ8XC9zdWI+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzc0IFx1YWNiMFx1YWNmY1x1YjI5NCBcdWM5OWRcdWJhODVcdWM3NDQgXHVhZTMwXHViMTUwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFkZjhcdWM3NTggXHViMmU0XHVjNzc0XHVjNWI0XHViOWFjXHVjNWQwICZsZHF1bztFdXJla2EhIG51bSA9ICZEZWx0YTsgKyAmRGVsdGE7ICsgJkRlbHRhOyZyZHF1bzsgXHViNzdjXHVhY2UwIFx1YzgwMVx1Yzc0MFx1YWM4M1x1YzVkMFx1YzExYyBcdWM3MjBcdWI4MDhcdWNlNzQgXHVjNzc0XHViODYwXHVjNzNjXHViODVjIFx1YzU0Y1x1YjgyNFx1Yzg0Y1x1YjJlNC4gXHVhZmNkXHVjNzQwIFx1YmE4N1x1YmE4NyBcdWM3OTBcdWM1ZjBcdWMyMThcdWFjMDAgXHVjODE1XHVkNjU1XHVkNzg4IDNcdWFjMWNcdWM3NTggXHVjMGJjXHVhYzAxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWMyZGNcdWM1ZDBcdWMxMWMsIDVcdWM2NDAgMTBcdWM3NDAgXHVjODE1XHVkNjU1XHVkNzg4IDNcdWFjMWNcdWM3NTggXHVjMGJjXHVhYzAxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYyA0XHVjNjQwIDZcdWM3NDAgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjODE1XHVkNjU1XHVkNzg4IDNcdWFjMWNcdWM3NTggXHVjMGJjXHVhYzAxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzBcdWI5N2MgXHVkMzEwXHViMmU4XHVkNTc0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWI3N2MuIFx1YjJlOCwgM1x1YWMxY1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThcdWFjMDAgXHViYWE4XHViNDUwIFx1YjJlY1x1Yjc3Y1x1YzU3YyBcdWQ1NjAgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM3OTBcdWM1ZjBcdWMyMTggSyAoMyAmbGU7IEsgJmxlOyAxLDAwMClcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBUXHVhYzFjXHVjNzU4IFx1Yjc3Y1x1Yzc3OFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWIzMDBcdWQ1NzQgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWI3N2NcdWM3NzhcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgS1x1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggM1x1YWMxY1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQgMVx1Yzc0NCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDQ0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV1cmVrYSBUaGVvcmVtIiwiZGVzY3JpcHRpb24iOiI8cD5BIHRyaWFuZ2xlIG51bWJlciBUPHN1Yj5uPFwvc3ViPihuICZnZTsgMSkgaXMgYSBmaWd1cmF0ZSBudW1iZXIgdGhhdCBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSByZWd1bGFyIGdlb21ldHJpYyBhcnJhbmdlbWVudCBvZiBlcXVhbGx5IHNwYWNlZCBwb2ludHMgYXMgaWxsdXN0cmF0ZWQgaW4gRmlndXJlIDEuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2V1cmVrYS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTlweDsgd2lkdGg6NDE2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEuPFwvcD5cclxuXHJcbjxwPlRoZSB0cmlhbmdsZSBudW1iZXIgVDxzdWI+bjxcL3N1Yj4gZm9yIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIG4gJmdlOyAxIGlzIGdpdmVuIGJ5IHRoZSBleHBsaWNpdCBmb3JtdWxhOjxcL3A+XHJcblxyXG48cD5UPHN1Yj5uPFwvc3ViPiA9IDEgKyAyICsgMyArIC4uLiArIG4gPSBuKG4rMSlcLzI8XC9wPlxyXG5cclxuPHA+SW4gMTc5NiwgR2F1c3MgcHJvdmVkIHRoYXQgZXZlcnkgcG9zaXRpdmUgaW50ZWdlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgYXQgbW9zdCB0aHJlZSB0cmlhbmdsZSBudW1iZXJzLiBGb3IgZXhhbXBsZXMsPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+NCA9IFQ8c3ViPjE8XC9zdWI+ICsgVDxzdWI+MjxcL3N1Yj48XC9saT5cclxuXHQ8bGk+NSA9IFQ8c3ViPjE8XC9zdWI+ICsgVDxzdWI+MTxcL3N1Yj4gKyBUPHN1Yj4yPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT42ID0gVDxzdWI+MjxcL3N1Yj4gKyBUPHN1Yj4yPFwvc3ViPiBvciA2ID0gVDxzdWI+MzxcL3N1Yj48XC9saT5cclxuXHQ8bGk+MTAgPSBUPHN1Yj4xPFwvc3ViPiArIFQ8c3ViPjI8XC9zdWI+ICsgVDxzdWI+MzxcL3N1Yj4gb3IgMTAgPSBUPHN1Yj40PFwvc3ViPjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoaXMgcmVzdWx0IGlzIGtub3duIGFzIHRoZSBFdXJla2EgdGhlb3JlbSBzaW5jZSBoZSB3cm90ZSBpbiBoaXMgZGlhcnkgJmxkcXVvO0V1cmVrYSEgbnVtID0gJkRlbHRhOyArICZEZWx0YTsgKyAmRGVsdGE7JnJkcXVvOyBmb3IgY29tbWVtb3JhdGluZyB0aGUgcHJvb2YuIFdlIHdvbmRlciBpZiBzb21lIHBvc2l0aXZlIGludGVnZXIgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgc3VtIG9mIGV4YWN0bHkgdGhyZWUgdHJpYW5nbGUgbnVtYmVycy4gQXMgc2hvd24gaW4gdGhlIGFib3ZlIGV4YW1wbGVzLCBpbnRlZ2VycyA1IGFuZCAxMCBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSB0cmlhbmdsZSBudW1iZXJzLCBidXQgaW50ZWdlcnMgNCBhbmQgNiBjYW5ub3QuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciwgd3JpdGUgYSBwcm9ncmFtIHRvIHRlc3Qgd2hldGhlciBvciBub3QgdGhlIGludGVnZXIgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgc3VtIG9mIGV4YWN0bHkgdGhyZWUgdHJpYW5nbGUgbnVtYmVycyB0aGF0IG1heSBub3QgYmUgZGlzdGluY3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgbGluZSBjb250YWluaW5nIGEgcG9zaXRpdmUgaW50ZWdlciBLICgzICZsZTsgSyAmbGU7IDEsMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gUHJpbnQgMSBpZiB0aGUgaW5wdXQgbnVtYmVyIEsgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgc3VtIG9mIGV4YWN0bHkgdGhyZWUgdHJpYW5nbGUgbnVtYmVycywgYW5kIHByaW50IDAgKHplcm8pLCBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2014 C번