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

문제

p는 2보다 큰 정수이다. 다음과 같은 규칙으로 무한 이진 트리의 각 노드에 정수인 숫자가 매겨진다.

  • 루트 노드에는 1을 매긴다.
  • 노드에 x가 매겨져 있다면 해당 노드의 왼쪽 자식 노드에는 p * x, 오른쪽 자식 노드에는 p * x + 1이 매겨진다.

예를 들어 p = 3 일때 트리의 시작 부분은 다음과 같을 것이다.

어떤 숫자는 무한 이진 트리 내의 서로 다른 두 노드에 매겨진 두 숫자의 합으로 표현 할 수 있는 방법이 한 가지면 "예쁜 숫자"로 분류된다. 주어진 p로 만든 무한 이진 트리 내에서  n1, n2, n3, n4가 "예쁜"지 출력하는 프로그램을 작성하라.

입력

한 줄에 정수 p, n1, n2, n3, n4가 차례로 주어진다. (2 < p < 50, 0 < n1 < 1018, 0 < n2 < 1018, 0 < n3 < 1018, 0 < n4 < 1018)

출력

한 줄에 차례로 n1, n2, n3, n4가 예쁘면 1을, 아니면 0을 출력한다.

예제 입력 1

3 7 28 13 9

예제 출력 1

