#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int INF=1e9+7, LIM=1e5+7, N=18; string S[N]; int odw[N], skok[N][LIM], prawo[N][LIM], lewo[N+1][LIM], sum[LIM], L, n, x, y; int nxt(int p, int k) { if(S[k][p/y]=='.') { if(prawo[k][p/y]*y-(p%y)>=x) return p; } if(p/y+1>=L) return INF; return skok[k][p/y+1]; } int prv(int l, int r, int k) { if(l>r) return -1; if(lewo[k][r/y]<l/y) return -1; return min((lewo[k][r/y]+1)*y, r+1); } bool check(vector<int>&V) { if(V.size()==n) return true; int pocz=0; if(V.size()) { pocz=V.back(); int lst=V.back(); rep(i, V.size()) { if(V[i]+x>lst) { pocz=max(pocz, prv(lst, V[i]+x-1, (int)V.size()-i+1)); lst=V[i]+x; } } } pair<int,int>mi1={INF, INF}, mi2={INF, INF}; rep(i, n) if(!odw[i]) { int a=nxt(pocz, i); if(a!=INF) { pair<int,int>p={a, i}; if(p<=mi1) { mi2=mi1; mi1=p; } else mi2=min(mi2, p); } } if(mi1.st<INF) { V.pb(mi1.st); odw[mi1.nd]=1; if(check(V)) return true; odw[mi1.nd]=0; V.pop_back(); } if(mi2.st<INF) { V.pb(mi2.st); odw[mi2.nd]=1; if(check(V)) return true; odw[mi2.nd]=0; V.pop_back(); } return false; } bool czy() { rep(i, n) { skok[i][L]=INF; for(int j=L-1; j>=0; --j) { skok[i][j]=skok[i][j+1]; if(prawo[i][j]*y>=x) skok[i][j]=j*y; } odw[i]=0; } vector<int>V; return check(V); } bool srt(pair<ll,ll>a, pair<ll,ll>b) { return a.st*b.nd<b.st*a.nd; } void solve() { cin >> n >> L; rep(i, n) cin >> S[i]; rep(i, L) sum[i]=0; rep(i, n) rep(j, L) if(S[i][j]=='.') ++sum[j]; rep(i, L) if(!sum[i]) { cout << -1 << '\n'; return; } rep(i, n) { rep(j, L+1) prawo[i][j]=0; for(int j=L-1; j>=0; --j) if(S[i][j]=='.' && sum[j]>1) prawo[i][j]=prawo[i][j+1]+1; } rep(i, n+1) { rep(j, L) lewo[i][j]=-1; rep(j, L) { if(j) lewo[i][j]=lewo[i][j-1]; if(sum[j]<=i) lewo[i][j]=j; } } int po=0, ko=L; while(po<ko) { int sr=(po+ko+1)/2; x=sr; y=1; if(czy()) po=sr; else ko=sr-1; } vector<pair<ll,ll>>U; U.pb({0, 1}); for(int i=2; i<=n; ++i) { for(int j=1; j<i; ++j) if(gcd(i, j)==1) U.pb({j, i}); } sort(all(U), srt); int calk=po; po=0; ko=(int)U.size()-1; while(po<ko) { int sr=(po+ko+1)/2; y=U[sr].nd; x=calk*y+U[sr].st; if(czy()) po=sr; else ko=sr-1; } y=U[po].nd; x=calk*y+U[po].st; cout << x << "/" << y << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int _=1; // cin >> _; while(_--) solve(); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int INF=1e9+7, LIM=1e5+7, N=18; string S[N]; int odw[N], skok[N][LIM], prawo[N][LIM], lewo[N+1][LIM], sum[LIM], L, n, x, y; int nxt(int p, int k) { if(S[k][p/y]=='.') { if(prawo[k][p/y]*y-(p%y)>=x) return p; } if(p/y+1>=L) return INF; return skok[k][p/y+1]; } int prv(int l, int r, int k) { if(l>r) return -1; if(lewo[k][r/y]<l/y) return -1; return min((lewo[k][r/y]+1)*y, r+1); } bool check(vector<int>&V) { if(V.size()==n) return true; int pocz=0; if(V.size()) { pocz=V.back(); int lst=V.back(); rep(i, V.size()) { if(V[i]+x>lst) { pocz=max(pocz, prv(lst, V[i]+x-1, (int)V.size()-i+1)); lst=V[i]+x; } } } pair<int,int>mi1={INF, INF}, mi2={INF, INF}; rep(i, n) if(!odw[i]) { int a=nxt(pocz, i); if(a!=INF) { pair<int,int>p={a, i}; if(p<=mi1) { mi2=mi1; mi1=p; } else mi2=min(mi2, p); } } if(mi1.st<INF) { V.pb(mi1.st); odw[mi1.nd]=1; if(check(V)) return true; odw[mi1.nd]=0; V.pop_back(); } if(mi2.st<INF) { V.pb(mi2.st); odw[mi2.nd]=1; if(check(V)) return true; odw[mi2.nd]=0; V.pop_back(); } return false; } bool czy() { rep(i, n) { skok[i][L]=INF; for(int j=L-1; j>=0; --j) { skok[i][j]=skok[i][j+1]; if(prawo[i][j]*y>=x) skok[i][j]=j*y; } odw[i]=0; } vector<int>V; return check(V); } bool srt(pair<ll,ll>a, pair<ll,ll>b) { return a.st*b.nd<b.st*a.nd; } void solve() { cin >> n >> L; rep(i, n) cin >> S[i]; rep(i, L) sum[i]=0; rep(i, n) rep(j, L) if(S[i][j]=='.') ++sum[j]; rep(i, L) if(!sum[i]) { cout << -1 << '\n'; return; } rep(i, n) { rep(j, L+1) prawo[i][j]=0; for(int j=L-1; j>=0; --j) if(S[i][j]=='.' && sum[j]>1) prawo[i][j]=prawo[i][j+1]+1; } rep(i, n+1) { rep(j, L) lewo[i][j]=-1; rep(j, L) { if(j) lewo[i][j]=lewo[i][j-1]; if(sum[j]<=i) lewo[i][j]=j; } } int po=0, ko=L; while(po<ko) { int sr=(po+ko+1)/2; x=sr; y=1; if(czy()) po=sr; else ko=sr-1; } vector<pair<ll,ll>>U; U.pb({0, 1}); for(int i=2; i<=n; ++i) { for(int j=1; j<i; ++j) if(gcd(i, j)==1) U.pb({j, i}); } sort(all(U), srt); int calk=po; po=0; ko=(int)U.size()-1; while(po<ko) { int sr=(po+ko+1)/2; y=U[sr].nd; x=calk*y+U[sr].st; if(czy()) po=sr; else ko=sr-1; } y=U[po].nd; x=calk*y+U[po].st; cout << x << "/" << y << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int _=1; // cin >> _; while(_--) solve(); } |