Như các bạn đã biết HotaVN là tập đoàn công nghệ lớn 'Nhất' Việt Nam CEO là Nguyễn Hoàng Sơn cao thủ tin học vàng CSLOJ hay top 1. Vâng và vừa rồi là một tràng giới thiệu không liên qua đến đề bài.
Đề bài:
Sơn hôm nay thấy trời đẹp liền mở shop khắp khu vực Sơn La với tiêu chí nhanh và chất. Bạn là một nhân viên quèn của HotaVN nhưng lại được giao nhiệu vụ không liên quan gì đến lĩnh vực của bạn. Đáng lẽ công việc này là của em gái sếp (karobot) nhưng bạn lại muốn cưới em gái sếp và chiếm tập đoàn nên bạn nhận công việc. Nhiệm vụ của bạn là: sếp bạn (Sơn) cho bạn một cái bản đồ khu vực sơn với độ phân giải là R x C, tại mỗi ô ta có 2 trạng thái là 0 và 1.Trạng thái 0 = chưa có cửa hàng của HotaVN
Trạng thái 1 = đã có cửa hàng của HotaVN
Và giờ bạn được xây thêm duy nhất một cửa hàng nữa để khoảng cách lớn nhất, ở bất kỳ ô nào có khoảng cách với cửa hàng gần nhất với nó là ngắn nhất
Input
dòng đầu tiên ghi số test (T), dòng thứ hai ghi 2 số R và C.
R dòng tiếp theo, ghi C số 0 hoặc 1 (Không có tứ tự khoảng cách)
Output
In ra số dòng tương ứng với T test. Mỗi dòng có dạng `Case #x: y` , trong đó `x` là chỉ số test, `y` là khoảng cách tối ưu được tối đa.
Limits
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
Test set :
1 ≤ R ≤ 10.
1 ≤ C ≤ 10.
Test set 2:
1 ≤ R ≤ 250.
1 ≤ C ≤ 250.
Sample
Input
3 3 3 101 000 101 1 2 11 5 5 10001 00000 00000 00000 10001
Output
Case #1: 1 Case #2: 0 Case #3: 2
In Sample Case #1, you get a minimum overall delivery time of 1 by building a new delivery office in any one of the five squares without a delivery office.
In Sample Case #2, all the squares already have a delivery office and so the minimum overall delivery time is 0. Note you have to add at most one delivery office.
In Sample Case #3, to get a minimum overall delivery time of 2, you can build a new delivery office in any of these squares: (2, 3), (3, 2), (3, 3), (3, 4), or (4, 3). Any other possibility results in a higher overall delivery time than 2.
Thuật full O(RC . Log(RC)), Bạn có thể tối ưu tối đa là O(RC) nhưng không cần tiết cho bài này
// _____ _ _ // / ____| | | (_) // | (___ ___ _ __ __| | ___ _ __ ______ _ _ // \___ \ / _ \| '_ \ / _` |/ _ \ '_ \ |_ / _` | | // ____) | (_) | | | | | (_| | __/ |_) | / / (_| | | // |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_| // | | // |_|#include <bits/stdc++.h> #define nmax 255 #define oo 10000000007 #define mod 1000000007 #define reset(x) memset(x, 0, sizeof x) #define F first #define S second #define sonin cin #define sonout cout #define debug(x) cout << "Loli -> " << #x << " : " << x << "\n" #define debugAry(x, a, b, y) for(int y = a; y<=b; y++) cout << #x << "[" << y << "]" << " -> " << x[y] << "\n" #define filename "" #define fileNX freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); #define fileN freopen(filename".inp", "r", stdin); #define fileX freopen(filename".out", "w", stdout); #define toiuuhoa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZ(a) (int) a.size() #define FOU(x,a,b) for (lli x=a;x<=b;x++) #define FOD(x,a,b) for (lli x=a;x>=b;x--) #define FOA(a,b) for(auto &a:b) #define ALLvec(a) a.begin(),a.end() #define REU(x,a,b) for (lli x=a;x<b;x++) #define RED(x,a,b) for (lli x=a;x>b;x--) #define AutoCinAry(a,b,x) for(int a = 1; a<=b; a++) cin >> x[i]; #define dembit1(x) __builtin_popcount(x) #define bit(x,i) ((x>>(i-1))&1ll) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1ll<<(i-1))) #define EL cout << "\n"; #define EX exit(0); #define Ary(x, i, j, a) x[(i - 1) * a + j] #define epsinon 1e-8 #define Son_onii_chan main #define times double stime = clock(); #define gettime cerr << "Time executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n"; using namespace std; typedef long long lli; typedef long double ldo; typedef double dou; typedef vector vi; typedef vector vvi; typedef pair<lli, lli> pii; typedef vector vpi; typedef deque dqll;
lli t, r, c; lli ary[nmax][nmax]; lli d[nmax][nmax]; lli dx[4] = {-1, 0, 1, 0}; lli dy[4] = {0, -1, 0, 1}; deque q;
bool isable(lli k){ lli n = 0; lli maxA = -r-c, maxB = -r-c, minA = r+c, minB = r+c; FOU(i,1,r){ FOU(i2,1,c){ if(d[i][i2] > k){ maxA = max(maxA, i + i2); maxB = max(maxB, i - i2); minA = min(minA, i + i2); minB = min(minB, i - i2); n++; } } } if(n == 0) return true; FOU(i,1,r){ FOU(i2,1,c){ lli A = i + i2, B = i - i2; if(d[i][i2] > 0 && max(max(abs(A - maxA), abs(B - maxB)), max(abs(A - minA), abs(B - minB))) <= k) return true; } } return false; } void MainProcess(){ sonin >> r >> c; FOU(i,1,r){ string pico = ""; sonin >> pico; FOU(i2,1,c){ ary[i][i2] = pico[i2-1] - '0'; if(ary[i][i2] == 1){ d[i][i2] = 0; q.push_back({i, i2}); } else d[i][i2] = -1; } } //BFS find dist lli maxd = 0; while(!q.empty()){ pii ga = q.front(); q.pop_front(); FOU(i,0,3){ lli ni = ga.F, nj = ga.S; ni += dx[i]; nj += dy[i]; if(ni < 1 || ni > r || nj < 1 || nj > c || d[ni][nj] != -1) continue; d[ni][nj] = d[ga.F][ga.S] + 1; q.push_back({ni, nj}); maxd = max(maxd, d[ni][nj]); } } //Binary search lli lt = 0, rt = maxd, ans = 0; while(lt<=rt){ lli mid = (lt+rt)/2; if(isable(mid)){ ans = mid; rt = mid - 1; } else lt = mid + 1; } sonout << ans; } int Son_onii_chan(){ //fileNX toiuuhoa sonin >> t; FOU(tup, 1, t){ sonout << "Case #" << tup << ": "; MainProcess(); EL } return 0; }
Tổng cộng 1 trả lời
Lại nữa há -.-? Em còn chưa gặp em gái anh bao h, loli à -.-?