Round E - B(Birthday Cake)
27264 ワード
#include <bits/stdc++.h>
using namespace std;
int cut(int length, unsigned long long K) {
if(length%K == 0)
return length/K;
return length/K+1;
}
int main() {
int T;
scanf("%d", &T);
for(int tc = 1; tc <= T; tc++) {
int R, C;
unsigned long long K;
scanf("%d %d %llu", &R, &C, &K);
int r1, c1, r2, c2;
scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
unsigned long long result = 0;
if(r1 == 1 && c1 == 1 && r2 == R && c2 == C)
result += 0;
else if((r1 == 1 && c1 == 1 && r2 == R) || (r1 == 1 && r2 == R && c2 == C))
result += cut(R, K);
else if((r1 == 1 && c1 == 1 && c2 == C) || (c1 == 1 && r2 == R && c2 == C))
result += cut(C, K);
else if(r1 == 1 && r2 == R)
result += 2*cut(R,K);
else if(c1 == 1 && c2 == C)
result += 2*cut(C,K);
else if((r1 == 1 && c1 == 1) || (r1 == 1 && c2 == C) || (r2 == R && c2 == C) || (r2 == R && c1 == 1))
result += cut((c2-c1+1),K) + cut((r2-r1+1),K);
else if((r1 == 1) || (r2 == R))
result += cut((c2-c1+1),K) + 2*cut((r2-r1+1),K);
else if((c1 == 1) || (c2 == C))
result += 2*cut((c2-c1+1),K) + cut((r2-r1+1),K);
else {
int temp;
int mini = 1000000000;
temp = cut(c2,K) + cut((c2-c1+1),K) + 2*cut((r2-r1+1),K);
mini = temp < mini ? temp : mini;
temp = cut((C-c1+1),K) + cut((c2-c1+1),K) + 2*cut((r2-r1+1),K);
mini = temp < mini ? temp : mini;
temp = cut(r2,K) + 2*cut((c2-c1+1),K) + cut((r2-r1+1),K);
mini = temp < mini ? temp : mini;
temp = cut((R-r1+1),K) + 2*cut((c2-c1+1),K) + cut((r2-r1+1),K);
mini = temp < mini ? temp : mini;
result += mini;
}
unsigned long long W = c2-c1+1;
unsigned long long H = r2-r1+1;
unsigned long long wq = W/K;
unsigned long long wr = W%K;
unsigned long long hq = H/K;
unsigned long long hr = H%K;
if(wr == 0 && hr == 0)
result += (wq-1)*hq + (hq-1)*wq;
else if(wr == 0)
result += (wq-1)*(hq+1)+hq*(wq-1);
else if(hr == 0)
result += (hq-1)*(wq+1)+wq*(hq-1);
else
result += wq*(hq+1) + hq*(wq+1);
result += wq*hq*(K-1+K*(K-1));
if(wr != 0)
result += hq*(wr-1+wr*(K-1));
if(hr != 0)
result += wq*(hr-1+hr*(K-1));
if(wr != 0 && hr != 0) {
result += hr*wr-1;
}
printf("Case #%d: %llu\n", tc, result);
}
}
Reference
この問題について(Round E - B(Birthday Cake)), 我々は、より多くの情報をここで見つけました https://velog.io/@amxasm/Google-Kick-Start-2021-Round-E-BBirthday-Cakeテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol