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

문제 설명

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes any number of sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

입력 

The first input line contains an integer tt: the number of tests. After this, tt test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x_1, x_2, ... , x_n : the number of sticks in each heap.

출력

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

입력 예

3
4
5 7 2 5
2
4 1
3
3 5 6

출력 예

first
first
second

제약조건

  • 1 <= t <= 2*1e5
  • 1 <= n <= 2*1e5
  • 1 <= x_i <= 1e9
  • the sum of all n is at most 2*1e5

 

문제 풀이

Game Theory 에 나오는 Nim Game 

Nim Sum 을 계산해서, 0인 경우는 나중에 하는 플레이어가 이기게 되고 0이 아닌 경우는 먼저하는 플레이어가 이기는 승리전략이 존재한다. 따라서, 문제에서 플레이어가 이 전략을 알고 거기에 따라서 행동하기 때문에 Nim Sum을 계산하면 답을 찾을 수 있다. Nim Sum은 이진수로 표현했을때 각 자리수의 1들을 2개씩 짝지을 수 있으면 0 없으면 1로 계산하는 것이다. 즉, 값들을 bit XOR 를 하면 Nim Sum을 얻을 수 있다.

프로그램 내용

더보기 
/// Nim sum == XOR values
...
	int tN, ret = 0;
	cin >> tN;

	for(int id=0; id<tN;++id)	
    	int tmp;
		cin >> tmp;

		ret ^= tmp;
...

 

7. Mathematics ( link )

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

'CSES' 카테고리의 다른 글

CSES 4. Graph Algorithms  (0) 2020.01.13
CSES 7. Nim Game II (1098)  (0) 2020.01.05
CSES 7. Mathematics  (0) 2020.01.01
CSES 7. Stair Game(1099)  (0) 2020.01.01
CSES 3. Array Description (1746)  (0) 2019.12.31

USACO Training Site problems ( link )

 

Section 6.1  All tasks 
section 6.1.1 PROB Postal Vans 
section 6.1.2 PROB A Rectangular Barn 
section 6.1.1 PROB Cow XOR 

Section 6.2  All tasks 
section 6.2.1 PROB Calf Flac 
section 6.2.2 PROB Packing Rectangles 
section 6.2.3 PROB Shaping Regions 

Section 6.3 All tasks 
section 6.3.1 PROB Fence Rails 
section 6.3.2 PROB Cryptcowgraphy 

Section 6.4 All tasks 
section 6.4.1 PROB The Primes 
section 6.4.2 PROB Electric Fences 
section 6.4.3 PROB Wisconsin Squares 

Section 6.5 All tasks  
section 6.5.1 PROB All Latin Squares 
section 6.5.2 PROB Closed Fences 
section 6.5.3 PROB Betsy's Tour 
section 6.5.4 PROB The Clocks 
section 6.5.5 PROB Checker Challenge 

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

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

Problem 1.2.5 Greedy Gift Givers - 2  (0) 2021.01.03
Problem 2.1.6 Healthy Holsteins  (0) 2020.02.11
USACO Training - Chapter 5. Serious challenges  (0) 2020.01.01
USACO Training - Chapter 4. Advanced algorithms and difficult drills  (0) 2020.01.01
USACO Training - Chapter 3. Techniques more subtle  (0) 2020.01.01

USACO Training Site problems (link)

 

Chapter 5  Serious challenges
Section 5.1 Convex Hulls 
section 5.1.1 TEXT Convex Hulls
section 5.1.2 PROB Fencing the Cows 
section 5.1.3 PROB Starry Night 
section 5.1.4 PROB Musical Themes 

Section 5.2 All tasks 
section 5.2.1 PROB Snail Trail 

Section 5.3 Heuristics 
section 5.3.1 TEXT Heuristics & Approximate Searches
section 5.3.2 PROB Milk Measuring 
section 5.3.3 PROB Window Area 
section 5.3.4 PROB Network of Schools 
section 5.3.5 PROB Big Barn 

Section 5.4 All tasks
section 5.4.1 PROB Canada Tour 
section 5.4.2 PROB Character Recognition 
section 5.4.3 PROB TeleCowmunication 

Section 5.5 All tasks 
section 5.5.1 PROB Picture 
section 5.5.2 PROB Hidden Passwords 
section 5.5.3 PROB Two Five 

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

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

