Từ thế kỷ trước, IOI đã có bài tương tác. Dù gần đây các kỳ thi dưới tỉnh选 ít gặp, năm 2019 loạt NOI liên tiếp出现 hai bài tương tác: 《P5208[WC2019]I 君的商店》 và 《P5473[NOI2019]I 君的探险》, có thể cho thấy bài tương tác quay lại.
Bài tương tác không đòi thuật toán tiền đề cao, thường cũng không có giới hạn thời gian nghiêm ngặt, chất lượng chương trình chủ yếu phụ thuộc số lần tương tác. Vì vậy nên học theo độ难 tăng dần. Nếu muốn rèn tư duy thuật toán, làm bài tương tác là cách tốt. Dù yêu cầu thuật toán không cao, vẫn建议 học thuật toán mức提高 và省选 trước rồi mới做, vì lúc đó tư duy và kiến thức đủ. Giới thiệu cơ bản có thể xem OI Wiki题型介绍 - 交互题.
Lỗi đặc thù của tương tác:
Sau mỗi output phải flush,否则 gây Idleness limit exceeded. Nếu nhiều test và có thể biết đáp án trước khi đọc hết input,仍 phải đọc hết dữ liệu,否则 cũng gây ILE (có thể hỏi nhiều lần, nhận trả lời một lần). Đồng thời尽量不要用 fast input.
Nếu truy vấn quá nhiều, Codeforces cho WA (và nêu原因); UVa cho Protocol Limit Exceeded (PLE).
Nếu format tương tác sai, UVa cho Protocol Violation (PV).
Vì I/O tương tác rườm rà,建议 bọc hàm nhập/xuất riêng.
Trong thi nếu ra đề cung cấp header grader (cho grader debug) hoặc checker (cho stdio debug), việc debug dễ hơn; vì đối拍 bài tương tác khó hơn nhiều so với bài thường. Không có testlib.h thì库 stdio tương tác với nhiều细节 thường dài 3k dòng, cộng đối拍 3k dòng,至少 cần 1 giờ. Dù có hay không có工具, debug tương tác thường phải mô phỏng tương tác; nên thí sinh cần thiết kế chương trình chất lượng cao,尽量 một lần đúng, và có khả năng rà lỗi tĩnh tốt.
Mỗi số nguyên tố chỉ có hai ước, nên ta trực tiếp liệt kê ước của số cần đoán. Do chỉ được hỏi 20 lần, và với số lớn (như 92) phân tích cần liệt kê tới \(\lfloor\frac{n}{2}\rfloor\) số nguyên tố, nên ta sàng các số nguyên tố ≤ 50 và hỏi lần lượt.
Đối拍 dễ, có thể thử toàn bộ giá trị trong miền. Sẽ发现 chương trình không xử lý tốt平方 của số nguyên tố. Vì vậy thêm 4,9,25,49 (bình phương của 2,3,5,7), tổng 19 số, đúng đề.
Danh sách liên kết最多 \(5 \times 10 ^ 4\) phần tử, chỉ được hỏi 1999 lần và chỉ biết node tiếp theo, nên không thể duyệt toàn bộ. Cách duy nhất là rải điểm ngẫu nhiên.
Với \(n < 2000\) thì liệt kê, với \(n \ge 2000\) thì rải 1000 điểm. Khi đó khoảng cách kỳ vọng nhỏ, ta bắt đầu từ giá trị lớn nhất < \(x\) và duyệt; có thể chứng minh sẽ gặp答案 trước khi chạm điểm tiếp theo. Trong quá trình duyệt,遇到 ≥ \(x\) là ra答案.
Ý tưởng đơn giản nhưng nếu chưa học các kỹ thuậtRandom không hoàn hảo như mô phỏng annealing, sẽ khá khó nghĩ.
Vì Codeforces có hack, nhiều người故意卡 code không init seed, nên trước random_shuffle() cần srand((size_t)new char).
Lần truy vấn đầu: chưa biết gì nên hỏi \([1, 10 ^ {18}]\) để lấy min/max.
Vì số truy vấn giới hạn \(\frac{N + 1}{2}\), ta cần mỗi lần lấy giá trị chưa lấy. Cách đơn giản: hỏi \([s,t]\) nhận \(mn, mx\), lần sau hỏi \([mn+1, mx-1]\).
Giới hạn độ dài đoạn hỏi.
Vì tổng số phần tử trong các đoạn hỏi không vượt \(3N\), nên cần tối thiểu hóa đoạn hỏi. Cách trên không còn dùng vì tổng规模 \(O(N^2)\). Có thể nghĩ đến nhị phân giá trị, nhưng không可靠, worst-case vẫn \(O(N^2)\). Cần chia miền giá trị hiệu quả để tránh hỏi trùng.
Nhận xét: đáp án ≥ \(\lfloor\frac{a_n - a_1}{N - 1}\rfloor\). Ta chia miền theo giá trị này: đặt \(i\) ban đầu 0, \(ans\) là giá trị trên, mỗi lần hỏi \([i, i+ans]\) và cập nhật \(ans\), rồi tăng \(i\) theo bước \(ans\).
Cách này không phù hợp subtask 1 vì có thể nhiều đoạn không có số nào.
Vì \(h \le 7\) và giới hạn 16 truy vấn nghiêm, cần tận dụng tối đa thông tin.
\(h \le 4\) có thể vét cạn. Khi \(h > 4\) cần thuật toán duyệt hiệu quả.
Rải điểm ngẫu nhiên không tốt vì không biết是否 đủ gần gốc, và xác suất碰到根 rất nhỏ.
Do \(1 \le k \le 3\) và không biết hướng nào gần gốc, xét worst-case: nếu \(k=3\), hai lần đầu đi xa gốc, lần thứ ba mới gần gốc. Vì vậy phải duyệt theo ba hướng.
Xét BFS và DFS; BFS có cây tìm kiếm lớn, ưu先 DFS. Nếu biết độ sâu hiện tại nhỏ và cây BFS trong phạm vi số truy vấn còn lại, có thể BFS.
Biết độ sâu vàDirection sẽ có ưu thế, nhưng biết đang đi về gốc hay về lá rất khó. Nếu DFS, chỉ khi đến gốc (\(k=2\)) hoặc lá (\(k=1\)) mới biết hướng. Vì vậy cần尽量 biết độ sâu hiện tại và không dùng迭代加深, tránh dừng giữa chừng.
Chọn ngẫu nhiên một节点 bắt đầu có thể rơi vào worst-case.
Nếu \(k=1\), ta biết độ sâu.
Nếu \(k=2\),当前就是根.
Nếu \(k=3\), ta DFS theo ba hướng. Hai hướng là về lá (độ dài đường đi giống nhau), một hướng về gốc nhưng có thể走错 về lá,路径更长. Khi đó có thể tính độ sâu.
Khi \(k=1\) hoặc \(k=3\), đường đi dài. Ta biếtNodes có độ sâu nhỏ nhất trên路径 (nhỏ hơn điểm bắt đầu). Nếu đánh dấu已访问, từ nodes đó chỉ còn mộtDirection, dù có thể vẫn走向叶, trên path vẫn có nodes có độ sâu nhỏ hơn; ta lặp lại步骤.
Xét worst-case \(h=7\) (mỗi lần chỉ về gốc 1 bước rồi về lá), DFS đơn thuần cần \(\frac{(1 + 7) \times 7}{2} = 28\) truy vấn. Nhưng đã biết độ sâu ban đầu, có thể算 ra深度 của已访问 nodes và决定是否 BFS từ nodes depth nhỏ nhất.
Khi đó, worst-case cần 17. Ta có thể减少 1 truy vấn: trong BFS sâu \(k\), cây có \(2^k-1\) nodes, cần \(2^k-1\) truy vấn để确定 nodes có 2 neighbors. Nhưng nếu已经问了 \(2^k-2\) nodes,最后一个 node必是根.
Vì phản hồi duy nhất là có撞墙 hay không, nên尽量 đi sát tường để:
Dễ biết có撞墙 không,获取更多信息.
Các ô sát tường không có portal, tránh机器人走丢.
Nếu已知 robot có thể ở một vị trí sát tường, có thể dùng “đi theo tường một bên” để xác định. Theo tôpô, trong迷宫两 bên đều là tường, nếu từ入口 và luôn bám một bên tường, sẽ找到出口. Vì tường trong bài khép kín, chỉ cần沿 tường đi là quay về điểm xuất phát mà không撞墙. Thực tế không cần cố撞墙, có thể đánh dấu các ô sát tường. Nếu撞墙, cần quay lại ngay để tránh走丢 và减少步数.
Suy ra: để xác định robot có ở ô X, đưa robot ra đường tường rồi đi một vòng; nếu không撞墙 thì确实 ở X.
Dùng方法 này:先标 tất cả ô未知, rồi từ trên xuống, trái qua phải判断 từng ô是否是 portal. Có thể先到 ô trên của nó, đi xuống, sang trái, rồi用方法 trên判断 robot có ở bên trái hay không. Nếu không, tức robot不在 vị trí dự kiến ⇒ ô là portal.
Xác định 2k ô portal xong cần匹配; vì \(k \le 5\),最多只需 \(9+7+5+3\) lần thử. So với判断所有未知 ô,最多 \(121-40\) lần.
#include<algorithm>#include<cstdio>#include<cstring>#include<iostream>#include<queue>#include<stack>#define Wall 0#define Unknown 1#define Space 2#define Gate 3#define Path 4constintN=20;constintdir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}};constchardirs[5]="ESWN";intn,m,k;inta[N][N],id[N][N];structpoint{intx,y;point(intx=0,inty=0):x(x),y(y){}booloperator==(constpoint&tmp)const{returnx==tmp.x&&y==tmp.y;}booloperator!=(constpoint&tmp)const{return!(*this==tmp);}pointside(intd)const{returnpoint(x+dir[d][0],y+dir[d][1]);}intcheck(intd){returna[x+dir[d][0]][y+dir[d][1]];}intid(){return::id[x][y];}}start;std::vector<std::pair<point,int>>path;std::pair<point,point>ans[N];std::pair<point,bool>vis[N];boolwalk(intd){printf("MoveRobot %c\n",dirs[d]);fflush(stdout);intret;scanf("%d",&ret);returnret;}boolwalk(intd,std::stack<int>&st){if(walk(d)){st.push(d);returntrue;}returnfalse;}boolread(){if(scanf("%d%d%d",&n,&m,&k)!=3)returnfalse;if(n==0)returnfalse;memset(a,0,sizeof(a));for(inti=0;i<n;i++)for(intj=0;j<m;j++){charc;std::cin>>c;if(c=='S')start=point(i,j);if(c=='*')a[i][j]=Wall;elsea[i][j]=Unknown;}returntrue;}voidanswer(){for(inti=0;i<k;i++)printf("Answer %d %d\n",ans[i].first.id(),ans[i].second.id());fflush(stdout);}// Đi theo một bên tường; vì Path sát tường là vòng khép kín lớn nhất,// chỉ cần đi沿 Path mà không撞障碍 là đượcvoidwall_follower_init(pointx,intlast,intwallside,points){if(x==s&&!path.empty())return;if(x.check(wallside)==Path){path.push_back(std::make_pair(x,wallside));wall_follower_init(x.side(wallside),wallside,last^2,s);}elseif(x.check(last)==Wall){for(inti=0;i<4;i++)if(i!=(last^2)&&x.check(i)!=Wall){path.push_back(std::make_pair(x,i));wall_follower_init(x.side(i),i,last,s);return;}}else{path.push_back(std::make_pair(x,last));wall_follower_init(x.side(last),last,wallside,s);}}voidinit(){intcnt=1;for(inti=0;i<n;i++)for(intj=0;j<m;j++){if(a[i][j]==Unknown){id[i][j]=cnt++;for(intk=0;k<8;k++)if(point(i,j).check(k)==Wall){a[i][j]=Path;break;}}elseid[i][j]=0;}path.clear();intwallside=0,last=0;for(inti=0;i<4;i++)if(start.check(i)==Wall){wallside=i;break;}for(inti=0;i<4;i++)if(start.check(i)==Path&&i!=(wallside^2)){last=i;break;}wall_follower_init(start,last,wallside,start);}voidundo(std::stack<int>&st){while(!st.empty())walk(st.top()^2),st.pop();}boolwall_follower(pointx){std::stack<int>st;boolok=true;inti=0;while(i<path.size()&&path[i].first!=x)i++;for(intj=i;ok&&j<path.size();j++){if(walk(path[j].second))st.push(path[j].second);elseok=false;}for(intj=0;ok&&j<i;j++){if(walk(path[j].second))st.push(path[j].second);elseok=false;}if(!ok)undo(st);returnok;}// Xác định hiện tại ở x; dùng “mò đá qua sông” để đi đến Path// Tránh障碍, ô未知 và portal; dùng khi tìm portal và ghép portalvoidbfs(points,pointt,std::vector<int>&v){staticintmap[N][N]={};memset(map,-1,sizeof(map));std::queue<point>q;map[s.x][s.y]=4;q.push(s);while(!q.empty()){pointx=q.front();q.pop();if(x==t)break;for(inti=0;i<4;i++){pointy=x.side(i);if((x.check(i)==Path||x.check(i)==Space)&&map[y.x][y.y]==-1){map[y.x][y.y]=i;q.push(y);}}}for(pointx=t;x!=s;x=x.side(map[x.x][x.y]^2)){v.push_back(map[x.x][x.y]);}std::reverse(v.begin(),v.end());}boolmove(points,pointt,std::stack<int>&st){// Dùng khi áp sát portalstaticstd::vector<int>v;v.clear();bfs(s,t,v);for(inti:v)if(!walk(i,st))returnfalse;returntrue;}// Di chuyển nhanh nhất về tườngboolmake_sure(pointx,intlast){if(a[x.x][x.y]==Path)returnwall_follower(x);for(inti=0;i<4;i++)if((x.check(i)==Path||x.check(i)==Space)&&i!=(last^2)){if(!walk(i))returnfalse;boolret=make_sure(x.side(i),i);walk(i^2);returnret;}returnfalse;}voidfind_gate(){intcnt=0;std::stack<int>st;for(inti=0;i<n;i++)for(intj=0;j<m;j++)if(cnt==k*2&&a[i][j]==Unknown)a[i][j]=Space;elseif(a[i][j]==Unknown){boolok=true;if(!move(start,point(i-1,j),st))ok=false;elseif(!walk(1,st))ok=false;elseif(!walk(2,st))ok=false;elseif(!make_sure(point(i,j-1),-1))ok=false;if(!ok){vis[cnt++]=std::make_pair(point(i,j),false);a[i][j]=Gate;for(intk=0;k<8;k++){pointy=point(i,j).side(k);if(point(i,j).check(k)==Unknown)a[y.x][y.y]=Space;}}elsea[i][j]=Space;undo(st);}}voidmake_gate_pair(){intcnt=0;std::stack<int>st;for(inti=0;i<k*2;i++)if(!vis[i].second)for(intj=0;!vis[i].second&&j<k*2;j++)if(j!=i&&!vis[j].second){boolok=true;if(!move(start,vis[i].first.side(2),st))ok=false;elseif(!walk(0,st))ok=false;elseif(!make_sure(vis[j].first.side(0),-1))ok=false;if(ok){ans[cnt++]=std::make_pair(vis[i].first,vis[j].first);vis[i].second=vis[j].second=true;}undo(st);}}intmain(){while(read()){init();find_gate();make_gate_pair();answer();}return0;}
Last updated on this page:, Update history Found an error? Want to help improve? Edit this page on GitHub! Contributors to this page:countercurrent-time, StudyingFather All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply