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

문제 설명

Given a string, your task is to generate all different strings that can be created using its characters.

입력 

The only input line has a string of length n. Each character is between a–z.

출력

First print an integer k: the number of strings. Then print k lines: the strings in alphabetical order.

입력 예

aabac

출력 예

20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa

제약조건

1 ≤ n ≤ 8

문제 풀이 내용

문자열을 읽어 들인다음, 정렬한다. next_permutation() 기능을 이용해서 새로운 문자열을 만들고 set<string>에 저장한다. set에 저장된 문자열 개수와 문자열들을 출력한다.

프로그램 내용

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

    set <string> out_str;

    sort(in_str.begin(), in_str.end());

    do {
        out_str.insert(in_str);
    } while (next_permutation(in_str.begin(), in_str.end()));

    cout << out_str.size() << endl;
    for (auto it : out_str)  
	    cout << it << endl;

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Chessboard and Queens (1624)  (0) 2019.09.23
CSES 1. Apple Division (1623)  (0) 2019.09.23
CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Trailing Zeros (1618)  (0) 2019.09.23

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

문제 설명

Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).

입력 

The only input line has a string of length n consisting of characters A–Z.

출력

Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTION".

입력 예

AAAACACBA

출력 예

AACABACAA

제약조건

1 <= n <= 10^6

문제 풀이

입력을 읽고, A~Z 까지 나온 빈도수를 센다. 나타난 빈도수가 홀수인 경우가 2 이상이면 palindrome 을 만들수 없으므로 "NO SOLUTION"을 출력한다.

A~Z까지 나타난 문자의 빈도수/2인 문자열을 만들어서 앞쪽과 뒤쪽으로 붙여나간다.

 

홀수인 경우는 가운데에 빈도수가 홀수인 문자를 추가하고, 아니면 그냥 앞쪽과 뒤쪽을 붙여서 만든다.

프로그램 내용

더보기 
#define MAX_S 1000000

int main()
{
    string in_str;
    cin >> in_str; /// input

	int ch_count[26] = {0};
    string out_str = in_str;

    int str_size = in_str.size();

    for(int i=0; i< in_str.size(); i++)
        ch_count[in_str[i]- 'A']++;

    int odd_count =0;
    int progress=0;
    char odd_char = '0';

    for(int i=0; i< 26; i++)
        if (ch_count[i] % 2)
            odd_count++;

		if (odd_count > 1)        
            cout << "NO SOLUTION" << endl;

		if (odd_count == 1 && odd_char == '0')
        	odd_char = 'A'+i;

    string first_half="";
    string second_half="";

    for(int i=0; i< 26; i++)
        char temp = 'A'+i;
        if (ch_count[i] > 0)
            string s(ch_count[i]/2, temp);
            first_half = first_half+s;
            second_half = s+second_half;

	if (odd_count == 1 && str_size %2 )
        out_str = first_half + odd_char + second_half;
    else
        out_str = first_half + second_half;

 

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Apple Division (1623)  (0) 2019.09.23
CSES 1. Creating Strings I (1622)  (0) 2019.09.23
CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22

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

문제 설명

You have two coin piles containing a and b coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.


Your task is to efficiently find out if you can empty both the piles.

입력

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

After this, there are t lines, each of which has two integers a and b: the numbers of coins in the piles.

출력

For each test, print "YES" if you can empty the piles and "NO" otherwise.

입력 예

3
2 1
2 2
3 3

출력 예

YES
NO
YES

제약조건

  • 1 <= t <= 10^5
  • 0 <= a,b <= 10^9

문제 풀이

두개의 입력 a, b를 이용해서 가능한 조건들을 검사한다.

먼저, 한번에 제거 가능한 숫자는 3개 이므로, 두개의 합이 3의 배수가 아니면 불가능하다. 왼쪽에서 2개 제거하는 수를 x, 오른쪽에서 2개 제거하는 수를 y로 해서 계산한다.

더할 수는 없으므로 하나라도 음수이면 불가능하다. (x < 0 || y <0)

한쪽의 입력이 다른 쪽의 2배보다 크면 불가능하다. (a > 2b || 2a < b)

두 입력의 차가 abs(a-b) = abs(x-y) 이면, 모두 없애는게 가능하므로, 이 조건까지 확인해서 결과를 출력한다.  

프로그램 내용

더보기 
#define MAX_T 100000
#define MAX_P 1000000000

int main()
{
    int a, b;
    int x, y;

	cin >> a >> b;
	x = (2*a-1*b)/3;
	y = (2*b-1*a)/3;

	if ((a+b) % 3 == 0)
		if ( a > 2*b || 2*a < b )
			cout << "NO" << endl;
		else if ( x < 0 || y < 0)
			cout << "NO" << endl;
		else if ( abs(a-b) == abs(x-y) )
        	cout << "YES" << endl;

        else
            cout << "NO" << endl;
    }
}

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Creating Strings I (1622)  (0) 2019.09.23
CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Knights (1072)  (0) 2019.09.22

+ Recent posts

티스토리툴바