codeforces round 816 (div.2)

A. Crossmarket

 

 

문제 :

$n\times m$크기의 판에 A, B가 있다. A는 $(1,1)$에서 $(n,m)$으로 가야 하고 B는 $(n,1)$에서 $(1,m)$으로 가야 한다. A, B는 처음에 각각 $(1,1)$, $(n,1)$의 위치에 있고 상하좌우로 $1$칸 움직이는데 $1$의 체력이 필요하다. B가 지나간 자리에는 포탈이 생기는데 만약 A, B가 포탈이 있는 칸에 있다면 포탈이 있는 칸 중 아무 곳이나 1의 체력으로 이동할 수 있다. 이때 A, B가 원하는 목적지까지 가는데 필요한 최소 체력을 구하면 된다.

 

 

풀이 :

B가 $(1,1)$로 올라간 뒤 $(1,m)$으로 간다고 하면 필요한 체력은 $(n-1) + (m-1)$이다.

A는 B가 지나간 경로에 있는 포탈을 사용해서 $(n,1)$이나 $(1,m)$으로 $1$의 체력으로 갈 수 있고 $(n,m)$으로 가면 되는데 $(n,1)$로 갔다면 $m-1$의 체력이 필요하고 $(1,m)$으로 갔다면 $n-1$만큼의 체력이 필요하다. 따라서 $n-1$과 $m-1$중 더 작은 값과 $(n-1) + (m-1)$의 값을 합하면 필요한 최소 체력을 알 수 있다.

만약 $n=m=1$이라면 A, B는 출발위치가 목적지와 같으므로 $0$이 답이된다.

 

 

코드 :

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

 

---

 

B. Beautiful Array

 

 

문제 :

길이가 $n$인 수열 $a$가 있고 각 원소는 음이 아닌 정수이다. $k,s,b$가 주어졌을 때 $\sum_{i=1}^na_i=s$이고 $\sum_{i=1}^n{\lfloor \frac{a_i}{k}\rfloor}=b$를 만족하는 수열 $a$를 구하면 된다. 만약 이런 경우가 불가능하면 $-1$이다.

 

 

풀이 :

$\lfloor\frac{a_i}{k}\rfloor=x$이면 $x\cdot k \leq a_i\leq x\cdot k + (k-1)$이다.

따라서 $k\cdot b\leq s\leq k\cdot b + n\cdot (k-1)$이라할 수 있고 이 조건을 만족하지 않으면 $a$를 만들 수 없다.($-1$)

가능한 경우이면 $\sum_{i=1}^n{\lfloor \frac{a_i}{k}\rfloor}=b$을 만족하기 위해 $a_1$을 $k\cdot b$라 하고 나머지 원소들에 $s-k\cdot b$를 분배해서 더해주면 된다. 이때 각 원소에 더할 수 있는 최댓값은 $k-1$이고($k$이상을 더하면 $s$보다 커지므로) 더할 값이 없다면 $0$으로 하면 된다.

 

 

코드 :

<hide/>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
void solve() {
	ll n, k, b, s;
	cin >> n >> k >> b >> s;
	if (k * b > s || k * b + n * (k - 1) < s) {
		cout << -1 << '\n';
		return;
	}
	else {
		ll temp = s - k * b;
		ll t = k - 1;
		if (temp < k - 1) t = temp;
		cout << k * b + t << ' ';
		temp -= t;
		for (int i = 1; i < n; i++) {
			if (temp > 0) {
				if (temp >= k - 1) cout << k - 1 << ' ';
				else cout << temp << ' ';
				temp -= (k - 1);
			}
			else cout << 0 << ' ';
		}
	}
	cout << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

C. Monoblock

 

 

문제 :

길이가 $n$인 수열 $a$가 있고 $a_i$의 값을 임의로 변경하는 연산이 $m$번 있다. 수열 $a$에 대해 함수 $g(l,r)$은 $l$부터 $r$까지 몇 번의 원소가 바뀌었는지와 그 값을 모두 더한 값이다. 예를 들어 $[1,2,2,4,5]$에서

$g(1,5)$의 값은 $1+2+2+3+4$,

$g(2,5)$는 $1+1+2+3$이런 식이다.

수열 $a$의 값을 $\sum_{i=1}^n{\sum_{j=1}^i{g(i,j)}}$라 했을 때 $m$개의 쿼리에 대한 수열의 값을 알아보면 된다.

 

---

 

D. 2+ doors