---
tags: theme
title: CSES 解題筆記
description: Use `{%hackmd BkVfcTxlQ %}` syntax to include this theme.
---

<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

body > .ui-infobar {
display: none;
}

.ui-view-area > .ui-infobar {
display: block;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>

CSES 解題筆記
===

[Toc]

Introductory Problems
===

## [Weird Algorithm](https://cses.fi/problemset/task/1068/)
###### tags: `AC ratio 70111 / 73263`
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
Your task is to simulate the execution of the algorithm for a given value of n .
* Input
The only input line contains an integer n.
* Output
Print a line that contains all values of n during the algorithm.
* Constraints
1≤n≤10^6

int main(){
    ll a;
    cin>>a;
    cout<<a<<" ";
    if(a==1)return 0;
    while(a){
        if(a==1){
            break;
        }
        else if(a%2){
            cout<<a*3+1<<" ";
            a=a*3+1;
        }
        else {
            cout<<a/2<<" ";
            a/=2;
        }
    }
}

## [Missing Number ](https://cses.fi/problemset/task/1083)
###### tags: `AC ratio 59344 / 62789`
You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.
* Input
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).
* Output
Print the missing number.
* Constraints
2≤n≤2⋅10^5

int main(){
    ll a;
    cin>>a;
    vector<int> yoyo;
    for(int i=0;i<a-1;i++){
        ll k;
        cin>>k;
        yoyo.push_back(k);
    }    
    sort(yoyo.begin(),yoyo.end());
    for(int i=1;i<=a;i++){
        if(yoyo[i-1]!=i){
            cout<<i<<endl;
            break;
        }
    }
    yoyo.clear();
}

---

## [Repetitions](https://cses.fi/problemset/task/1069)
###### tags: `AC ratio 51800 / 54502`
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.
* Input
The only input line contains a string of n characters.
* Output
Print one integer: the length of the longest repetition.
* Constraints
1≤n≤10^6

int main(){
    AC
    string s;
    cin>>s;
    ll countt=1;
    ll nc=1;
    for(int i=1;i<(int)s.size();i++){
        if(s[i]-'0'==s[i-1]-'0')nc++;
        else{
            countt=max(countt,nc);
            nc=1;
        }
    }
    cout<<max(countt,nc)<<endl;
}

## [Increasing Array](https://cses.fi/problemset/task/1094)
###### tags: `AC ratio 48106 / 50288`
You are given an array of n integers. You want to modify thearray so that it is increasing, i.e., every element is at least as large as the previous element.
On each move, you may increase the value of any element by one. What is the minimum number of moves required?

* Input
The first input line contains an integer n: the size of the array.
Then, the second line contains n integers x1,x2,…,xn: the contents of the array.
* Output
Print the minimum number of moves.
* Constraints
1≤n≤2^ 10^5
1≤xi≤10^9

ll countt;
int main(){
	ll n;
	cin>>n;
	countt=0;
	ll last=0;
	for(int i=0;i<n;i++){
		ll k;
		cin>>k;
		if(i==0)last=k;
		else {
			if(k<last)countt+=last-k;
			else last=k;
		}
	}
	cout<<countt<<endl;
}

---

## [Permutations](https://cses.fi/problemset/task/1070)
###### tags: `AC ratio 42543 / 44021`
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.
* Input
The only input line contains an integer n.
* Output
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".
* Constraints
1≤n≤10^6

ll countt;
int main(){
	int n;
	cin>>n;
	if(n==1)cout<<"1"<<endl;
	else if(n<4)cout<<"NO SOLUTION"<<endl;
	else {
		for(int i=2;i<=n;i+=2)cout<<i<<" ";
		for(int i=1;i<=n;i+=2)cout<<i<<" ";
	}
	cout<<endl;
}

