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

많은 다뤄야 할 내용들을 가볍게 소개하면서 지나가는 책이다.

 

어떤 내용들이 지원되는지 항목을 찾는 수준까지 쓸 수 있을 책이다.

 

실제로 구현코드나 적용방법은 부족하고, 개론서 수준으로 생각하면 아쉽지는 않다.

 

책에 나오는 예제 코드들은 실제 프로그램 작성에 사용하기는 부족하다는 느낌이다.

 

C++ 언어 전체에 대해서, 기초적인 지식을 쌓는 수준을 목표로 살펴봤다.

 

 

프로그램 언어 입문서라고 평가하면 충분하다.

 

 

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

'Basic Preparation' 카테고리의 다른 글

USAMO vs USACO III  (0) 2020.04.16
USAMO vs USACO II  (0) 2020.04.09
USACO vs USAMO I  (0) 2020.04.05
C++ 공부 - 2019. 8월  (0) 2019.09.02
2019년 8월 진행  (0) 2019.08.24

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

문제 설명

The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .

입력 

Line 1: Two integers, a and b

출력 

The list of palindromic primes in numerical order, one per line.

입력 예

5 500

출력 예

5
7
11
101
131
151
181
191
313
353
373
383

문제 풀이 

자리수가 짝수인 palindrome 은 11의 배수 이므로, 자리수가 홀수인 숫자들을 만들어서 소수인지 검사한다.  다만, 소수는 2를 제외하면 모두 짝수이고, 끝자리가 0/5인 경우도 5의 배수가 된다. 또, 자리수 합이 3의 배수이면 3의 배수가 된다. 이런 몇가지 검사를 통과한 수들을 대상으로 소수검사를 시행한다.

프로그램 내용

더보기 
#define MIN_A 5
#define MAX_B 100000000

vector <long> palindrome;

bool check_prime(long input);

void palindrome1(int A, int B); /// 1자리 소수 5, 7
void palindrome2(int A, int B); /// 2자리 소수 palindrome 11
void palindrome3(int A, int B); 
void palindrome5(int A, int B);
void palindrome7(int A, int B);
void build_palindrome(int A, int B);

int main() {
    /// build palindrome with digit n
    build_palindrome(A, B);

    sort(palindrome.begin(),palindrome.end(),compare);

    for(int idx=0; idx < palindrome.size();++idx)
        if( palindrome[idx] >= A && palindrome[idx] <= B)
            fout << palindrome[idx] << endl;

 

Chapter 1. Getting started

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

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

Problem 2.2.5 Runaround Numbers  (0) 2019.09.18
Problem 1.6.4 SuperPrime Rib  (0) 2019.09.16
Problem 1.6.2 Number Triangles  (0) 2019.09.16
Problem 1.5.2 Arithmetic Progressions  (0) 2019.09.14
USACO Training - Chapter 2. Bigger Challenges  (0) 2019.09.13

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

문제 설명

Number Triangles
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

입력

The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

출력

A single line containing the largest sum using the traversal specified.

입력 예

5 
7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5

출력 예

30

문제 풀이 내용

읽어 들인 입력들을 2차원 배열에 저장한다. 첫번째 입력부터 아래로 내려가면서 더해간다. 양쪽에서 도착할 수 있는 경우, 2개위 상위 수에서 큰수를 기준으로 한다. 이렇게 마지막 행에 도착해서, 제일 큰 수를 출력한다. 

프로그램 내용

더보기 
#define MAX_R 1001
#define MAX_N 100

int Tr[MAX_R][MAX_R] = {0};
int val[(MAX_R+1)*MAX_R/2] = {0};
int ret = 0;

int main() {
    /// Read 1 ~ idx number
    for (int i=0; i < R ; i++)
        for (int j=0; j<i+1 ; j++)
            fin >> Tr[i][j];

            idx1 = (i*(i+1)/2+j);
            if (i > 0)
                if(j == 0 )
                {
                    idx2 = idx3 = i*(i-1)/2;
                }
                else if (j == i)
                {
                    idx2 = idx3 = (i*(i-1)/2+j-1);
                }
                else
                {
                    idx2 = (i*(i-1)/2+j-1);
                    idx3 = (i*(i-1)/2+j);
                }

            }
            val[0] = Tr[0][0];
            val[1] = val[0] + Tr[1][0];
            val[2] = val[0] + Tr[1][1];

            if(idx1 > 2)
            {
                val[idx1] = max (val[idx2], val[idx3]) + Tr[i][j];
            }

            ret = max(ret, val[idx1]);

 

Chapter 1. Getting started

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

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

Problem 1.6.4 SuperPrime Rib  (0) 2019.09.16
Problem 1.6.3 Prime Palindromes  (0) 2019.09.16
Problem 1.5.2 Arithmetic Progressions  (0) 2019.09.14
USACO Training - Chapter 2. Bigger Challenges  (0) 2019.09.13
Problem 1.4.8 Ski Course Design  (0) 2019.09.12

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

문제 설명

You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character.

입력 

The only input line contains a string of n characters.

출력

Print one integer: the length of the longest repetition.

입력 예

ATTCGGGA

출력 예

3

문제 풀이

1 <= n <= 10^6

문자열을 입력받아서, 앞에서부터 문자 하나씩 읽어 가면서, 직전 문자와 같으면 카운터를 증가시키고, 다르면 초기화 시킨다. 가장 큰 카운터 값을 기록하고 있다가, 변경된 카운터 값과 비교해서 최대값을 유지시킨다.

프로그램 내용

더보기 
#define MAX_N 1000000

int main()
{
    string inString;
    cin >> inString;

    int s_count = 0;
    int t_count = 1;
    for (int i=1; i <= inString.size(); ++i)
        char t_char = inString[i-1];
        char tt_char = inString[i];

        if ( t_char == tt_char)
            t_count++;
        else
            t_count = 1;

        s_count = max (s_count, t_count);

	cout << s_count << endl;

 

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

CSES 1. Permutations (1070)  (0) 2019.09.19
CSES 1. Increasing Array (1094)  (0) 2019.09.19
CSES 1. Missing Number (1083)  (0) 2019.09.15
CSES - Introductory Problems  (0) 2019.09.14
CSES 1. Weird Algorithm (1068)  (2) 2019.09.14

+ Recent posts

티스토리툴바