Problem 2.1.6 Healthy Holsteins  (0) 2020.02.11
USACO Training - Chapter 6. Contest Practice  (0) 2020.01.01
USACO Training - Chapter 4. Advanced algorithms and difficult drills  (0) 2020.01.01
USACO Training - Chapter 3. Techniques more subtle  (0) 2020.01.01
Problem 1.4.6 Combination Lock - 2  (0) 2019.10.13

USACO Training Site problems (link)

 

Chapter 4. Advanced algorithms and difficult drills

Section 4.1 Optimization
section 4.1.1 Optimization Techniques
section 4.1.2 PROB Beef McNuggets 
section 4.1.3 PROB Fence Loops 

Section 4.2 Network Flow
section 4.2.1 TEXT "Network Flow" Algorithms
section 4.2.2 PROB Drainage Ditches 
section 4.2.3 PROB The Perfect Stall 
section 4.2.4 PROB Job Processing 

Section 4.3 Bignums 
section 4.3.1 TEXT Big Numbers
section 4.3.2 PROB Buy Low, Buy Lower 
section 4.3.3 PROB Street Race 
section 4.3.4 PROB Letter Game 

 

Section 4.4  All tasks 
section 4.4.1 PROB Shuttle Puzzle 
section 4.4.2 PROB Pollutant Control 
section 4.4.3 PROB Frame Up 

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

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

USACO Training - Chapter 6. Contest Practice  (0) 2020.01.01
USACO Training - Chapter 5. Serious challenges  (0) 2020.01.01
USACO Training - Chapter 3. Techniques more subtle  (0) 2020.01.01
Problem 1.4.6 Combination Lock - 2  (0) 2019.10.13
Problem 1.5.3 Mother's Milk  (0) 2019.10.12

USACO Training Site problems ( link )

 

Chapter 3 Techniques more subtle

Section 3.1 Spanning Trees
section 3.1.1 TEXT Minimal Spanning Trees
section 3.1.2 PROB Agri-Net
section 3.1.3 PROB Score Inflation
section 3.1.4 PROB Humble Numbers
section 3.1.5 PROB Contact
section 3.1.6 PROB Stamps

Section 3.2 Knapsack
section 3.2.1 TEXT Knapsack Problems
section 3.2.2 PROB Factorials
section 3.2.3 PROB Stringsobits 
section 3.2.4 PROB Spinning Wheels
section 3.2.5 PROB Feed Ratios 
section 3.2.6 PROB Magic Squares 
section 3.2.7 PROB Sweet Butter 


Section 3.3 Eulerian Tours
section 3.3.1 TEXT Eulerian Tours
section 3.3.2 PROB Riding The Fences 
section 3.3.3 PROB Shopping Offers 
section 3.3.4 PROB Camelot 
section 3.3.5 PROB Home on the Range 
section 3.3.6 PROB A Game 

Section 3.4 Computational Geometry
section 3.4.1 TEXT Computational Geometry
section 3.4.2 PROB American Heritage 
section 3.4.3 PROB Electric Fence 
section 3.4.4 PROB Raucous Rockers 

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

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

USACO Training - Chapter 5. Serious challenges  (0) 2020.01.01
USACO Training - Chapter 4. Advanced algorithms and difficult drills  (0) 2020.01.01
Problem 1.4.6 Combination Lock - 2  (0) 2019.10.13
Problem 1.5.3 Mother's Milk  (0) 2019.10.12
Problem 2.3.4 Money Systems  (0) 2019.10.11

Mathematics

  1. Josephus Queries
  2. Exponentiation  (0)
  3. Exponentiation II  (0)
  4. Counting Divisors
  5. Common Divisors
  6. Sum of Divisors
  7. Divisor Analysis
  8. Prime Multiples
  9. Counting Coprime Pairs
  10. Binomial Coefficients
  11. Creating Strings II
  12. Distributing Apples
  13. Christmas Party
  14. Bracket Sequences I
  15. Bracket Sequences II
  16. Counting Necklaces
  17. Counting Grids
  18. Fibonacci Numbers
  19. Throwing Dice
  20. Graph Paths I
  21. Graph Paths II
  22. Dice Probability
  23. Moving Robots
  24. Candy Lottery
  25. Inversion Probability
  26. Stick Game  (1)
  27. Nim Game I  (1)
  28. Nim Game II  (1)
  29. Stair Game  (1)
  30. Grundy's Game
  31. Another Game 

 

