CCO '05 P4 - Primed Sequences - DMOJ: Modern Online Judge

CCO '05 P4 - Primed Sequences

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 4.0s

Memory limit: 16M

Problem type

Canadian Computing Competition: 2005 Stage 2, Day 2, Problem 1

Given a sequence of positive integers of length $n$ ~n~, we define a primed subsequence as a consecutive subsequence of length at least two that sums to a prime number greater than or equal to two.

For example, given the sequence:

3 5 6 3 8

There are two primed subsequences of length $2$ ~2~ ( $5 + 6 = 11$ ~5 + 6 = 11~ and $3 + 8 = 11$ ~3 + 8 = 11~), one primed subsequence of length $3$ ~3~ ( $6 + 3 + 8 = 17$ ~6 + 3 + 8 = 17~), and one primed subsequence of length $4$ ~4~ ( $3 + 5 + 6 + 3 = 17$ ~3 + 5 + 6 + 3 = 17~).

Input Specification

Input consists of a series of test cases. The first line consists of an integer $t$ ~t~ $(1 \le t \le 20)$ ~(1 \le t \le 20)~, the number of test cases.

Each test case consists of one line. The line begins with the integer $n$ ~n~, $0 < n \le 10\,000$ ~0 < n \le 10\,000~, followed by $n$ ~n~ positive numbers less than or equal to $10\,000$ ~10\,000~ comprising the sequence.

You should note that in test cases worth $80\%$ ~80\%~ of the points, there will be at most $1\,000$ ~1\,000~ numbers in the sequence.

Output Specification

For each sequence, print Shortest primed subsequence is length x:, where $x$ ~x~ is the length of the shortest primed subsequence, followed by the shortest primed subsequence, separated by spaces. If there are multiple such sequences, print the one that occurs first. If there are no such sequences, print This sequence is anti-primed..

Sample Input

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

Sample Output

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.

Comments

0

dnialh_ commented on April 19, 2023, 6:50 a.m.

What does "80% of the test cases" mean in this context? Is it that in each test, there are at most 4 sequences with length more than 1000, or is it that 40/50 points are achievable for solutions that work for $n \le 1000$ ~n \le 1000~.

1

BalintR commented on April 19, 2023, 5:00 p.m. ← edited →

The latter. A solution that can consistently solve $n \le 1\,000$ ~n \le 1\,000~ is expected to score 40/50 points.

The statement has been updated to clarify this.

1

maxcruickshanks commented on June 30, 2022, 4:17 p.m.

Since the original data were weak, an additional test case was added, and all submissions were rejudged.