1 1 0 0
W3sicHJvYmxlbV9pZCI6IjMxNTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MDhcdWMwNWMgXHVjMjJiXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5wXHViMjk0IDJcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3M2NcdWI4NWMmbmJzcDtcdWJiMzRcdWQ1NWMgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc1OCZuYnNwO1x1YWMwMSBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHVjODE1XHVjMjE4XHVjNzc4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViOGU4XHVkMmI4IFx1YjE3OFx1YjRkY1x1YzVkMFx1YjI5NCAxXHVjNzQ0IFx1YjllNFx1YWUzNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMTc4XHViNGRjXHVjNWQwIHhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWQ1NzRcdWIyZjkgXHViMTc4XHViNGRjXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHVjNWQwXHViMjk0IHAgKiZuYnNwO3gsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHVjNWQwXHViMjk0IHAgKiZuYnNwO3gmbmJzcDsrJm5ic3A7MVx1Yzc3NCBcdWI5ZTRcdWFjYThcdWM5YzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBwID0gMyBcdWM3N2NcdWI1NGMgXHVkMmI4XHViOWFjXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWJkODBcdWJkODRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91c2VydXBsb2FkXC9pbnN1X255bVwvMjAxNjAxMjFcLzIwYWMxYTUzMmFlYzk1MGM2MzlkY2M3MGE3YTYzNjZlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMwNXB4OyB3aWR0aDo1ODdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmIzNFx1ZDU1YyBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjIFx1YjBiNFx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHViOWU0XHVhY2E4XHVjOWM0IFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNCBcdWQ1NjAmbmJzcDtcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWQ1NWMmbmJzcDtcdWFjMDBcdWM5YzBcdWJhNzQmbmJzcDsmcXVvdDtcdWM2MDhcdWMwNWMgXHVjMjJiXHVjNzkwJnF1b3Q7XHViODVjIFx1YmQ4NFx1Yjk1OFx1YjQxY1x1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWM0IHBcdWI4NWMgXHViOWNjXHViNGUwJm5ic3A7XHViYjM0XHVkNTVjIFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWMgXHViMGI0XHVjNWQwXHVjMTFjJm5ic3A7IG48c3ViPjE8XC9zdWI+LCBuPHN1Yj4yPFwvc3ViPiwgbjxzdWI+MzxcL3N1Yj4sJm5ic3A7bjxzdWI+NDxcL3N1Yj5cdWFjMDAgJnF1b3Q7XHVjNjA4XHVjMDVjJnF1b3Q7XHVjOWMwJm5ic3A7XHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCZuYnNwO3AsJm5ic3A7bjxzdWI+MTxcL3N1Yj4sIG48c3ViPjI8XC9zdWI+LCBuPHN1Yj4zPFwvc3ViPiwmbmJzcDtuPHN1Yj40PFwvc3ViPlx1YWMwMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbHQ7IHAgJmx0OyA1MCwgMCAmbHQ7IG48c3ViPjE8XC9zdWI+Jm5ic3A7Jmx0OyAxMDxzdXA+MTg8XC9zdXA+LCAwICZsdDsgbjxzdWI+MjxcL3N1Yj4mbmJzcDsmbHQ7IDEwPHN1cD4xODxcL3N1cD4sIDAgJmx0OyBuPHN1Yj4zPFwvc3ViPiZuYnNwOyZsdDsgMTA8c3VwPjE4PFwvc3VwPiwgMCAmbHQ7IG48c3ViPjQ8XC9zdWI+Jm5ic3A7Jmx0OyAxMDxzdXA+MTg8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjYzI4XHViODQwXHViODVjIG48c3ViPjE8XC9zdWI+LCBuPHN1Yj4yPFwvc3ViPiwgbjxzdWI+MzxcL3N1Yj4sIG48c3ViPjQ8XC9zdWI+XHVhYzAwIFx1YzYwOFx1YzA1OFx1YmE3NCAxXHVjNzQ0LCBcdWM1NDRcdWIyYzhcdWJhNzQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE1MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpbmFyeSBUcmVlIiwiZGVzY3JpcHRpb24iOiI8cD5MZXQgcCBiZSBhbiBpbnRlZ2VyLCBiaWdnZXIgdGhhbiAyLiBJbnRlZ2VycyBhcmUgd3JpdHRlbiBpbiB0aGUgdmVydGljZXMgb2YgdGhlIGluZmluaXR5IGJpbmFyeSB0cmVlIGluIHRoZSBmb2xsb3dpbmcgd2F5OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmluIHRoZSByb290IG9mIHRoZSB0cmVlIGl0IGlzIHdyaXR0ZW4gMTs8XC9saT5cclxuXHQ8bGk+aWYgaW4gYW55IHZlcnRleCBvZiB0aGUgdHJlZSBpdCBpcyB3cml0dGVuIHggLCB0aGVyZWZvcmUgaXRzIGxlZnQgY2hpbGQgY29udGFpbnMgcCZuYnNwOyZ0aW1lczsmbmJzcDt4LiBhbmQgaXRzIHJpZ2h0IGNoaWxkIGNvbnRhaW5zIHAgJnRpbWVzOyZuYnNwO3ggKyAxLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiBwID0gMywgdGhlbiB0aGUgYmVnaW5uaW5nIG9mIHRoZSB0cmVlIGxvb2tzIGluIHRoZSBmb2xsb3dpbmcgd2F5OjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8zMTUyXC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMwNXB4OyB3aWR0aDo1ODdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BIG51bWJlciBpcyBjYWxsZWQgcHJldHR5IGlmIGl0IGNhbiBiZSBwcmVzZW50ZWQgaW4gYSBzaW5nbGUgd2F5IGFzIGEgc3VtIG9mIHR3byBkaWZmZXJlbnQgbnVtYmVycywgd2hpY2ggYXBwZWFyIGluIHRoZSB0cmVlIHZlcnRpY2VzLiBXcml0ZSBhIHByb2dyYW0gYnRyZWUsIHdoaWNoIGRldGVybWluZXMgd2hldGhlciB0aGUgZ2l2ZW4gbnVtYmVycyBuPHN1Yj4xPFwvc3ViPiwgbjxzdWI+MjxcL3N1Yj4sIG48c3ViPjM8XC9zdWI+IGFuZCBuPHN1Yj40PFwvc3ViPiBhcmUgcHJldHR5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gYSBzaW5nbGUgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlIGludGVnZXJzIHAsIG48c3ViPjE8XC9zdWI+LCBuPHN1Yj4yPFwvc3ViPiwgbjxzdWI+MzxcL3N1Yj4gYW5kIG48c3ViPjQ8XC9zdWI+IGFyZSBnaXZlbiAoMiAmbHQ7IHAgJmx0OyA1MCwgMCAmbHQ7IG48c3ViPjE8XC9zdWI+ICZsdDsgMTA8c3VwPjE4PFwvc3VwPiwgMCAmbHQ7IG48c3ViPjI8XC9zdWI+ICZsdDsgMTA8c3VwPjE4PFwvc3VwPiwgMCAmbHQ7IG48c3ViPjM8XC9zdWI+ICZsdDsgMTA8c3VwPjE4PFwvc3VwPiwgMCAmbHQ7IG48c3ViPjQ8XC9zdWI+ICZsdDsgMTA8c3VwPjE4PFwvc3VwPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gYSBzaW5nbGUgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IGZvciBldmVyeSBudW1iZXIgbjxzdWI+MTxcL3N1Yj4sIG48c3ViPjI8XC9zdWI+LCBuPHN1Yj4zPFwvc3ViPiBhbmQgbjxzdWI+NDxcL3N1Yj4gdGhlIHByb2dyYW0gbXVzdCB3cml0ZSAxIGlmIHRoZSBudW1iZXIgaXMgcHJldHR5IGFuZCAwIGlmIGl0IGlzIG5vdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Tournament in Informatics > Shumen 2011 B1번

  • 문제를 번역한 사람: insu_nym
  • 잘못된 번역을 찾은 사람: junie