## [Number Spiral](https://cses.fi/problemset/task/1071)
###### tags: `AC ratio 29976 / 32688`
A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:
Your task is to find out the number in row y and column x.
* Input
The first input line contains an integer t: the number of tests.
After this, there are t lines, each containing integers y and x.
* Output
For each test, print the number in row y and column x.
* Constraints
1≤t≤10^5
1≤y,x≤10^9

int main(){
    int tc;
    ll x,y;
    cin >> tc;
    while (tc--){
        cin >>x>> y;
        if (x < y){
            if (y % 2 == 1){
                ll r = y * y;
                cout << r - x + 1 << endl;
            }
            else{
                ll r = (y - 1) * (y - 1) + 1;
                cout << r + x - 1 << endl;
            }
        }
        else{
            if (x % 2 == 0){
                ll r = x * x;
                cout << r - y + 1 << endl;
            }
            else{
                ll r = (x - 1) * (x - 1) + 1;
                cout << r + y - 1 << endl;
            }
        }
    }
    return 0;
}

## [Two Knights](https://cses.fi/problemset/task/1072)
###### tags: `AC ratio 22463 / 23245` `math`
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.
* Input
The only input line contains an integer n.
* Output
Print n integers: the results.
* Constraints
1≤n≤10000

int main(){
	ll k;
	cin>>k;
    for (ll n=1;n<=k;n++){
        cout<<n*n*(n*n-1)/2-4*(n-1)*(n-2)<<endl;
    }
    return 0;
}

## [Two Sets](https://cses.fi/problemset/task/1092)
###### tags: `AC ratio 24194 / 26239`
Your task is to divide the numbers 1,2,…,n into two sets of equal sum.
* Input
The only input line contains an integer n.
* Output
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.
* Constraints
1≤n≤10^6

bool ck[1000005];
int main(){
	ll n;
	cin>>n;
	if(((1+n)*n/2)%2)cout<<"NO"<<endl;
	else {
		vector<int> yoyo;
		cout<<"YES"<<endl;
		ll k=((1+n)*n/2)/2;
 
		for(ll i=n;i>=1;i--){
			if((k-i)>=0)ck[i]=1,yoyo.push_back(i),k-=i;		
		}
		cout<<(int)yoyo.size()<<endl;
		for(ll i=0;i<yoyo.size();i++){
			cout<<yoyo[i]<<" ";
		}
		cout<<endl;
		cout<<n-(int)yoyo.size()<<endl;
		for(int i=1;i<=n;i++){
			if(!ck[i])cout<<i<<" ";
		}
		cout<<endl;
		yoyo.clear();
	}
}

## [Bit Strings](https://cses.fi/problemset/task/1617)

###### tags: `AC ratio 28549 / 30172`
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.
* Input
The only input line has an integer n.
* Output
Print the result modulo 109+7.
* Constraints
1≤n≤10^6

int main(){
	int n;
	cin>>n;
	int ans=1;
	for(int i=0;i<n;i++){
		ans=(ans*2)%mod;
	}
	cout<<ans<<endl;
} 

## [Trailing Zeros](https://cses.fi/problemset/task/1618)
###### tags: `AC ratio 26787 / 28657`
Your task is to calculate the number of trailing zeros in the factorial n!.
For example, 20!=2432902008176640000 and it has 4
trailing zeros.
* Input
The only input line has an integer n.
* Output
Print the number of trailing zeros in n!.
* Constraints
1≤n≤10^9

int main(){
	int n;
	cin>>n;
	int ans=0;
	while(n){
		ans+=n/5;
		n/=5;
		
	}
	cout<<ans<<endl;
}
   

## [Coin Piles](https://cses.fi/problemset/task/1754)
###### tags: `AC ratio 23476 / 25950`
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.
* Input
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.
* Output
For each test, print "YES" if you can empty the piles and "NO" otherwise.
* Constraints
1≤t≤10^5
0≤a,b≤10^9

