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

문제 설명

Your task is to calculate the number of trailing zeros in the factorial n!n!.

For example, 20!=2432902008176640000 and it has 4 trailing zeros.

입력

The only input line has an integer n.

출력 양식

Print the number of trailing zeros in n!.

입력 예

20

출력 예

4

제약조건

1 <= n <= 10^9

문제 풀이

팩토리얼에서 뒤에 나오는 0의 갯수는 N보다 작은 수중에서 곱해지는 5나 5의 거듭제곱수들이 몇번인가와 같다. 그래서, 5로 계속 나누면서 나오는 수들을 누적해서 출력한다. 엄밀하게는 2와 2의 거듭제곱수들의 빈도수와 비교해야 한다.

프로그램 내용

더보기 
#define MAX_N 1000000000

int main()
{
    int N;
    cin >> N; 

    /// count number of 5 less than N
    int count_5=0;
    int div=1;
    long base = N;

    while(div != 0)
        div = base / 5;
        count_5 += div;
        base = div;

	cout << count_5 << endl;

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21

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

문제 설명

Your task is to calculate the number of bit strings of length n.

For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

입력

The only input line has an integer n.

출력

Print the result modulo 10^9+7 

입력 예

3

출력 예

8

제약조건

1 <= n <=10^6

문제 풀이 

n - bit 의 문자열은 2^n 만큼의 다른 정보를 가진다. 입력 받은 N에 대해서 2^N mod Base 연산을 하고, 결과를 출력한다. 단, Base = 1e9 +7 이다. 

프로그램 내용

더보기 
#define MAX_N 1000000
#define BASE 1000000007 /// BASE is prime number

int modpow(int n)
{
    long long m = 1e9+7; 

    if (n == 0) return 1%m;

    long long u = modpow(n/2);

    u = (u*u) %m ;

    if (n%2 == 1) u = (u*2)%m;

    return u;
};

int main()
{
    int N;			/// number of bits    

    cout << modpow(N) << endl;

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Number Spiral (1071)  (0) 2019.09.21

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

문제 설명

Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.

입력 

The only input line contains an integer n.

출력

Print n integers: the results.

입력 예

8

출력 예

0
6
28
96
252
550
1056
1848

제약조건

1 <= n <= 10000

문제 풀이 

N x N 체스보드에 두개의 knight를 올려 놓는 방법의 경우의 수는 첫번째 나이트를 놓을 수 있는 경우의 수(NxN)와 두번째 나이트를 올려 놓을 수 있는 경우의 수 (NxN-1)를 곱한 만큼이다. 이 중에서 두개의 knight가 서로 공격할 수 있는 경우는 3x2 혹은 2x3의 작은 보드의 마주보는 귀퉁이에 나이트들이 위치하는 경우이다. 이 작은 보드의 수는 2x3의 경우는 (N-1)(N-2), 3x2의 경우는 (N-2)(N-1) 이다. 4개의 귀퉁이가 있으므로 4[(N-2)(N-1)+(N-1)(N-2)]를 전체에서 제외하면 된다. 문제에서는 2개의 Knight 색깔을 구분하지 않으므로, 계산한 경우의 수/2를 하면 답이다.

W    
    B
혹은 
W  
   
  B

프로그램 내용

더보기 
#define MAX_N 10000

int main()
{

    for (long i=1;i<= N;i++)
        unsigned long long k_case;
        k_case = i*i*i*i - 9*i*i + 24*i -16;

        if (i==1)
            cout << 0 << endl;
        else
            cout << k_case/2 << endl;

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19

출처: 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

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

문제 설명

You are given an array of N integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each turn, you may increase the value of any element by one. What is the minimum number of turns required?

입력 양식

The first input line contains an integer N: the size of the array.

Then, the second line contains N integers x_1,x_2,…,x_n : the contents of the array

출력 

Print the minimum number of turns.

입력 예

5
3 2 5 1 7

출력 예

5

문제 풀이

Constraints

  • 1 <= n  <= 2⋅10^5 
  • 1 <= x_i <= 10^9

입력을 배열로 받아 들여서, 입력 받은 수 전체를 비교한다. 현재 수보다 다음 수가 작으면, 그 차이 만큼 더하고 기록을 누적한다. 입력 범위에 주의하면 충분하다.

프로그램 내용

더보기 
#define MAX_N 200000
#define MAX_X 1000000000

int main()
{
    long long N;
    cin >> N;

    long long arr[N];

    for (int i=0; i< N; ++i)
        cin >> arr[i];

    long long op_count = 0;
    for (int i=0; i< N - 1; ++i)
    {
        long long temp = arr[i] - arr[i+1];

        if (temp >= 0)
        {
            arr[i+1] += temp;
            op_count += temp;
        }
    }

    cout << op_count << endl;

 

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19
CSES 1. Repetitions (1069)  (0) 2019.09.16
CSES 1. Missing Number (1083)  (0) 2019.09.15
CSES - Introductory Problems  (0) 2019.09.14

출처: https://train.usaco.org/usacogate

문제 설명

Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

입력

Line 1: N (1 <= N <= 1000), the number of records to be sorted
Lines 2-N+1: A single integer from the set {1, 2, 3}

출력

A single line containing the number of exchanges required

입력 예

9 
2 
2 
1 
3 
3 
3 
2 
3 
1

출력 예

4 

문제 풀이

정렬할 입력을 저장하면서, 1, 2, 3 숫자를 기록한다. bubble sort와 비슷한 방법으로 진행한다. 2보다 뒤쪽에 있는 1들을 2와 바꾼다. 3보다 뒤에 있는 1들을 3과 바꾼다. 마지막으로 3보다 뒤에 있는 2들을 3과 바꾼다. 

프로그램 내용

더보기 
#define MAX_N 1000

int main()
{
    int N;
    fin >> N;

    vector <int> in_Nums;
    int eachNum[3] = {0};

    for (int idx=0; idx< N ; ++idx)
        fin >> num;
        in_Nums.push_back(num);
        eachNum[num-1]++;		/// count 1, 2, 3

    /// exchange 1 with 2 until eachNum[0] 
    /// part(eachNum[0], 1 , 2, N)
    int cnt=0;
    for(int i= eachNum[0]; i< N; ++i)
        if(in_Nums[i] == 1)
        for(int j=0;j<eachNum[0];++j)
            if(in_Nums[j] == 2)
                swap(in_Nums[i],in_Nums[j]);

    /// exchange 1 with 3 until eachNum[0]
    for(int i= eachNum[0]; i< N; ++i)
        if(in_Nums[i]== 1)
        for(int j=0;j<eachNum[0];++j)
            if(in_Nums[j]==3)
                swap(in_Nums[i],in_Nums[j]);

    /// exchange 2 with 3 eachNum[0]+eachNum[1]
    for(int i= eachNum[0]+eachNum[1]; i< N; ++i)
        if(in_Nums[i]== 2)
        for(int j=0;j<eachNum[0]+eachNum[1];++j)
            if(in_Nums[j]==3)
                swap(in_Nums[i],in_Nums[j]);

 

Chapter 2. Bigger Challenges

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

'USACO Training' 카테고리의 다른 글

Problem 2.3.4 Money Systems  (0) 2019.10.11
Problem 2.2.4 Subset Sums  (0) 2019.10.10
Problem 2.1.4 Ordered Fractions  (0) 2019.09.18
Problem 2.2.5 Runaround Numbers  (0) 2019.09.18
Problem 1.6.4 SuperPrime Rib  (0) 2019.09.16

출처: https://train.usaco.org/usacogate

문제 설명

Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5:

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

입력 양식

One line with a single integer N.

출력

One fraction per line, sorted in order of magnitude. 

입력 예 

5

출력 예

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1 

문제 풀이 내용

받은 N보다 작은 정수들로 정수쌍 ( i, j ) 를 만들고 첫번째 수는 0, 마지막 수는 1/1 로 해서 vector에 저장한다. 이때 두수가 서로 서로소가 아닌 경우는 제외한다. 왜냐하면 1/2 = 2/4 = 3/6 ..이 되지만, 문제에서는 1/2만 출력해야 한다. vector를 정렬하는데, (a, b) vs (c, d)의 크기 비교는 a/b vs c/d => ad/bd vs bc/bd => ad vs bc 로 비교하도록 했다.

프로그램 내용

더보기 
#define MAX_M 161

/// check co-prime a, b -> gcd(a, b) == 1
int CoPrime(int a, int b);

vector <pair<int, int>> sequence;

int main() {
    sequence.push_back(make_pair(0,1));

	for (int denominator = 1; denominator < M+1 ; ++denominator)
        for (int numerator  = 1; numerator < denominator ; ++numerator)
            if( CoPrime(numerator, denominator) == 1)
                sequence.push_back(make_pair(numerator, denominator));

	sequence.push_back(make_pair(1,1));

    sort(sequence.begin()+1, sequence.end()-1, compare2);

    for (int idx= 0; idx < sequence.size(); ++idx)
        fout << sequence[idx].first << "/" << sequence[idx].second << endl;

 

Chapter 2.  Bigger Challenges

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

'USACO Training' 카테고리의 다른 글

Problem 2.2.4 Subset Sums  (0) 2019.10.10
Problem 2.1.5 Sorting A Three-Valued Sequence  (0) 2019.09.18
Problem 2.2.5 Runaround Numbers  (0) 2019.09.18
Problem 1.6.4 SuperPrime Rib  (0) 2019.09.16
Problem 1.6.3 Prime Palindromes  (0) 2019.09.16

출처: https://train.usaco.org/usacogate

문제 설명

Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:

If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
Repeat this cycle (this time for the six counts designed by the `6') and you should end on a new digit: 2 8 1 3 6 2, namely 2.
Repeat again (two digits this time): 8 1
Continue again (one digit this time): 3
One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.
Given a number M (that has anywhere from 1 through 9 digits), find and print the next runaround number higher than M, which will always fit into an unsigned long integer for the given test data.

입력

A single line with a single integer, M

출력

A single line containing the next runaround number higher than the input value, M.

입력 예

81361

출력 예

81362

문제 풀이 내용

입력받는 숫자는 최대 9자리가 가능하다. (중복없이 1~9) 두개의 배열을 만들어서, 유일성 검사를 하고, 문제 조건대로 각 자리수 숫자에 도착했는지 검사한다. 숫자 자리수 만큰 움직여서, 모든 자리수에 도착했으면 통과, 아니면 실패하도록 한다. 숫자 자리수 순환 시키는 것은 % 연산으로 처리한다.

프로그램 내용

더보기 
bool visit[10] = {false};
bool digit[10] = {false};

bool check(int n) /// check reachable within digit length


int main()
{
    int N;
	fin >> N;

    N++;
    while(!check(N))
        N++;

    fout << N << endl;

 

Chapter 2. Bigger Challenges

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

'USACO Training' 카테고리의 다른 글

Problem 2.1.5 Sorting A Three-Valued Sequence  (0) 2019.09.18
Problem 2.1.4 Ordered Fractions  (0) 2019.09.18
Problem 1.6.4 SuperPrime Rib  (0) 2019.09.16
Problem 1.6.3 Prime Palindromes  (0) 2019.09.16
Problem 1.6.2 Number Triangles  (0) 2019.09.16

+ Recent posts

티스토리툴바