CSES Problem Set 소개 ( link )

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

'CSES' 카테고리의 다른 글

CSES 7. Nim Game II (1098)  (0) 2020.01.05
CSES 7. Nim Game I (1730)  (0) 2020.01.05
CSES 7. Stair Game(1099)  (0) 2020.01.01
CSES 3. Array Description (1746)  (0) 2019.12.31
CSES 3. Book Shop (1158)  (0) 2019.12.28

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

문제 설명

You know that an array has n integers between 1 and m, and the difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

입력  

The first input line has two integers n and mm: the array size and the upper bound for each value.

The next line has n integers x_1,x_2,…,x_n : the contents of the array. Value 0 denotes an unknown value.

출력 

Print one integer: the number of arrays modulo 10^9+7.

입력 예

3 5
2 0 2

출력 예

3

Explanation: [2,1,2], [2,2,2] , and [2,3,2]

제약조건

  • 1 <= N <= 10^5
  • 1 <= M <= 100
  • 0 <= x_i <= M 

문제 풀이 

배열에서 어떤 위치의 숫자는 바로 전 위치의 숫자 값에 따라서 결정된다(+1, -1, 0). 이렇게 가능한 경우의 배열을 x_0 부터 x_n-1까지 계속해서 더해서 만든다. 단, 이렇게 더하는 과정에 커지는 숫자는 modulo 연산으로 일정하게 만든다.

프로그램 내용

더보기 
...
for (int i = 1; i < n; i++)
{
	if( x_i == 0 )	/// update all possible numbers 
	{
		for (int j = 1; j <= m; j++)
		{
			k = min(1, j);
			dp[i][k] += (dp[i-1][k-1] + dp[i-1][k] + dp[i-1][k+1]) % MOD;
		}
	}
	else	/// update x_i
	{
		dp[i][x_i] += (dp[i-1][x_i-1] + dp[i-1][x_i] + dp[i-1][x_i+1]) % MOD;
	}
}
...

 

Dynamic Programming ( link )

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

'CSES' 카테고리의 다른 글

CSES 7. Mathematics  (0) 2020.01.01
CSES 7. Stair Game(1099)  (0) 2020.01.01
CSES 3. Book Shop (1158)  (0) 2019.12.28
CSES 3. Grid Paths (1638)  (0) 2019.12.28
CSES 2. Sliding Cost (1077)  (0) 2019.12.28

출처: https://cses.fi/problemset/1158

문제 설명

You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

입력 

N X // Number of books, maximum total price

h_i // books price

s_i // number of pages

 

출력

the maximum number of pages.

입력 예 

4 10
4 8 5 3
5 12 8 1

출력 예

13

제약조건

  • 1<= N <= 1000
  • 1<= X <= 1e5
  • 1<= h_i, s_i <= 1000 

문제 풀이 내용

Knapsack 문제이다. 어떤 특정한 책을 선택했을 때 페이지와, 그 책을 고르지 않았을 경우에 얻을 수 있는 페이지의 최대값을 비교해서 큰 값을 선택하도록 한다.

프로그램 내용

더보기 
...
    vector<int> pr(n,0);
    vector<int> pg(n,0);
    vector<int> dp(x+1,0);
...
    for (int i = 0; i < n; i++) 
        for (int j = x; j >= 1; j--) 
            if (pr[i] <= j) 
                dp[j] = max(dp[j], dp[j - pr[i]] + pg[i]); 
...

 

Dynamic Programming ( link )

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

'CSES' 카테고리의 다른 글

CSES 7. Stair Game(1099)  (0) 2020.01.01
CSES 3. Array Description (1746)  (0) 2019.12.31
CSES 3. Grid Paths (1638)  (0) 2019.12.28
CSES 2. Sliding Cost (1077)  (0) 2019.12.28
CSES 2. Sliding Median (1076)  (0) 2019.12.25

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

문제 설명

Consider an N x N grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square where you only can move right or down.

입력  

First line: N /// grid size

N line : grid information ( . : empty cell, * : trap)

출력

Print the number of paths modulo 1e9 + 7

입력 예

4
....
.*..
...*
*...

출력 예

3

제약조건

1 <= N <= 1000

문제 풀이 내용

