시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 4017 2390 1819 58.829%

문제

삼각수 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+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Yzc5MFx1YzVmMFx1YzIxOCBLICgzICZsZTsgSyAmbGU7IDEsMDAwKVx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFRcdWFjMWNcdWM3NTggXHViNzdjXHVjNzc4XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHVkNDVjXHVjOTAwXHVjZDljXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YjMwMFx1ZDU3NCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVkNTVjIFx1Yjc3Y1x1Yzc3OFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBLXHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCAzXHVhYzFjXHVjNzU4IFx1YzBiY1x1YWMwMVx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDIwXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCAxXHVjNzQ0LCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNDQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXVyZWthIFRoZW9yZW0iLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHJpYW5nbGUgbnVtYmVyIFQ8c3ViPm48XC9zdWI+KG4gJmdlOyAxKSBpcyBhIGZpZ3VyYXRlIG51bWJlciB0aGF0IGNhbiBiZSByZXByZXNlbnRlZCBieSBhIHJlZ3VsYXIgZ2VvbWV0cmljIGFycmFuZ2VtZW50IG9mIGVxdWFsbHkgc3BhY2VkIHBvaW50cyBhcyBpbGx1c3RyYXRlZCBpbiBGaWd1cmUgMS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZXVyZWthLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExOXB4OyB3aWR0aDo0MTZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS48XC9wPlxyXG5cclxuPHA+VGhlIHRyaWFuZ2xlIG51bWJlciBUPHN1Yj5uPFwvc3ViPiBmb3IgYW55IHBvc2l0aXZlIGludGVnZXIgbiAmZ2U7IDEgaXMgZ2l2ZW4gYnkgdGhlIGV4cGxpY2l0IGZvcm11bGE6PFwvcD5cclxuXHJcbjxwPlQ8c3ViPm48XC9zdWI+ID0gMSArIDIgKyAzICsgLi4uICsgbiA9IG4obisxKVwvMjxcL3A+XHJcblxyXG48cD5JbiAxNzk2LCBHYXVzcyBwcm92ZWQgdGhhdCBldmVyeSBwb3NpdGl2ZSBpbnRlZ2VyIGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIHN1bSBvZiBhdCBtb3N0IHRocmVlIHRyaWFuZ2xlIG51bWJlcnMuIEZvciBleGFtcGxlcyw8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT40ID0gVDxzdWI+MTxcL3N1Yj4gKyBUPHN1Yj4yPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT41ID0gVDxzdWI+MTxcL3N1Yj4gKyBUPHN1Yj4xPFwvc3ViPiArIFQ8c3ViPjI8XC9zdWI+PFwvbGk+XHJcblx0PGxpPjYgPSBUPHN1Yj4yPFwvc3ViPiArIFQ8c3ViPjI8XC9zdWI+IG9yIDYgPSBUPHN1Yj4zPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT4xMCA9IFQ8c3ViPjE8XC9zdWI+ICsgVDxzdWI+MjxcL3N1Yj4gKyBUPHN1Yj4zPFwvc3ViPiBvciAxMCA9IFQ8c3ViPjQ8XC9zdWI+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhpcyByZXN1bHQgaXMga25vd24gYXMgdGhlIEV1cmVrYSB0aGVvcmVtIHNpbmNlIGhlIHdyb3RlIGluIGhpcyBkaWFyeSAmbGRxdW87RXVyZWthISBudW0gPSAmRGVsdGE7ICsgJkRlbHRhOyArICZEZWx0YTsmcmRxdW87IGZvciBjb21tZW1vcmF0aW5nIHRoZSBwcm9vZi4gV2Ugd29uZGVyIGlmIHNvbWUgcG9zaXRpdmUgaW50ZWdlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSB0cmlhbmdsZSBudW1iZXJzLiBBcyBzaG93biBpbiB0aGUgYWJvdmUgZXhhbXBsZXMsIGludGVnZXJzIDUgYW5kIDEwIGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIHN1bSBvZiBleGFjdGx5IHRocmVlIHRyaWFuZ2xlIG51bWJlcnMsIGJ1dCBpbnRlZ2VycyA0IGFuZCA2IGNhbm5vdC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBwb3NpdGl2ZSBpbnRlZ2VyLCB3cml0ZSBhIHByb2dyYW0gdG8gdGVzdCB3aGV0aGVyIG9yIG5vdCB0aGUgaW50ZWdlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSB0cmlhbmdsZSBudW1iZXJzIHRoYXQgbWF5IG5vdCBiZSBkaXN0aW5jdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgYSBwb3NpdGl2ZSBpbnRlZ2VyIEsgKDMgJmxlOyBLICZsZTsgMSwwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBQcmludCAxIGlmIHRoZSBpbnB1dCBudW1iZXIgSyBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSB0cmlhbmdsZSBudW1iZXJzLCBhbmQgcHJpbnQgMCAoemVybyksIG90aGVyd2lzZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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