Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "testlib.h"
- #include <bits/stdc++.h>
- using namespace std;
- string h[101],h1[101];
- bool bio[101][101];
- int n,m,k,r,s,se;
- int dx[]={1,0,-1,0,1,1,-1,-1};
- int dy[]={0,1,0,-1,-1,1,1,-1};
- bool ok(int i,int j)
- {
- return (i>=0 && j>=0 && i<n && j<m);
- }
- int countKnown()
- {
- int a=0;
- for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (h1[i][j]!='?') ++a;
- return a;
- }
- void dfs(int i,int j)
- {
- if (!ok(i,j)) return;
- if (bio[i][j]) return;
- if (h[i][j]=='*') return;
- bio[i][j]=1;
- h1[i][j]=h[i][j];
- if (h[i][j]!='0') return;
- for (int k=0;k<8;++k) dfs(i+dx[k],j+dy[k]);
- }
- bool close(int i,int j)
- {
- if (i==r && j==s) return 1;
- for (int k=0;k<8;++k) if ((i+dx[k])==r && (j+dy[k])==s) return 1;
- return 0;
- }
- int minCount()
- {
- int mo=0;
- for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (h[i][j]=='*') ++mo;
- return mo;
- }
- int main(int argc, char **argv){
- registerInteraction(argc, argv);
- n = inf.readInt(5, 40);
- m = inf.readInt(5, 40);
- k = inf.readInt(1, n*m/4);
- se = inf.readInt();
- char **ar=argv;
- ar[0][0]=se/256;
- ar[0][1]=se%256;
- registerGen(argc,ar,1);
- cout<<n<<' '<<m<<' '<<k<<endl;
- r = ouf.readInt(0,n-1);
- s = ouf.readInt(0,m-1);
- double lo=0.0001,hi=10000;
- bool found=0;
- for (int i=0;i<n;++i) for (int j=0;j<m;++j) h[i].push_back('.');
- while (!found)
- {
- double mid=(lo+hi)/2,c=clock();
- int su=0,ti=0;
- do
- {
- for (int i=0;i<n;++i) for (int j=0;j<m;++j)
- {
- if (close(i,j)) continue;
- if (rnd.next(1010101)%(int(n*m/sqrt(1+sqrt((i-r)*(i-r)+(j-s)*(j-s)))))<k*mid) h[i][j]='*';
- else h[i][j]='.';
- }
- su+=minCount();
- ++ti;
- }
- while (minCount()!=k && (clock()-c)/CLOCKS_PER_SEC<0.01);
- if (minCount()==k) found=1;
- if (su*1./ti<k) lo=mid;
- else hi=mid;
- }
- for (int i=0;i<n;++i) for (int j=0;j<m;++j)
- {
- if (h[i][j]=='*') continue;
- int a=0;
- for (int k=0;k<8;++k)
- {
- int i2=i+dx[k],j2=j+dy[k];
- if (!ok(i2,j2)) continue;
- if (h[i2][j2]=='*') ++a;
- }
- h[i][j]=a+'0';
- }
- for (int i=0;i<n;++i) for (int j=0;j<m;++j) h1[i].push_back('?');
- dfs(r,s);
- bool done=0;
- while (!done && countKnown()!=n*m)
- {
- for (int i=0;i<n;++i) cout<<h1[i]<<endl;
- int z=ouf.readInt();
- if (z==0) break;
- for (int i=0;i<z;++i)
- {
- int q=ouf.readInt();
- int w=ouf.readInt();
- ouf.readSpace();
- char th=ouf.readChar();
- if (th=='*')
- {
- if (h[q][w]!='*') done=1;
- else
- {
- h1[q][w]=h[q][w];
- dfs(q,w);
- }
- }
- else
- {
- if (h[q][w]=='*') done=1;
- else
- {
- h1[q][w]=h[q][w];
- dfs(q,w);
- }
- }
- }
- }
- cout<<(countKnown()*countKnown()*1.)/(n*m*sqrt(n*m))<<" points, "<<countKnown()<<" found."<<endl;
- quitp(_pc((countKnown()*countKnown()*1.)/(n*m*sqrt(n*m)))-16, "%d known things", countKnown());
- tout<<(countKnown()*countKnown()*1.)/(n*m*sqrt(n*m))<<endl<<countKnown()<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
