소요시간 3시간
문제 요약
파이어볼을 부리는 상어가 명령을 K 번 했을 때, 남은 파이어볼의 질량을 구하자!
초기상태
- N*N 격자(N<50) 위에 파이어볼 M개를 뱉어두었다.
- 파이어볼들은 명령을 기다리고 있다.
환경
- 이 격자는 N번째 행과 1번째 행이 이어져있고 N번째 열과 1번째 열이 이어져있는 rollable구조이다.
- 파이어볼은 각자 방향(0-7로 표현)을 가지고 있다.
한 번의 명령에 일어나는 일
마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.
- 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
(이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.) - 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
2-1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
2-2. 파이어볼은 4개의 파이어볼로 나누어진다.
2-3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
2-4. 질량이 0인 파이어볼은 소멸되어 없어진다.
아이디어
정확한 시뮬레이션이 중요하다.
매 명령마다 2차원 배열을 돌면서 파이어볼이 존재할 때 요구하는 작업들을 해주면 된다.
주의할점 1 : rollable
rollable matrix에 대해 인덱싱을 잘 해주자!
- 양의 방향 : (현위치+방향*속력)%N
- 음의 방향 : ((현위치+방향*속력)%N)+N (양수랑 똑같이 한 뒤 한 세트를 앞에 놔주는 기분)
음수 mod N
- (N-1)~0의 값이 나온다. 양수범위로 변환하고 싶을 땐+N을 하자!
주의할점 2 : 나눠질 때의 속력
rollable이라고 처음에 속력들을 받아서 저장할 때 %N 처리를 해주었었다. 하지만 이렇게 하면 문제가 있는 게 파이어볼이 나뉘어진 자식들은 속력의 합/형제수라는 것이다. 속력의 합이 mod가 들어가버리면 똑같이 나오지 않는다.
예시 (N = 4)
위 아래 예시들의 파이어볼 A와 파이어볼 B는 똑같이 동작하지만 이들이 합쳐진 뒤 자식? 파이어볼의 속력은 다르다.
- 파이어볼 A : 속력 9, 파이어볼 B : 속력 10
=> 나뉘어진 파이어볼의 속력 = (9+10)/2 = 8
=> rollable하게 (0,0)자리에서 2번(0,1)방향으로 움직일 때 8%4 = 0 자리에서 멈춤 - 파이어볼 A : 속력 1, 파이어볼 B : 속력 2
=> 나뉘어진 파이어볼의 속력 = (1+2)/2 = 1
=> rollable하게 (0,0)자리에서 2번(0,1)방향으로 움직일 때 1%4 = 1 자리에서 멈춤
소스코드
#include<iostream>
#include<vector>
using namespace std;
int N, M, K;
struct fire {
int m, s, d;
fire(int mm, int ss, int dd) {
m = mm; s = ss; d = dd;
}
fire() {
m = 0; s = 0; d = 0;
}
};
struct pt {
int i, j;
pt(int ii, int jj) {
i = ii % N;
j = jj % N;
if (i < 0) {
i += N;
}
if (j < 0) {
j += N;
}
}
};
vector<fire> arr[50][50];
vector<fire> empty_arr[50][50];
int di[] = { -1,-1,0,1,1,1,0,-1 };
int dj[] = { 0,1,1,1,0,-1,-1,-1 };
int pd[] = { 0, 2, 4, 6 };
int upd[] = { 1, 3, 5, 7 };
int main() {
cin >> N >> M >> K;
int r, c, m, s, d;
for (int i = 0; i < M; i++) {
cin >> r >> c >> m >> s >> d;
arr[r-1][c-1].push_back(fire(m, s, d));
}
for (int ctr = 0; ctr < K; ctr++) {
vector<fire> temp[50][50];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < arr[i][j].size(); k++) {
fire cur = arr[i][j][k];
if (cur.m != 0) {
pt next_pt = pt(i + cur.s * di[cur.d], j + cur.s * dj[cur.d]);
temp[next_pt.i][next_pt.j].push_back(cur);
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
arr[i][j] = vector<fire>();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (temp[i][j].size() == 1) {
arr[i][j].push_back(temp[i][j][0]);
}
if (temp[i][j].size() >= 2) {
int sum_m = 0, sum_s = 0, sum_odd=0;
for (int k = 0; k < temp[i][j].size(); k++) {
sum_m += temp[i][j][k].m;
sum_s += temp[i][j][k].s;
if (temp[i][j][k].d % 2 == 1) {
sum_odd++;
}
}
int child_m = sum_m / 5, child_s = (sum_s / temp[i][j].size());
bool is_pure = (sum_odd == temp[i][j].size() || sum_odd == 0);
if (child_m != 0) {
for (int k = 0; k < 4; k++) {
int dir = (is_pure ? pd[k] : upd[k]);
fire child = fire(child_m, child_s, dir);
arr[i][j].push_back(child);
}
}
}
}
}
}
int sum_m = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < arr[i][j].size(); k++) {
sum_m += arr[i][j][k].m;
}
}
}
cout << sum_m << endl;
}