int main(){
	int t;
	cin>>t;
	while(t--){
		int a,b;
		cin>>a>>b;
		if((!a || !b)&& (a  || b))cout<<"NO"<<endl;
		else if((a>2*b)|| (b>2*a))cout<<"NO"<<endl;
		else {
			if((a+b)%3==0)cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}
	}
}

## [Palindrome Reorder](https://cses.fi/problemset/task/1755)
###### tags: `AC ratio 21227 / 22688`
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).
* Input
The only input line has a string of length n consisting of characters A–Z.
* Output
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".
* Constraints
1≤n≤10^6

int main() {
    string s;
    cin >> s;
 
    vector<int> a(26);
    for(char c : s) a[c - 'A']++;
    
    int check = 0;
    for(int i = 0; i < 26; i++) check += (a[i] % 2);
    //only one of the letters should be of odd frequency or all pair
    if(check > 1){
        cout << "NO SOLUTION";
        return 0;
    }
    //organize the palindrome
    string result;
    for (int i = 0; i < 26; i++){
        if(!(a[i]%2)){
            for(int j = 0; j < a[i]/2; j++) result.push_back(i + 'A');
        }
    }
    for (int i = 0; i < 26; i++){
        if(a[i]%2){
            for(int j = 0; j < a[i]; j++) result.push_back(i + 'A');
        }
    }
    for (int i = 25; i >= 0; i--){
        if(!(a[i]%2)){
            for(int j = 0; j < a[i]/2; j++) result.push_back(i + 'A');
        }
    }
 
    cout << result << endl;
    return 0;
}

## [Gray Code](https://cses.fi/problemset/task/2205)
###### tags: `AC ratio 12211 / 13941`
A Gray code is a list of all 2n bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).
Your task is to create a Gray code for a given length n.
* Input
The only input line has an integer n.
* Output
Print 2n lines that describe the Gray code. You can print any valid solution.
* Constraints
1≤n≤16

int n;
int x;
void print(){
	for(int i=n-1;i>-1;i--){
		if( (1<<i) & x)cout<<"1";
		else cout<<"0";
	}
	cout<<'\n';
}
int main(){
	cin>>n;
	for(int i=0;i<(1<<n);i++){
		print();
		if(i%2==0){
			x=x^1;
		}
		else{
		    for(int j=0;j<n;j++){
			if(x&(1<<j)){
				x=(1<<(j+1))^x;
				break;
			}
                    }
		}
	}
} 

## [Tower of Hanoi](https://cses.fi/problemset/task/2165)
###### tags: `AC ratio 11435 / 11951`
The Tower of Hanoi game consists of three stacks (left, middle and right) and n round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom.
The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk.
Your task is to find a solution that minimizes the number of moves.
* Input
The only input line has an integer n: the number of disks.
* Output
First print an integer k
: the minimum number of moves.
After this, print k lines that describe the moves. Each line has two integers a and b
: you move a disk from stack a to stack b.
* Constraints
1≤n≤16

vector< pair<int,int> > ans;
void hanoi(int x,int a,int b,int c){
	if(x==0)return;
	hanoi(x-1,a,c,b);
	ans.push_back({a,c});
	hanoi(x-1,b,a,c);
}
int main(){
	int n;
	cin>>n;
	hanoi(n,1,2,3);
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++){
		cout<<ans[i].first<<" "<<ans[i].second<<endl;
	}
}

## [Creating Strings](https://cses.fi/problemset/task/1622)
###### tags: `AC ratio 18450 / 19013`
Given a string, your task is to generate all different strings that can be created using its characters.
* Input
The only input line has a string of length n. Each character is between a–z.
* Output
First print an integer k: the number of strings. Then print k lines: the strings in alphabetical order.
* Constraints
1≤n≤8

void permutaion(int l,int r){
	if(l==r){
		se.insert(s);
		return;
	}
	for(int i=l;i<=r;i++){
		swap(s[l],s[i]);
		permutaion(l+1,r);
		swap(s[l],s[i]);
	}	
}
 
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>s;
	permutaion(0,(int)s.size()-1);
	cout<<(int)se.size()<<'\n';
	for(string yoyo:se)cout<<yoyo<<'\n';
}

