educational codeforces round 133

A. 2-3 Moves

 

문제 :

정수로 된 직선에서 초기에는 $0$의 위치에 있고 $n$의 위치까지 이동하려 한다. $2, 3$의 거리를 이동할 수 있을 때($+2, +3, -2, -3$) 최소 몇번의 움직임으로 갈 수 있을지를 알아보면 된다.($1\leq n\leq10^9$)

 

 

풀이 :

$n=1$일 때 : $2$번의 이동으로 갈 수 있다.

$n\geq 2$일 때 : $\lceil\frac{3}{n}\rceil$번의 이동으로 갈 수 있다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	if (n == 1) cout << 2;
	else cout << (int)ceil(n / 3.);
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);	
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

B. Permutation Chain

 

문제 :

$1$부터 $n$까지 각 원소가 한 번씩 등장하는 길이가 $n$인 수열이 있다. 수열의 $i$번째 원소를 $p_i$라 할 때 이 수열의 점수는 $1\leq i\leq n$인 $i$에 대하여 $p_i=i$인 개수이다. 수열의 맨 처음은 $a_1 = [1, 2, ..., n]$이고 여기서 임의의 두 원소를 바꿔 수열 $a_2$를 만들 수 있고 또 $a_2$에서 임의의 두 원소를 바꿔 $a_3$을 만들 수 있다. 이런 식으로 $a_1, a_2,  a_3, ...$를 만들 수 있다. $a_i$는 $a_{i-1}$보다 작은 값을 가져야 한다. 이때 $a_1, a_2, ...$를 최대로 구하면 된다.

 

 

풀이 :

수열의 개수가 최대가 되려면 점수의 감소량이 최소가 돼야 한다.

$a_1$에서는 점수가 $n$이고, $a_2$에서는 $a_1$에서 두 원소가 바뀌었으므로 점수가 $n-2$이다.

$a_i (i\geq3)$부터는 $a_{i-1}$에서 $p_i\neq i$인 원소하나 와 $p_i=i$인 원소를 바꿀 때마다 점수가 $1$씩 감소하므로 점수의 감소량을 최소로 할 수 있다. 수열의 점수가 $0$일 때까지 반복하면 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	cout << n << '\n';
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		v[i] = i + 1;
		cout << v[i] << ' ';
	}
	cout << '\n';
	for (int i = 1; i < n; i++) {
		swap(v[i - 1], v[i]);
		for (int it : v) cout << it << ' ';
		cout << '\n';
	}
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);	
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

C. Robot in a Hallway

 

문제 :

$2\times m$크기의 판이 있고 이 판을 움직일 수 있는 로봇은 초기에 $(1,1)$의 위치에 있다. 이 로봇은 상하좌우로 $1$만큼 움직일 수 있고 모든 칸을 한 번씩만 방문해서 모든 칸을 방문해야 한다. $2\times m$의 판에서 $(1,1)$을 제외한 각 칸들은 처음에 잠겨있다가 일정 시간이 지나면 열리는데 이 값은 $[0, 10^9]$의 값 중 하나이다. 열린 칸으로 만 이동할 수 있는 로봇이 모든 칸을 방문하려 할 때 최소의 시간을 구하면 된다.

 

---

 

D. Chip Move

 

문제 :

정수로 된 직선에서 현재 $0$의 위치에 있고 임의의 양의 정수 $k$에 대하여 처음에는 양의 방향으로 $k$의 배수$(\neq 0)$만큼 움직이고 그다음으로 $k+1$의 배수$(\neq 0)$만큼, 그 다음으로 $k+2$의 배수$(\neq 0)$만큼, ... 이런 식으로 움직일 때 $1$부터 $n$까지 각각 몇 가지 경우가 있는지를 알아보면 된다.

 

 

풀이 : 

$f_{i,j}$를 $i$개의 증가하는 $k$들의 합으로 만들 수 있는 $j$의 경우의 수라고 하면

$f_{1,j}$는 $k$의 배수이면 $1$, 아니면 $0$이고

$f_{i,j} = \sum_{m=1}^{}f_{i-1,j-m(k+i-1)}$이다.

이전의 값들을 $k+i-1$간격으로 누적합을 구하면 $m$번 반복하는 것을 한 번의 연산으로 해결할 수 있다.2차원 배열로 구현하면 메모리가 부족하기 때문에 점화식에서 현재의 상태를 구할 때 바로 이전의 상태만 필요하다는 것을 사용하여 1차원 배열 2개로 구현할 수 있다.

 

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
 
const int mod = 998244353;
 
void solve() {
	int n, k;
	cin >> n >> k;
 
	vector<int> ar(n + 1);
	vector<int> s(n + 1);
	vector<int> ans(n + 1, 0);
	int sum = k;
 
	s[0] = 1;
	for (int i = k; i <= n; i += k) s[i] = (s[i] + s[i - k]) % mod;
 
	for (int i = 1; sum <= n; i++) {
		for (int j = sum; j <= n; j++) {
			ar[j] = s[j - k];
			ans[j] = (ans[j] + ar[j]) % mod;
		}
 
		s = ar;
		fill(ar.begin(), ar.end(), 0);
		for (int j = sum + (++k); j <= n; j++) {
			s[j] = (s[j] + s[j - k]) % mod;
			ar[j] = s[j - k];
		}
		sum += k;
	}
 
	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
	return;	
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);	
	solve();
	return 0;
}

 

---

 

E. Swap and Maximum Block

 

문제 :

---

 

F. Bags with Balls

 

문제 :