시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 278 209 200 80.645%

문제

네 개의 양의 정수 a, b, c, d가 있을 때, 아래와 같이 차이를 계산할 수 있다.

|a-b| |b-c| |c-d| |d-a|

이렇게 나온 네 개의 수를 이용해서 다시 또 차이를 계산할 수 있다. 이 작업을 모든 네 개의 정수가 같아질 때까지 반복한다.

예를 들어, 1, 3, 5, 9로 시작했을 때를 생각해보자.

1 3 5 9

2 2 4 8 (1)

0 2 4 6 (2)

2 2 2 6 (3)

0 0 4 4 (4)

0 4 0 4 (5)

4 4 4 4 (6)

위의 경우에서 수열은 6번 만에 수렴한다. a, b, c, d가 주어졌을 때, 이 수열이 얼마나 빨리 수렴하는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, a, b, c, d가 순서대로 주어진다. 입력의 마지막 줄에는 0이 4개 주어진다. (1 ≤ a,b,c,d ≤ 2,000,000,000)

출력

각 테스트 케이스에 대해서, 수열이 몇 번 만에 수렴하는지 출력한다.

예제 입력 1

1 3 5 9
4 3 2 1
1 1 1 1
0 0 0 0

예제 출력 1

6
4
0

힌트

만약 네 정수가 2n보다 작다면, 3*n번 이내에 수렴한다.

