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

 

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

 

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

 

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

 

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

문제 설명

Butchering Farmer John's cows always yields the best prime rib. You can tell prime ribs by looking at the digits lovingly stamped across them, one by one, by FJ and the USDA. Farmer John ensures that a purchaser of his prime ribs gets really prime ribs because when sliced from the right, the numbers on the ribs continue to stay prime right down to the last rib, e.g.:
     7  3  3  1
The set of ribs denoted by 7331 is prime; the three ribs 733 are prime; the two ribs 73 are prime, and, of course, the last rib, 7, is prime. The number 7331 is called a superprime of length 4.

Write a program that accepts a number N 1 <=N<=8 of ribs and prints all the superprimes of that length.

The number 1 (by itself) is not a prime number.

입력

A single line with the number N.

출력 

The superprime ribs of length N, printed in ascending order one per line.

입력 예

4

출력 예

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

문제 풀이 내용

제일 왼쪽에 올 수 있는 숫자는 2/3/5/7 (한자리수 소수)만 올 수 있다. 또한 두자리수 이상의 수에서 제일 앞을 제외한 모든 자리수는 (1/3/7/9) 만이 가능하다. 이 조건을 만족하도록, 왼쪽에서부터 숫자를 만들어 출력한다.

프로그램 내용

더보기 
#define MAX_N 8

int digit_limit[4] = {1,3,7,9};

vector <long> sprimes;
int s_start[MAX_N] = {0};
int s_end[MAX_N] = {0};

bool check_prime(long input);
void build_digit1();
void build_digit2(); /// 1digit rib-prime + digit_limit => check_prime
... 
void build_digit8(); /// 7digit rib-prime + digit_limit => check_prime
void build_numbers(); /// build 1~8digit rib-prime

