Маяки могут находится в 1 точке. P.S. Если считать, что маяки не могут быть в одной точке, то тогда нужно решать паросочетанием (как я в начале и решал), что гораздо сложнее по реализации The problem was clarified: It is guaranteed that measurements are consistent, i.e. the solution always exists, but may be ambiguous. Incorrect test #15 was deleted. In the same time the new tests were added. In total, 27 authors lost their AC. Anyone knows what's the problem with 2nd test? any ideas, please!! Found it. Misunderstood the problem. how to say....I WA#2 too however cannot find my mistakes....... Considering my submissions, I concluded that in the 15-th test there is a radiobeacon for which its coordinates can't be integers between 1 and 200. If for such radiobeacons output "UNKNOWN", the solution gets AC. This does not fit with the statement. In test #15 there are radiobeacons which don't have correct location on the plane (i.e. no one of points 1 <= x,y <= 200 is acceptable) but their signals are identified by checkpoints. In the problem statement we can find, that "N radiobeacons are located on the plane" and "we know ... that their coordinates are integers from 1 to 200". So, I believe that such test cases are incorrect. Yes, my assert also falls. This test helped me to find several bugs 2 0,0:1-1,2012-200 201,201:2012-1 1:1,1 2012:200,200 Thank you! Wow!!! Usually the answer doesn't come so fast =) RSignJ - distance from checkpoint I to beacon J - can be 0 I'm sure I got WA because of reading string. Please help me, thanks. Here is my code to read string : ... fscanf(stdin,"%d\n",&m) ; for(int i=0;i<m;i++) { char s[1000] ; int j = 0 , k = 0 ; fscanf(stdin,"%s",&s) ; while ( s[j] != ',' ) a[i].x = a[i].x * 10 + s[j++] - 48 ; j++ ; while ( s[j] != ':' ) a[i].y = a[i].y * 10 + s[j++] - 48 ; j++ ; while (j < strlen(s) ) { while ( s[j] != '-' ) b[i][k] = b[i][k] * 10 + s[j++] - 48 ; j++ ; while ( j < strlen(s) && s[j] != ',' ) c[i][k] = c[i][k] * 10 + s[j++] - 48 ; k++ ; if ( s[j] == '\n' ) { j++ ; break ; } j++ ; } deg[i] = k ; } scanf("%d\n",&n); int i; int id,x,y,r; for (i = 0 ; i<n ; i++){ scanf("%d,%d:",&x,&y); while (true){ scanf("%d-%d",&id,&r); a[id][cnt[id]].x = x; a[id][cnt[id]].y = y; a[id][cnt[id]].r = r; cnt[id]++; char ch; ch = getc(stdin); if (ch!=',') break; }
} or: for (int i=0; i<m; i++){ char buf; cin >> tmp.x >> buf >> tmp.y; while ((buf=cin.get())!='\n' && buf!=EOF){ int id; cin >> id >> buf >>tmp.r; a[id].push_back(tmp); } } Simple problem, I use brute force, size of my code less 50 lines. This problem is simple, but I choose way to work with geometry for a long time. Hint: while finding coordinates of beacon you must use information that beacon`s coordinates are between 1 and 200. My solution doesn't use this limitations on coordinates, it's more general and works very fast. New tests have been added. 78 authors have lost AC. While reading the information of the checkpoints,I can use there coordinates and the distance between it and a certain beacon to determin the range of the beacon.And as more information was read,the range will become smaller and smaller.So after the procedure,if I am sure the beacon is at a point,I output it and it's coordinates,otherwise I output UNKNOWN.Of course after sorting. I think my algorithm is right if I did understand the idea. But I got wa even on test 2,who can help me and tell me the meaning of the problem or give me your algorithm,thank you. This is my code ,I don't think it's wrong ,could you help me checking it? #include<iostream> #include<string> #include<memory> #include<cstdio> #include<cstring> using namespace std; //#define DEBUG #ifndef DEBUG FILE *fin=stdin; #else FILE *fin=fopen("1151.txt","r"); #endif const long maxm=20; const long maxn=11; const long maxint=200; //long map[maxn]; struct node{ long map,minx,miny,maxx,maxy; }list[maxn]; long n=0,m; long insert(long x) { long i; for(i=0;i<n;++i){ if(list[i].map==x)return i; } list[n].map=x; list[n].minx=list[n].miny=1; list[n].maxx=list[n].maxy=200; ++n; return n-1; } void read() { long x,y,a,b; char ch; fscanf(fin,"%ld,%ld",&x,&y); //cin>>x>>ch>>y; //cin.get(ch); ch=getc(fin); long i; while(ch!='\n'){ fscanf(fin,"%ld-%ld",&a,&b); //cin>>a>>ch>>b; i=insert(a); if(x+b<list[i].maxx)list[i].maxx=x+b; if(x-b>list[i].minx)list[i].minx=x-b; if(y+b<list[i].maxy)list[i].maxy=y+b; if(y-b>list[i].miny)list[i].miny=y-b; if(fscanf(fin,"%c",&ch)==-1)break; //cin.get(ch); //if(cin.fail())break; } } int par(int p,int r) { node temp=list[p]; while(p<r){ while(p<r&&list[r].map>=temp.map)--r; list[p]=list[r]; while(p<r&&list[p].map<=temp.map)++p; list[r]=list[p]; } list[p]=temp; return p; } void qsort(int p,int r) { if(p<r){ int q=par(p,r); qsort(p,q-1); qsort(q+1,r); } } int main(void) { fscanf(fin,"%ld",&m); while(m>0){ read(); --m; } qsort(0,n-1); for(long i=0;i<n;++i){ if(list[i].minx==list[i].maxx&&list[i].miny==list[i].maxy){ //printf("%ld:%ld,%ld\n",list[i].map,list[i].maxx,list[i].maxy); cout<<list[i].map<<':'<<list[i].maxx<<','<<list[i].maxy<<endl; } else{ //printf("%ld:UNKNOWN\n",list[i].map); cout<<list[i].map<<":UNKNOWN"<<endl; } } return 0; } I rewrite my program and it still got wa on test 2,could anybody help me????? I'm sure your understanding is right. Why sample output isn't for example: 5:UNKNOWN 16:UNKNOWN or 5:12,12 16:8,8? Const MaxN = 10; MaxSize = 200; Type TotalType = Array[1..MaxN,1..MaxSize,1..MaxSize] of Byte; Var B : ^TotalType; Id : Array[1..MaxN] of Integer; T : Array[1..MaxN] of Integer; N : Integer; Procedure FindPlace(X,Y,TheId,d : Integer); Var i,j : Integer; Function GetNum : Integer; Var k : Integer; Begin For k := 1 to N do If TheId=Id[k] then Begin GetNum := k; Exit; End; Inc(N); Id[N] := TheId; GetNum := N; End; Begin i := GetNum; Inc(T[i]); For j := -d to d do Begin If (1<=X+d) and (X+d<=MaxSize) then If (1<=Y+j) and (Y+j<=MaxSize) then Inc(B^[i,X+d,Y+j]); If (1<=X-d) and (X-d<=MaxSize) then If (1<=Y+j) and (Y+j<=MaxSize) then Inc(B^[i,X-d,Y+j]); End; For j := -d+1 to d-1 do Begin If (1<=Y+d) and (Y+d<=MaxSize) then If (1<=X+j) and (X+j<=MaxSize) then Inc(B^[i,X+j,Y+d]); If (1<=Y-d) and (Y-d<=MaxSize) then If (1<=X+j) and (X+j<=MaxSize) then Inc(B^[i,X+j,Y-d]); End; End; Function ReadNum(Var X : String) : Integer; Var Temp : Longint; Begin Temp := 0; While (Length(X)>0) and (X[1] in ['0'..'9']) do Begin Temp := Temp*10+Ord(X[1])-48; Delete(X,1,1); End; If Length(X)>0 then Delete(X,1,1); ReadNum := Temp; End; Procedure Main; Var Total,i : Integer; Str : String; X,Y : Integer; TheId,d : Integer; Begin Readln(Total); For i := 1 to Total do Begin Readln(Str); X := ReadNum(Str); Y := ReadNum(Str); While Length(Str)<>0 do Begin TheId := ReadNum(Str); d := ReadNum(Str); FindPlace(X,Y,TheId,d); End; End; End; Procedure Print; Var i,j,k : Integer; Total : Integer; Place : Array[1..MaxN,1..2] of Integer; Begin Fillchar(Place,Sizeof(Place),0); For i := 1 to N do Begin Total := 0; For j := 1 to MaxSize do For k := 1 to MaxSize do If B^[i,j,k]=T[i] then Begin Inc(Total); Place[i,1] := j; Place[i,2] := k; End; If Total<>1 then Begin Place[i,1] := 0; Place[i,2] := 0; End; End; For j := 1 to 30000 do For i := 1 to N do If Id[i]=j then If Place[i,1]=0 then Writeln(j,':UNKNOWN') else Writeln(j,':',Place[i,1],Chr(44),Place [i,2]); End; Begin New(B); Fillchar(B^,Sizeof(B^),0); Main; Print; Dispose(B); End. |
|