어떤 특정한 cell ( path[i][j] ) 까지 도착하는 경로는 왼쪽에서 온 경우( path[i-1][j])와 위쪽에서 온 경우(path[i][j-1])의 합으로 결정된다. 제일 처음 출발하는 cell부터 목표로 하는 cell 까지 cell이 trap(*)인 경우는 제외하고 더해서 만들어 간다. 

프로그램 내용

더보기 
...
    vector <string> maze(n+1);
    for (int i = 1; i <= n; i++)
        string tmp;
        maze[i] = "."+tmp;

    vector <vector<int>> path(n+1, vector<int>(n+1));

    path[1][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (maze[i][j] == '.')
                path[i][j] = (path[i-1][j]+path[i][j-1]) % M;
...

 

Dynamic Programming ( link )

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

'CSES' 카테고리의 다른 글

CSES 3. Array Description (1746)  (0) 2019.12.31
CSES 3. Book Shop (1158)  (0) 2019.12.28
CSES 2. Sliding Cost (1077)  (0) 2019.12.28
CSES 2. Sliding Median (1076)  (0) 2019.12.25
CSES 3. Removing Digits (1637)  (0) 2019.10.14

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

문제 설명

You are given an array of n integers. Your task is to calculate for each window of k elements, from left to right, the minimum total cost of making all elements equal.

You can increase or decrease each element with cost x where x is the difference between the new and the original value. The total cost is the sum of such costs.

입력 

The first input line contains two integers n and k: the number of elements and the size of the window.

Then there are n integers x_1,x_2,…,x_n: the contents of the array.

출력  

Output n−k+1 values: the costs.

입력 예

8 3
2 4 3 5 8 1 2 1

출력 예

2 2 5 7 7 1

제약조건

  • 1 <= k  <= n <= 2x10^5
  • 1 <= x_i <= 10^9

문제 풀이 내용

중간값을 출력하는 문제의 확장이다. 다만, 이경우에 윈도우를 움직일때마다 새롭게 변경되는 중간값과 그것을 기준으로 하는 비용을 다시 계산하면, 시간제한에 걸린다. 

바로 직전의 중간값과 비용을 저장하고 있다가, 새로 변경되는 부분만큼만 비용을 갱신하는 방법을 사용한다.

프로그램 내용

더보기 
...
    vector<long> num_arr(tN + 1);

    for (int id = 1; id <= tN; ++id)
        cin >> num_arr[id];

	long cost = 0;
    long old_med = 0;
    long med = 0;

    if (tK == 1) 
        for (int id = 1; id <= tN; ++id)
            cout << 0 << " ";
    else
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> lpq;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> rpq;

        long mid = (tK + 1) / 2;
        int w_size = 0;
        for (int id = 1; id <= tN ; ++id) 
            while (!lpq.empty() && lpq.top().second <= id - tK) lpq.pop();
            while (!rpq.empty() && rpq.top().second <= id - tK) rpq.pop();

            if (w_size < mid) 
                rpq.push(make_pair(num_arr[id], id));
                auto tmp = rpq.top();
                rpq.pop();
                lpq.push(tmp);
                ++w_size;
            else 
                lpq.push(make_pair(num_arr[id], id));
                auto tmp = lpq.top();
                lpq.pop();
                rpq.push(tmp);

            while (!lpq.empty() && lpq.top().second <= id - tK) lpq.pop();
            while (!rpq.empty() && rpq.top().second <= id - tK) rpq.pop();

            if (id == tK) 
                old_med = lpq.top().first;
                for (int idn = 1; idn <= tK; ++idn) 
                    cost += abs(num_arr[idn] - old_med);
            else if (id > tK)  
                med = lpq.top().first;

                cost = cost + abs(med - num_arr[id]) - abs(old_med - num_arr[id - tK]);

                if (tK % 2 == 0) cost -= (med - old_med);

                old_med = med;
            else 
                continue;
            if (num_arr[id - tK + 1] <= lpq.top().first) --w_size;
...

 

Sorting and Searching ( link )

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

'CSES' 카테고리의 다른 글

CSES 3. Book Shop (1158)  (0) 2019.12.28
CSES 3. Grid Paths (1638)  (0) 2019.12.28
CSES 2. Sliding Median (1076)  (0) 2019.12.25
CSES 3. Removing Digits (1637)  (0) 2019.10.14
CSES 3. Coin Combinations II (1636)  (0) 2019.10.10

+ Recent posts

티스토리툴바