W3sicHJvYmxlbV9pZCI6IjQwODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJWaXZhIGxhIERpZmVyZW5jaWEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjEyNCBcdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiLCBjLCBkXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjYzI4XHVjNzc0XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD58YS1ifCB8Yi1jfCB8Yy1kfCB8ZC1hfDxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHViMDk4XHVjNjI4IFx1YjEyNCBcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWIyZTRcdWMyZGMgXHViNjEwIFx1Y2MyOFx1Yzc3NFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWJhYThcdWI0ZTAgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhYzE5XHVjNTQ0XHVjOWM4IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDEsIDMsIDUsIDlcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTg4XHVjNzQ0IFx1YjU0Y1x1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPjEgMyA1IDk8XC9wPlxyXG5cclxuPHA+MiAyIDQgOCA8c3Ryb25nPigxKTxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+MCAyIDQgNiA8c3Ryb25nPigyKTxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+MiAyIDIgNiA8c3Ryb25nPigzKTxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+MCAwIDQgNCA8c3Ryb25nPig0KTxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+MCA0IDAgNCA8c3Ryb25nPig1KTxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+NCA0IDQgNCA8c3Ryb25nPig2KTxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YzExYyBcdWMyMThcdWM1ZjRcdWM3NDAgNlx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVjMjE4XHViODM0XHVkNTVjXHViMmU0LiBhLCBiLCBjLCBkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWJjXHViOWM4XHViMDk4IFx1YmU2OFx1YjlhYyBcdWMyMThcdWI4MzRcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgYSwgYiwgYywgZFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IDRcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGEsYixjLGQgJmxlOyAyLDAwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YmE4NyBcdWJjODggXHViOWNjXHVjNWQwIFx1YzIxOFx1YjgzNFx1ZDU1OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjljY1x1YzU3ZCBcdWIxMjQgXHVjODE1XHVjMjE4XHVhYzAwIDI8c3VwPm48XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNFx1YmE3NCwgMypuXHViYzg4IFx1Yzc3NFx1YjBiNFx1YzVkMCBcdWMyMThcdWI4MzRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpZnJhbWUgZnJhbWVib3JkZXI9XCIwXCIgaGVpZ2h0PVwiNDgwXCIgc3JjPVwiaHR0cDpcL1wvd3d3LnlvdXR1YmUuY29tXC9lbWJlZFwvZHZnWmttMXhXUEVcIiB3aWR0aD1cIjg1M1wiPjxcL2lmcmFtZT48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQwODQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWaXZlIGxhIERpZmZlcmVuY2UhIiwiZGVzY3JpcHRpb24iOiI8cD5UYWtlIGFueSBmb3VyIHBvc2l0aXZlIGludGVnZXJzOiBhLCBiLCBjLCBkLiBGb3JtIGZvdXIgbW9yZSwgbGlrZSB0aGlzOiZuYnNwOzxcL3A+XHJcblxyXG48cD58YS1ifCB8Yi1jfCB8Yy1kfCB8ZC1hfDxcL3A+XHJcblxyXG48cD5UaGF0IGlzLCB0YWtlIHRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiB0aGUgZGlmZmVyZW5jZXMgb2YgYSB3aXRoIGIsIGIgd2l0aCBjLCBjIHdpdGggZCwgYW5kIGQgd2l0aCBhLiAoTm90ZSB0aGF0IGEgemVybyBjb3VsZCBjcm9wIHVwLCBidXQgdGhleSZyc3F1bztsbCBhbGwgc3RpbGwgYmUgbm9uLW5lZ2F0aXZlLikgVGhlbiwgZG8gaXQgYWdhaW4gd2l0aCB0aGVzZSBmb3VyIG5ldyBudW1iZXJzLiBBbmQgdGhlbiBhZ2Fpbi4gQW5kIGFnYWluLiBFdmVudHVhbGx5LCBhbGwgZm91ciBpbnRlZ2VycyB3aWxsIGJlIHRoZSBzYW1lLiBGb3IgZXhhbXBsZSwgc3RhcnQgd2l0aCAxLDMsNSw5OjxcL3A+XHJcblxyXG48cD4xIDMgNSA5Jm5ic3A7PGJyIFwvPlxyXG4yIDIgNCA4ICgxKTxiciBcLz5cclxuMCAyIDQgNiAoMik8YnIgXC8+XHJcbjIgMiAyIDYgKDMpPGJyIFwvPlxyXG4wIDAgNCA0ICg0KTxiciBcLz5cclxuMCA0IDAgNCAoNSk8YnIgXC8+XHJcbjQgNCA0IDQgKDYpPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgY2FzZSwgdGhlIHNlcXVlbmNlIGNvbnZlcmdlZCBpbiA2IHN0ZXBzLiBJdCB0dXJucyBvdXQgdGhhdCBpbiBhbGwgY2FzZXMsIHRoZXNlcXVlbmNlIGNvbnZlcmdlcyB2ZXJ5IHF1aWNrbHkuIEluIGZhY3QsIGl0IGNhbiBiZSBzaG93biB0aGF0IGlmIGFsbCBmb3VyIGludGVnZXJzIGFyZSBsZXNzIHRoYW4gMm4sIHRoZW4gaXQgd2lsbCB0YWtlIG5vIG1vcmUgdGhhbiAzKm4gc3RlcHMgdG8gY29udmVyZ2UhPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEsIGIsIGMgYW5kIGQsIGZpZ3VyZSBvdXQganVzdCBob3cgcXVpY2tseSB0aGUgc2VxdWVuY2UgY29udmVyZ2VzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBmb3VyIHBvc2l0aXZlIGludGVnZXJzIG9uIGEgc2luZ2xlIGxpbmUgKDEgJmxlOyBhLGIsYyxkICZsZTsgMiwwMDAsMDAwLDAwMCksIHdpdGggc2luZ2xlIHNwYWNlcyBmb3Igc2VwYXJhdGlvbi4gVGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggZm91ciAwcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIG9uIGl0cyBvd24gbGluZSwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHN0ZXBzIHVudGlsIGNvbnZlcmdlbmNlLiBPdXRwdXQgbm8gZXh0cmEgc3BhY2VzLCBhbmQgZG8gbm90IHNlcGFyYXRlIGFuc3dlcnMgd2l0aCBibGFuayBsaW5lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > North America > Southeast USA Regional > 2011 Southeast USA Regional Programming Contest D번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kgj291