시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 660 138 71 19.777%

문제

양의 정수로 이루어진 길이가 n인 수열이 있다. 소수 부분 수열이란 길이가 적어도 2이면서, 합이 2보다 크거나 같은 소수가 되는 연속 부분 수열이다.

예를 들어, 수열이 [3, 5, 6, 3, 8] 일 때, 길이가 2인 소수 부분 수열이 두 개(5 + 6 = 11, 3 + 8 = 11)이 있고, 길이가 3인 소수 부분 수열은 1개 (6 + 3 + 8 = 17), 길이가 4인 소수 부분 수열은 1개 (3 + 5 + 6 + 3 = 17) 가 있다.

수열이 주어졌을 때, 길이가 가장 짧은 소수 부분 수열을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 t (1 ≤ t ≤ 20) 가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 줄의 첫 번째 정수 n은 (0 < n ≤ 10000) 수열의 길이이다. 다음에 주어지는 정수 n개는 수열의 원소이다. 수열의 원소는 10000보다 작거나 같은 음이 아닌 정수이다.

출력

각 테스트 케이스마다 가장 짧은 소수 부분 수열의 길이가 x라면 "Shortest primed subsequence is length x:"를 출력하고, 그 수열 공백으로 구분해 출력한다. 가장 짧은 소수 부분 수열이 여러 가지면, 먼저 나오는 것을 출력한다.

소수 부분 수열이 없는 경우에는 "This sequence is anti-primed."를 출력한다.

예제 입력 1

3
5 3 5 6 3 8
5 6 4 5 4 12
21 15 17 16 32 28 22 26 30 34 29 31 20 24 18 33 35 25 27 23 19 21

예제 출력 1

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.
W3sicHJvYmxlbV9pZCI6IjY4ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0XHVhYzAwIG5cdWM3NzggXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3ODAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCAyXHVjNzc0XHViYTc0XHVjMTFjLCBcdWQ1NjlcdWM3NzQgMlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWI0MThcdWIyOTQgXHVjNWYwXHVjMThkIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzIxOFx1YzVmNFx1Yzc3NCBbMywgNSwgNiwgMywgOF0gXHVjNzdjIFx1YjU0YywgXHVhZTM4XHVjNzc0XHVhYzAwIDJcdWM3NzggXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHViNDUwIFx1YWMxYyg1ICsgNiA9IDExLCAzICsgOCA9IDExKVx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YWMwMCAzXHVjNzc4IFx1YzE4Y1x1YzIxOCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQwIDFcdWFjMWMgKDYgKyAzICsgOCA9IDE3KSwgXHVhZTM4XHVjNzc0XHVhYzAwIDRcdWM3NzggXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDAgMVx1YWMxYyAoMyArIDUgKyA2ICsgMyA9IDE3KSBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCB0ICgxICZsZTsgdCAmbGU7IDIwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzkwNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOCBuXHVjNzQwICgwICZsdDsgbiAmbGU7IDEwMDAwKSBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzgxNVx1YzIxOCBuXHVhYzFjXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM3NzRcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWIyOTQgMTAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YzE4Y1x1YzIxOCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCB4XHViNzdjXHViYTc0ICZxdW90O1Nob3J0ZXN0IHByaW1lZCBzdWJzZXF1ZW5jZSBpcyBsZW5ndGggeDomcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWFkZjggXHVjMjE4XHVjNWY0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YzE4Y1x1YzIxOCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWJhNzQsIFx1YmEzY1x1YzgwMCBcdWIwOThcdWM2MjRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtUaGlzIHNlcXVlbmNlIGlzIGFudGktcHJpbWVkLiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjg4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlByaW1lZCBTZXF1ZW5jZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgc2VxdWVuY2Ugb2YgcG9zaXRpdmUgaW50ZWdlcnMgb2YgbGVuZ3RoIG4sIHdlIGRlZmluZSBhIHByaW1lZCBzdWJzZXF1ZW5jZSBhcyBhIGNvbnNlY3V0aXZlIHN1YnNlcXVlbmNlIG9mIGxlbmd0aCBhdCBsZWFzdCB0d28gdGhhdCBzdW1zIHRvIGEgcHJpbWUgbnVtYmVyIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byB0d28uPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBnaXZlbiB0aGUgc2VxdWVuY2U6PFwvcD5cclxuXHJcbjxwPjMgNSA2IDMgODxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgdHdvIHByaW1lZCBzdWJzZXF1ZW5jZXMgb2YgbGVuZ3RoIDIgKDUgKyA2ID0gMTEgYW5kIDMgKyA4ID0gMTEpLCBvbmUgcHJpbWVkIHN1YnNlcXVlbmNlIG9mIGxlbmd0aCAzICg2ICsgMyArIDggPSAxNyksIGFuZCBvbmUgcHJpbWVkIHN1YnNlcXVlbmNlIG9mIGxlbmd0aCA0ICgzICsgNSArIDYgKyAzID0gMTcpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29uc2lzdHMgb2YgYSBzZXJpZXMgb2YgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgY29uc2lzdHMgb2YgYW4gaW50ZWdlciB0ICgxICZsZTsgdCAmbGU7IDIwKSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBvbmUgbGluZS4gVGhlIGxpbmUgYmVnaW5zIHdpdGggdGhlIGludGVnZXIgbiwgMCAmbHQ7IG4gJmxlOyAxMDAwMCwgZm9sbG93ZWQgYnkgbiBub24tbmVnYXRpdmUgbnVtYmVycyBsZXNzIHRoYW4mbmJzcDtvciBlcXVhbCB0byAxMDAwMCBjb21wcmlzaW5nIHRoZSBzZXF1ZW5jZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBzZXF1ZW5jZSwgcHJpbnQgdGhlICZxdW90O1Nob3J0ZXN0IHByaW1lZCBzdWJzZXF1ZW5jZSBpcyBsZW5ndGggeDomcXVvdDssIHdoZXJlIHggaXMgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgcHJpbWVkIHN1YnNlcXVlbmNlLCBmb2xsb3dlZCBieSB0aGUgc2hvcnRlc3QgcHJpbWVkIHN1YnNlcXVlbmNlLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgc3VjaCBzZXF1ZW5jZXMsIHByaW50IHRoZSBvbmUgdGhhdCBvY2N1cnMgZmlyc3QuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBubyBzdWNoIHNlcXVlbmNlcywgcHJpbnQgJnF1b3Q7VGhpcyBzZXF1ZW5jZSBpcyBhbnRpLXByaW1lZC4mcXVvdDsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Canadian Computing Competition & Olympiad > 2005 > CCO 2005 4번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: slah007