본문 바로가기
알고리즘/Codeforces

Codeforces Round #683 (Div. 2, by Meet IT) AB

by 유시은 2020. 11. 16.
import sys
input = sys.stdin.readline
 
for _ in range(int(input())):
    n = int(input())
    print(n)
    for i in range(n):
    	print(i+1, end=" ")
    print()

 

A - Add Candies

 

한 바구니를 선택한다는 조건을 무시하면, 사탕을 n번 넣었을 때 모든 바구니에 똑같이 (n * (n+1))/2 개의 사탕을 넣게 된다.

 

이때 각 바구니에 들어있는 사탕 수는 처음과 같이 등차 +1의 관계를 가진다.

 

따라서 1번 바구니부터 1, 2, 3... 순서로 빼주면 모든 바구니가 같은 수의 사탕을 가지게 된다.

 

결론은 1번부터 n번까지 순서대로 한 번 씩 선택하면 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
int board[10][10];
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    int TEST; cin >> TEST; while (TEST--) {
        int r, c; cin >> r >> c;
        int s = 0, n = 0, z = 0, m = 1000;
        for (int i = 0; i < r * c; ++i) {
            cin >> board[r][c];
            s += abs(board[r][c]);
            m = min(m, abs(board[r][c]));
            if (board[r][c] < 0) n += 1;
            if (board[r][c] == 0) z += 1;
        }
        if (z > 0) {
            cout << s;
        }
        else {
            if (n % 2 == 0) {
                cout << s;
            }
            else {
                cout << s - m*2;
            }
        }
        cout << "\n";
    }
}

 

B - Numbers Box

 

중요한 아이디어는, 인접한 수를 계속 고르면서 진행하면 결국 임의의 두 위치 A와 B에 -1을 곱할 수 있다는 것이다.

 

0이 있으면 모든 음의 부호를 0과 맞바꾸어 모든 수를 양수로 만들 수 있다.

 

0이 없으면 음수가 짝수개인 경우와 홀수개인 경우로 나뉜다.

 

  • 음수가 짝수개라면 음수끼리 쌍을 맞추어 모두 양수로 만들 수 있다.
  • 음수가 홀수개라면 결국 마지막에 음수가 하나 남는데, 이 수는 절댓값이 가장 작은 수로 결정하면 된다. 

 

댓글