MTXN2NT1 - XN2NTQ - Judge Subtask 3, 4
English | Vietnamese |
For a positive integer n a1, a2, .... an, sought grouped satisfy the following conditions:
- Each number can only be placed in a group;
- Each group has exactly 2 and the total number of two numbers in each group is prime;
- The number of groups are classified as the most.
example: With 8 positive integers 1, 2, 3, 4, 5, 6, 7, 8 have a classified into 4 groups (1,4); (2.5); (3.8); (6.7);
Input
- The first line contains an integer N.
- 2nd line contains N integers a1, a2, ... an. (a[i] <= 10^6).
Output
- 1 single line group number to find the most
Example
Input: 8 1 2 3 4 5 6 7 8 Output: 4
Subtask 1: n<=10 [25 tests]
Subtask 2: n<=20 [25 tests]
Subtask 3: n<=1000 [25 tests]
Subtask 4: n <= 10 ^ 5, the numbers a1, a2, .. a[n] is a permutation of 1, 2, ... n [25 tests]
Note: here judge subtask 3, 4! go to MTXN2NTQ to judge substack 1, 2.
http://www.spoj.com/problems/MTXN2NTQ/en/
hide comments
Con Bò Huyền Thoại:
2014-12-17 15:57:24
Managers expect spoj.com sympathy for the existence of the second problem. because we have 100 test. but only a maximum of 63 test upload / problem. So we decided to split substack substack 1.2 and 3.4.
|
Added by: | Đặng Minh Tiến |
Date: | 2014-12-16 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |