출처: https://cses.fi/problemset/task/1092

문제 설명

Your task is to divide the numbers 1,2,…,n into two sets of equal sum.

입력 양식

The only input line contains an integer n.

출력

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

입력 예

Example 1.

7

 

Example 2.

6

출력 예

Example 1.

YES
4
1 2 4 7
3
3 5 6

 

Example 2.

NO

제약조건

1 <= n  <= 1e6

문제 풀이

입력받은 n 이 4k 혹은 4k+3 인 경우에만 YES가 된다. ( (n+1)*n/2/2 == 0 ) n이 4k+3 형태인 경우와 4k 형태인 경우로 나누고, 4개 혹은 3개 그룹을 같도록 나누어서 출력한다.

프로그램 내용

더보기 
#define MAX_N 1000000

int main()
{
    long long N;
    long long K;

    cin >> N;

    if ( (N+1)*N/2 % 2 != 0 )
        cout << "NO" << endl;

    if ( (N+1)*N/2 % 2 == 0 )
        cout << "YES" << endl;
        /// N = 4k + 3
        /// 2(k+1) ,
        /// 0, 3, 4, 7, ...
        if ( N % 4 == 3)
            K = (N+1) / 4;
            cout << 2*K -1 << endl;
            for (int i=0; i< K; i++)
                if ( i == 0)
                    cout << 4*i + 3 << " ";
                else
                    cout << 4*i << " " << 4*i + 3 << " ";
        /// 2(k+1)-1,
        /// 4k+2, 4k+1, 4(k-1)+2, 4(k-1)+1, ...
        /// 1, 2, 5, 6, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1)+1 << " " << 4*(i - 1) +2 << " ";

        if ( N % 4 == 0)
            K = N / 4;
            /// N = 4k
            /// 2(k+1) ,
            /// 1, 4, 5, 8, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1) + 1 << " " << 4*i << " ";

			/// N = 4k + 3
            /// 2(k+1) ,
            /// 2, 3, 6, 7, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1)+2 << " " << 4*(i - 1) +3 << " ";

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19
CSES 1. Increasing Array (1094)  (0) 2019.09.19

출처: https://cses.fi/problemset/task/1071

문제 설명

A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:

1 2 9 10 25
4 3 8 11 24
5 6 7 12 23
16 15 14 13 22
17 18 19 20 21

Your task is to find out the number in row y and column x.

입력

The first input line contains an integer t: the number of tests.

After this, there are tt lines, each containing integers y and x.

출력

For each test, print the number in row y and column x.

입력 예

3
2 3
1 1
4 2

출력 예

8
1
15

제약조건

  • 1 <= t  <= 10^5 
  • 1 <= y , x <= 10^9

 

문제 풀이 

(y, x) 위치를 입력 받아서, y 와 x 를 비교해서 더 큰 수를 기준으로 출발한다. x의 경우 홀수이면 (2k+1)^2에서 y만큼 줄이면 원하는 답이 되고, 짝수이면 (2k+1)^2+1 에서 y만큼 더하면 된다. y의 경우 짝수이면 (2k)^2에서 x 만큼 줄이고, 홀수이면 (2k)^+1에서 x만큼 더하면 된다.

프로그램 내용

더보기 
#define MAX_SQUARE 100000
#define MAX_ELEMENT 1000000000

int main()
{    
    long long x, y;
	cin >> y >> x;

    /// (1,1), (1,2), (1,3), ... , (1,t)
    /// (2,1), (2,2), (2,3), ... , (2,t)
    /// ... (1, (2k-1)) -> (2k-1)^2 , (2,(2k-1)) = (2k-1)^2 - (2-1) = 8
    /// ... (2k, 1) -> (2k)^2, (2k, 2) = (2k)^2 - (2-1) = 15
    if (x >= y) /// (2,3), (3,3)           
		if( x%2 == 1)	/// x = 2k-1,
			result[i] = x*x - (y-1);
		else
			result[i] = (x-1)*(x-1) + y;
	else /// y > x            
		if( y%2 == 0 ) /// y = 2k,
			result[i] = y*y - (x-1);
		else
			result[i] = (y-1)*(y-1) + x;

	for (int i=0; i< TestNum; i++)
        cout << result[i] << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19
CSES 1. Increasing Array (1094)  (0) 2019.09.19
CSES 1. Repetitions (1069)  (0) 2019.09.16

출처: https://cses.fi/problemset/task/1070

문제 설명

A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 1.

Given N, construct a beautiful permutation if such a permutation exists.

입력 양식

The only input line contains an integer N.

출력

Print a beautiful permutation of integers 1,2,…,n If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

입력 예

test1. 5 

test2. 3 

출력 예

test1. 4 2 5 3 1

test2. NO SOLUTION

제약조건

1 <=  n <= 1e6  

문제 풀이

N = 1 이면, 그냥 1을 출력 No distance, N=2 or N=3 -> No Solution, if N > 4 이면 짝수들을 2부터 2씩 커지는 순서로 N보다 작거나 같을 때까지 출력하고 1부터 나머지 홀수들을 2씩 증가시키면서 출력한다.

- 처음에는 next_permutation 함수를 써서 임의의 문자열에 대해서, 거리들을 측정했는데 숫자가 커지면서 TIME LIMIT EXCEEDED 가 나와서 그냥 만드는 방법으로 변경했다.

프로그램 내용

더보기 
int main()
{
    int N;
    cin >> N;

    vector <int> numbers;			/// 1 ~ N
    for (int idx=0; idx< N; ++idx)
        numbers.push_back(idx+1);

    if (N == 1)
        cout << 1 << endl;
    else if (N==2 ||N == 3)
        cout << "NO SOLUTION" << endl;
    else
        for (int i=1; i < N; i += 2)	/// odd index
            cout << numbers[i] << " ";
        for (int i=0; i < N; i += 2)	/// even index
            cout << numbers[i] << " ";

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Increasing Array (1094)  (0) 2019.09.19
CSES 1. Repetitions (1069)  (0) 2019.09.16
CSES 1. Missing Number (1083)  (0) 2019.09.15

+ Recent posts

티스토리툴바