## [Apple Division](https://cses.fi/problemset/task/1623)
###### tags: `AC ratio 17580 / 20234`
There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.
* Input
The first input line has an integer n: the number of apples.
The next line has n integers p1,p2,…,pn: the weight of each apple.
* Output
Print one integer: the minimum difference between the weights of the groups.
* Constraints
1≤n≤20
1≤pi≤10^9

ll n,t,min_all,min_loc;
vector<ll> a;
vector<ll> x;
 
void test(){
	ll px=0;
	min_loc=0;
	for(ll i=0;i<n;i++){
		if(px<x.size() && x[px]==i){
			min_loc+=a[i];
			px++;
		}
		else min_loc-=a[i];
	}
	min_all=min(abs(min_loc),min_all);
}
 
void solve(ll i){
	if(i==n){
		test();
		return;
	}
	solve(i+1);
	x.push_back(i);
	solve(i+1);
	x.pop_back();
}
 
int main(){
	min_all=10000000000;
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>t;
		a.push_back(t);
	}
	
	solve(0);
	cout<<min_all<<'\n';
}

## [Chessboard and Queens](https://cses.fi/problemset/task/1624)
###### tags: `AC ratio 10573 / 10796`
Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.
How many possible ways are there to place the queens?
* Input
The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).
* Output
Print one integer: the number of ways you can place the queens.

bool tkcols[8],tkdiag1[16],tkdiag2[16];
 
void try_place(string board[8],int now,int &ans){
	if(now==8){
		ans++;
		return;
	}
	for(int c=0;c<8;c++){
		if(board[now][c]=='.'){
			if(!tkcols[c] &&!tkdiag1[now-c+7]&&!tkdiag2[now+c]){
				tkcols[c]=1;
				tkdiag1[now-c+7]=1;
				tkdiag2[now+c]=1;
				try_place(board,now+1,ans);
				tkcols[c]=0;
				tkdiag1[now-c+7]=0;
				tkdiag2[now+c]=0;
			}
		}
	
	}
}
 
int main(){
	string board[8];
	for(int i=0;i<8;i++){
		cin>>board[i];
	}
	int ans=0;
	try_place(board,0,ans);
	
	cout<<ans<<endl;
	
}

## [Digit Queries](https://cses.fi/problemset/task/2431)
###### tags: `AC ratio 6597 / 8011`
Consider an infinite string that consists of all positive integers in increasing order:
12345678910111213141516171819202122232425...
Your task is to process q queries of the form: what is the digit at position k in the string?
* Input
The first input line has an integer q: the number of queries.
After this, there are q lines that describe the queries. Each line has an integer k: a 1-indexed position in the string.
* Output
For each query, print the corresponding digit.

int main(){
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		ll tens=1;
		ll sum=0;
		ll i=1;
		while(sum<n){
			sum+=i*9*tens;
			i++;
			tens*=10;
		}
		i--;
		tens/=10;
		sum-=i*9*tens;
		
		ll diff=n-sum;
		ll resnum=tens+(diff-1)/i;
		int resbit=(diff-1)%i;
		
		string s=to_string(resnum);
		cout<<(s[resbit]-'0')<<endl;
	}
}

## [Grid Paths](https://cses.fi/problemset/task/1625)
###### tags: `AC ratio 4395 / 5634`
There are 88418 paths in a 7×7
grid from the upper-left square to the lower-left square. Each path corresponds to a 48-character description consisting of characters D (down), U (up), L (left) and R (right).For example, the path:
corresponds to the description DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

You are given a description of a path which may also contain characters ? (any direction). Your task is to calculate the number of paths that match the description.

* Input
The only input line has a 48
-character string of characters ?, D, U, L and R.
* Output
Print one integer: the total number of paths.