UTS Open '21 P2 - Prime Array - Olympiads Online Judge

UTS Open '21 P2 - Prime Array

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Memory limit: 64M

Author:

4fecta

Problem type

Edward is learning about prime numbers in math class today. Having just learnt what arrays are the day before, he decided to invent what he now calls a prime array. Specifically, he calls an array prime if the greatest common divisor of all its elements is $1$ ~1~. For example, $[4, 5, 2]$ ~[4, 5, 2]~ and $[1]$ ~[1]~ are prime but $[3, 9, 6]$ ~[3, 9, 6]~ and $[7]$ ~[7]~ are not. Having caught him dozing off in class, Mr. Brown challenges Edward to find an array that has exactly $K$ ~K~ prime non-empty subarrays. Since Mr. Brown is not looking forward to spending more than a few hours reading over the array, he specifies that the array must contain no more than $100$ ~100~ elements, and that all the elements of the array must be integers in the range $[1, 10^9]$ ~[1, 10^9]~. Now on the spot, Edward is asking you to help him solve this problem. Please help him find an array satisfying Mr. Brown's requirements.

Constraints

For this problem, you MUST pass the sample case in order to receive points.

$0 \le K \le 5 \times 10^3$ ~0 \le K \le 5 \times 10^3~

It can be proven that an array satisfying the requirements always exists under the given constraints.

Input Specification

The first and only line of input contains an integer $K$ ~K~, as described in the problem statement.

Output Specification

First, output one line containing $N$ ~N~ $(1 \le N \le 100)$ ~(1 \le N \le 100)~, the length of the array $A$ ~A~ you have found.

Then output $N$ ~N~ space separated integers $A_i$ ~A_i~ $(1 \le A_i \le 10^9)$ ~(1 \le A_i \le 10^9)~, representing the elements of the array $A$ ~A~.

Sample Input

Sample Output

5
5 8 2 6 3

Explanation

The prime subarrays are: $[5, 8], [5, 8, 2], [2, 6, 3], [5, 8, 2, 6], [8, 2, 6, 3], [5, 8, 2, 6, 3]$ .

Comments

-23

d3story commented on Feb. 9, 2021, 1:22 a.m. ← edit 4 →

Wait, there is an issue with this question is there not? How is it possible to have more than 4950 prime sub-arrays when doing this question. Let all of the numbers in this 100 array be unique primes let 1 represent the first prime and 2 represent the second prime etc all the way to the 100th. There could be 99 sub-arrays containing 1: {1,2},{1,2,3}..........{1,2,3.....99,100}. As seen in the sample case {1} by itself is not considered a sub-array. Now The total number of possible sub-primes arrays will be (1+99)*99/2 = 4950.

Ps, it is well known that there are 5050 sub-arrays in an array of 100 HOWEVER that is under the circumstances such that {1},{2}..... etc are all considered as sub-arrays which in this situation they are not and guess what 5050-100=4950. Maybe I am just being special again but I am quite sure my argument makes sense

This comment is hidden due to too much negative feedback. Show it anyway.

-6

WAO commented on Feb. 9, 2021, 11:13 p.m.

As a CMO qualifier myself I can assure you that there is nothing wrong with this problem and it's perfectly fine the way it is

This comment is hidden due to too much negative feedback. Show it anyway.

-18

kevinyang commented on Feb. 9, 2021, 4:31 a.m.

As a CMO qualifier I can assure you that there is nothing wrong with this problem and it's perfectly fine the way it is

This comment is hidden due to too much negative feedback. Show it anyway.

11

EpicChadGamer commented on Feb. 9, 2021, 3:40 a.m. ← edited →

Just solve the problem lol

11

BalintR commented on Feb. 9, 2021, 1:31 a.m.

Sub arrays of length one are valid as shown in the problem statement:

For example, $[4, 5, 2]$ ~[4, 5, 2]~ and $[1]$ ~[1]~ are prime but $[3, 9, 6]$ ~[3, 9, 6]~ and $[7]$ ~[7]~ are not