int main() {
    int digit;

    /// build N digit numbers
    build_numbers();

    for (int idx=0; idx<sprimes.size(); ++idx)
            fout << sprimes[idx] <<endl;

 

Chapter 1. Getting started

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

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

Problem 2.1.4 Ordered Fractions  (0) 2019.09.18
Problem 2.2.5 Runaround Numbers  (0) 2019.09.18
Problem 1.6.3 Prime Palindromes  (0) 2019.09.16
Problem 1.6.2 Number Triangles  (0) 2019.09.16
Problem 1.5.2 Arithmetic Progressions  (0) 2019.09.14

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

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

문제 설명

You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.

입력 

The first input line contains an integer n.

The second line contains n−1 numbers. Each number is distinct and between 1 and n (inclusive).

출력 

Print the missing number.

입력 예

5
2 3 1 5

출력 예

4

문제 풀이

2 <= n <= 2⋅10^5,

1~N까지 합이 N*(N+1)/2 이므로, 입력들을 다 더해서 두 수의 차이를 비교하면 답을 찾을 수 있다.

 

프로그램 내용

더보기 
#define MAX_N 2*100000

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

    if (n > 2*100000) return 0;

    long sum=0;
    for(int i=0; i<n-1;i++)
        int temp;
        cin >> temp;
        sum += temp;

    long expected_sum = n*(n+1)/2;

    int missing = expected_sum - sum;

    cout << missing << endl;

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

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
CSES - Introductory Problems  (0) 2019.09.14
CSES 1. Weird Algorithm (1068)  (2) 2019.09.14
  1. Weird Algorithm  (1) 
  2. Missing Number (1)
  3. Repetitions (1)
  4. Increasing Array (1)
  5. Permutations (1)
  6. Number Spiral (1)
  7. Two Knights (1)
  8. Two Sets (1)
  9. Bit Strings (1)
  10. Trailing Zeros (1)
  11. Coin Piles (1)
  12. Palindrome Reorder (1)
  13. Gray Code
  14. Tower of Hanoi
  15. Creating Strings (1)
  16. Apple Division (1) 
  17. Chessboard and Queens (1)
  18. Digit Queries 
  19. Grid Paths (1)

CSES Problem Set ( link )

 

 

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

'CSES' 카테고리의 다른 글

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
CSES 1. Missing Number (1083)  (0) 2019.09.15
CSES 1. Weird Algorithm (1068)  (2) 2019.09.14

: https://cses.fi/problemset/task/1068

문제 설명

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:

3→10→5→16→8→4→2→1

입력 

The only input line contains an integer n.

출력  

Print a line that contains all values of n during the algorithm.

입력 예

3

출력 예

3 10 5 16 8 4 2 1

문제 풀이

입력받는 정수값이 너무 크면, 프로그램을 종료하도록 하고, 문제에서 설명한 알고리즘을 구현했다.

 

프로그램 설명  

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

    if (n > 1000000) return 0;

    while(true)
        cout << n << " " ;
        if ( n == 1 ) break;
        else if ( n %2 == 0) n /= 2;
        else n = n*3 + 1;

 

Introductory problems ( link )

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

'CSES' 카테고리의 다른 글

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
CSES 1. Missing Number (1083)  (0) 2019.09.15
CSES - Introductory Problems  (0) 2019.09.14

출처: http://train.usaco.org  

 

 

문제 설명

An arithmetic progression is a sequence of the form a, a+b, a+2b, ..., a+nb where n=0, 1, 2, 3, ... . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p^2 + q^2 (where p and q are non-negative integers).

TIME LIMIT: 5 secs

입력 

INPUT FORMAT
Line 1: N (3 <= N <= 25), the length of progressions for which to search
Line 2: M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

출력

If no sequence is found, a single line reading `NONE'. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first. 

There will be no more than 10,000 sequences.

입력 예

5 
7

출력 예

1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24

문제 풀이 내용

먼저, 제곱수들의 합들의 집합을 만든다. 이때, 집합의 값들을 같이 저장해두고, 검색할때 참고한다. 

검색하는 대상을 줄일 수 있는 방법을 찾는다. 일단,  a + b*n 이라고 수열을 정의한다. 

N개의 수열이 모두 집합에 있다고 하면,  a + b * (N-1) < 2 * M * M  이 된다. 여기에서 b의 범위를 축소하면,  b < 2*M*M/(N-1) 이 된다. 또, 제곱수들의 합인 집합에서 더하는 제곱수들이 커지면 집합내의 수들의 간격이 넓어진다.

3^2 + 4^2 = 25, 4^2+4^2 = 32  gap : 9 vs. 100^2 + 100^2 = 200, 100^2 + 101^2 = 221 gap: 21

그러므로, 만들어진 수  a + b * (N-1) 가 제곱수 합의 집합에 있는지 검사할 때는 큰 수들에서부터 검색하면 없는 경우를 더 빨리 찾을 수 있다.

프로그램 내용

더보기 
#define MAX_N 25 /// 3 <= N <= 25
#define MAX_M 250 /// 1 <= M <= 250
#define MAX_SEQUENCE 10000

/// TIME LIMIT: 5 secs

int main() {
    int N=0; int M=0;
    fin >> N >> M;

    bool noneF = true;

    /// 0 <= p, q <= M

    /// build bisqueare sets
    bool bsqurares[2*M*M+1] = {false};
    int places[4*M*M] = {0};
    int pl=0;

    for (int idx1=0; idx1 < M+1 ; ++ idx1)
        for (int idx2 = 0; idx2< M+1 ; ++ idx2)
            if(!bsqurares[idx1*idx1 + idx2*idx2])
                bsqurares[idx1*idx1 + idx2*idx2] = true;
                places[pl] =  idx1*idx1 + idx2*idx2;
                pl++;

    /// find in bsquares
    /// a in bsquare, a+b in bsquare, ... a + (n-1)b in bsquare
    /// (N-1) * b <= 2*M*M => b <= 2*M*M/(N-1)
    /// a + b*(N-1) < 2*M*M ... backward search (N-1) ...0 
    /// many gap in bsquare for bigger numbers
 
    for (int def=1; def <= M*M*2/(N-1);def++) /// b
        for (int p = 0; places[p]<= (M*M*2 - ((N-1)*def)); p++) /// a
            bool is;
            is = true;
            int where;

            for (int c = (N-1); c>=0 ; c--)
                if (places[p]+c*def > 2*M*M) break;
                if (!bsqurares[places[p]+c*def]) /// a+ b*n
                    is = false;
                    where = (p+c*def);

 

Chapter 1. Getting started

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

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

Problem 1.6.3 Prime Palindromes  (0) 2019.09.16
Problem 1.6.2 Number Triangles  (0) 2019.09.16
USACO Training - Chapter 2. Bigger Challenges  (0) 2019.09.13
Problem 1.4.8 Ski Course Design  (0) 2019.09.12
Problem 1.4.7 Wormholes  (0) 2019.09.12

USACO training chapter 2


Section 2.1.1 Text Graph Theory
Section 2.1.2 Text Flood Fill Algorithms
Section 2.1.3 Prob The Castle (1)
Section 2.1.4 Prob Ordered Fractions (1)
Section 2.1.5 Prob Sorting A Three-Valued Sequence (1)
Section 2.1.6 Prob Healthy Holsteins (1)
Section 2.1.7 Prob Hamming Codes (1)

 

Section 2.2 Data Structures, Dynamic Prog. 
Section 2.2.1 Text Data Structures 

Section 2.2.2 Text Dynamic Programming 

Section 2.2.3 Prob Preface Numbering (1)

Section 2.2.4 Prob Subset Sums ( 1 )

Section 2.2.5 Prob Runaround Numbers (1)

Section 2.2.6 Prob Party Lamps

 

Section 2.3 Problems

Section 2.3.1 Prob The Longest Prefix

Section 2.3.2 Prob Cow Pedigrees

Section 2.3.3 Prob Zero Sum

Section 2.3.4 Prob Money Systems ( 1 )

Section 2.3.5 Prob Controlling Companies


Section 2.4  Shortest Paths

Section 2.4.1 Text Shortest Paths 

Section 2.4.2 Prob The Tamworth Two 

Section 2.4.3 Prob Overfencing 

Section 2.4.4 Prob Cow Tours 

Section 2.4.5 Prob Bessie Come Home 

Section 2.4.6 Prob Fractions to Decimals

 

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

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

Problem 1.6.2 Number Triangles  (0) 2019.09.16
Problem 1.5.2 Arithmetic Progressions  (0) 2019.09.14
Problem 1.4.8 Ski Course Design  (0) 2019.09.12
Problem 1.4.7 Wormholes  (0) 2019.09.12
Problem 1.4.6 Combination Lock  (0) 2019.09.12

+ Recent posts

티스토리툴바