시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3491 2085 1588 58.837%

문제

삼각수 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+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPltcdWFkZjhcdWI5YmNdPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzVmMFx1YzIxOCBuXHVjNWQwIFx1YjMwMFx1ZDU3NCBuICZnZTsgMVx1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThUPHN1Yj5uPFwvc3ViPlx1YjI5NCBcdWJhODVcdWJjMzFcdWQ1NWMgXHVhY2Y1XHVjMmRkXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+VDxzdWI+bjxcL3N1Yj4gPSAxICsgMiArIDMgKyAuLi4gKyBuID0gbihuKzEpXC8yPFwvcD5cclxuXHJcbjxwPjE3OTZcdWIxNDQsIFx1YWMwMFx1YzZiMFx1YzJhNFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YjMwMCAzXHVhYzFjXHVjNzU4IFx1YzBiY1x1YWMwMVx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVjOTlkXHViYTg1XHVkNTU4XHVjNjAwXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjQgPSBUPHN1Yj4xPFwvc3ViPiArIFQ8c3ViPjI8XC9zdWI+PFwvbGk+XHJcblx0PGxpPjUgPSBUPHN1Yj4xPFwvc3ViPiArIFQ8c3ViPjE8XC9zdWI+ICsgVDxzdWI+MjxcL3N1Yj48XC9saT5cclxuXHQ8bGk+NiA9IFQ8c3ViPjI8XC9zdWI+ICsgVDxzdWI+MjxcL3N1Yj4gb3IgNiA9IFQ8c3ViPjM8XC9zdWI+PFwvbGk+XHJcblx0PGxpPjEwID0gVDxzdWI+MTxcL3N1Yj4gKyBUPHN1Yj4yPFwvc3ViPiArIFQ8c3ViPjM8XC9zdWI+IG9yIDEwID0gVDxzdWI+NDxcL3N1Yj48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzQgXHVhY2IwXHVhY2ZjXHViMjk0IFx1Yzk5ZFx1YmE4NVx1Yzc0NCBcdWFlMzBcdWIxNTBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWRmOFx1Yzc1OCBcdWIyZTRcdWM3NzRcdWM1YjRcdWI5YWNcdWM1ZDAgJmxkcXVvO0V1cmVrYSEgbnVtID0gJkRlbHRhOyArICZEZWx0YTsgKyAmRGVsdGE7JnJkcXVvOyBcdWI3N2NcdWFjZTAgXHVjODAxXHVjNzQwXHVhYzgzXHVjNWQwXHVjMTFjIFx1YzcyMFx1YjgwOFx1Y2U3NCBcdWM3NzRcdWI4NjBcdWM3M2NcdWI4NWMgXHVjNTRjXHViODI0XHVjODRjXHViMmU0LiBcdWFmY2RcdWM3NDAgXHViYTg3XHViYTg3IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggM1x1YWMxY1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzJkY1x1YzVkMFx1YzExYywgNVx1YzY0MCAxMFx1Yzc0MCBcdWM4MTVcdWQ2NTVcdWQ3ODggM1x1YWMxY1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjIDRcdWM2NDAgNlx1Yzc0MCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggM1x1YWMxY1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMFx1Yjk3YyBcdWQzMTBcdWIyZThcdWQ1NzRcdWM4ZmNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNFx1Yjc3Yy4gXHViMmU4LCAzXHVhYzFjXHVjNzU4IFx1YzBiY1x1YWMwMVx1YzIxOFx1YWMwMCBcdWJhYThcdWI0NTAgXHViMmVjXHViNzdjXHVjNTdjIFx1ZDU2MCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YmM4OFx1YzlmOFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM3OTBcdWM1ZjBcdWMyMTggSyAoMyAmbGU7IEsgJmxlOyAxLDAwMClcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBUXHVhYzFjXHVjNzU4IFx1Yjc3Y1x1Yzc3OFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWIzMDBcdWQ1NzQgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWI3N2NcdWM3NzhcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgS1x1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggM1x1YWMxY1x1Yzc1OCBcdWMwYmNcdWFjMDFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQgMVx1Yzc0NCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQ0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV1cmVrYSBUaGVvcmVtIiwiZGVzY3JpcHRpb24iOiI8cD5BIHRyaWFuZ2xlIG51bWJlciBUPHN1Yj5uPFwvc3ViPihuICZnZTsgMSkgaXMgYSBmaWd1cmF0ZSBudW1iZXIgdGhhdCBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSByZWd1bGFyIGdlb21ldHJpYyBhcnJhbmdlbWVudCBvZiBlcXVhbGx5IHNwYWNlZCBwb2ludHMgYXMgaWxsdXN0cmF0ZWQgaW4gRmlndXJlIDEuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2V1cmVrYS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTlweDsgd2lkdGg6NDE2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEuPFwvcD5cclxuXHJcbjxwPlRoZSB0cmlhbmdsZSBudW1iZXIgVDxzdWI+bjxcL3N1Yj4gZm9yIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIG4gJmdlOyAxIGlzIGdpdmVuIGJ5IHRoZSBleHBsaWNpdCBmb3JtdWxhOjxcL3A+XHJcblxyXG48cD5UPHN1Yj5uPFwvc3ViPiA9IDEgKyAyICsgMyArIC4uLiArIG4gPSBuKG4rMSlcLzI8XC9wPlxyXG5cclxuPHA+SW4gMTc5NiwgR2F1c3MgcHJvdmVkIHRoYXQgZXZlcnkgcG9zaXRpdmUgaW50ZWdlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgYXQgbW9zdCB0aHJlZSB0cmlhbmdsZSBudW1iZXJzLiBGb3IgZXhhbXBsZXMsPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+NCA9IFQ8c3ViPjE8XC9zdWI+ICsgVDxzdWI+MjxcL3N1Yj48XC9saT5cclxuXHQ8bGk+NSA9IFQ8c3ViPjE8XC9zdWI+ICsgVDxzdWI+MTxcL3N1Yj4gKyBUPHN1Yj4yPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT42ID0gVDxzdWI+MjxcL3N1Yj4gKyBUPHN1Yj4yPFwvc3ViPiBvciA2ID0gVDxzdWI+MzxcL3N1Yj48XC9saT5cclxuXHQ8bGk+MTAgPSBUPHN1Yj4xPFwvc3ViPiArIFQ8c3ViPjI8XC9zdWI+ICsgVDxzdWI+MzxcL3N1Yj4gb3IgMTAgPSBUPHN1Yj40PFwvc3ViPjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoaXMgcmVzdWx0IGlzIGtub3duIGFzIHRoZSBFdXJla2EgdGhlb3JlbSBzaW5jZSBoZSB3cm90ZSBpbiBoaXMgZGlhcnkgJmxkcXVvO0V1cmVrYSEgbnVtID0gJkRlbHRhOyArICZEZWx0YTsgKyAmRGVsdGE7JnJkcXVvOyBmb3IgY29tbWVtb3JhdGluZyB0aGUgcHJvb2YuIFdlIHdvbmRlciBpZiBzb21lIHBvc2l0aXZlIGludGVnZXIgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgc3VtIG9mIGV4YWN0bHkgdGhyZWUgdHJpYW5nbGUgbnVtYmVycy4gQXMgc2hvd24gaW4gdGhlIGFib3ZlIGV4YW1wbGVzLCBpbnRlZ2VycyA1IGFuZCAxMCBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSB0cmlhbmdsZSBudW1iZXJzLCBidXQgaW50ZWdlcnMgNCBhbmQgNiBjYW5ub3QuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciwgd3JpdGUgYSBwcm9ncmFtIHRvIHRlc3Qgd2hldGhlciBvciBub3QgdGhlIGludGVnZXIgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgc3VtIG9mIGV4YWN0bHkgdGhyZWUgdHJpYW5nbGUgbnVtYmVycyB0aGF0IG1heSBub3QgYmUgZGlzdGluY3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgbGluZSBjb250YWluaW5nIGEgcG9zaXRpdmUgaW50ZWdlciBLICgzICZsZTsgSyAmbGU7IDEsMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gUHJpbnQgMSBpZiB0aGUgaW5wdXQgbnVtYmVyIEsgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgc3VtIG9mIGV4YWN0bHkgdGhyZWUgdHJpYW5nbGUgbnVtYmVycywgYW5kIHByaW50IDAgKHplcm8pLCBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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