CF1388A-Captain Flint and Crew Recruitment

题目:

题目描述:

Despite his bad reputation, Captain Flint is a friendly person (at least, friendly to animals). Now Captain Flint is searching worthy sailors to join his new crew (solely for peaceful purposes). A sailor is considered as worthy if he can solve Flint’s task.

Recently, out of blue Captain Flint has been interested in math and even defined a new class of integers. Let’s define a positive integer $ x $ as nearly prime if it can be represented as $ p \cdot q $ , where $ 1 < p < q $ and $ p $ and $ q $ are prime numbers. For example, integers $ 6 $ and $ 10 $ are nearly primes (since $ 2 \cdot 3 = 6 $ and $ 2 \cdot 5 = 10 $ ), but integers $ 1 $ , $ 3 $ , $ 4 $ , $ 16 $ , $ 17 $ or $ 44 $ are not.

Captain Flint guessed an integer $ n $ and asked you: can you represent it as the sum of $ 4 $ different positive integers where at least $ 3 $ of them should be nearly prime.

Uncle Bogdan easily solved the task and joined the crew. Can you do the same?

输入格式:

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases.

Next $ t $ lines contain test cases — one per line. The first and only line of each test case contains the single integer $ n $ $ (1 \le n \le 2 \cdot 10^5) $ — the number Flint guessed.

输出格式:

For each test case print:

• YES and $ 4 $ different positive integers such that at least $ 3 $ of them are nearly prime and their sum is equal to $ n $ (if there are multiple answers print any of them);
• NO if there is no way to represent $ n $ as the sum of $ 4 $ different positive integers where at least $ 3 $ of them are nearly prime.

You can print each character of YES or NO in any case.

样例:

样例输入 1:

1
2
3
4
5
6
7
8

7
7
23
31
36
44
100
258

样例输出 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

NO
NO
YES
14 10 6 1
YES
5 6 10 15
YES
6 7 10 21
YES
2 10 33 55
YES
10 21 221 6

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include "ybwhead/ios.h"
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        int n;
        yin >> n;
        if (n >= 1 + 6 + 10 + 14)
        {
            puts("YES");
            if (n == 36)
            {
                yout << "5 6 10 15" << endl;
                continue;
            }
            if (n == 44)
            {
                yout << "6 7 10 21" << endl;
                continue;
            }
            if (n == 40)
            {
                yout << "6 10 15 9" << endl;
                continue;
            }
            // if (n == 40)
            yout << 6 << " " << 10 << ' ' << 14 << ' ' << n - 10 - 6 - 14 << endl;
        }
        else
            puts("NO");
    }
    return 0;
}