Show all threads Hide all threads Show all messages Hide all messages | GOOD HINT | Felix_Mate | 1151. Radiobeacons | 29 Sep 2017 21:30 | 1 | Маяки могут находится в 1 точке. P.S. Если считать, что маяки не могут быть в одной точке, то тогда нужно решать паросочетанием (как я в начале и решал), что гораздо сложнее по реализации | Tests are fixed | Vladimir Yakovlev (USU) | 1151. Radiobeacons | 7 Feb 2016 14:56 | 1 | 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. | WA #2 | ile | 1151. Radiobeacons | 23 Oct 2015 19:02 | 3 | WA #2 ile 26 Oct 2010 04:54 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....... | Why WA 5? | kvsmirnov | 1151. Radiobeacons | 22 Jun 2015 19:03 | 1 | | Tests are inconsistent | Baz | 1151. Radiobeacons | 8 Feb 2014 17:19 | 1 | 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. | To admins: "strange" radiobeacons | Alexey Shmelev [NNSU] | 1151. Radiobeacons | 4 Oct 2012 01:57 | 2 | 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. | Good Test | bsu.mmf.team | 1151. Radiobeacons | 25 Jul 2012 13:43 | 3 | 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 Wow!!! Usually the answer doesn't come so fast =) | Why I got WA on #15? | HJ | 1151. Radiobeacons | 4 Sep 2010 21:33 | 2 | | WA 12, what's wrong ? | Alias (Alexander Prudaev) | 1151. Radiobeacons | 4 Sep 2010 21:32 | 3 | RSignJ - distance from checkpoint I to beacon J - can be 0 | Help , please . How to read string in this problem ??? | A.Ferdinand | 1151. Radiobeacons | 27 Aug 2010 05:12 | 3 | 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); } } | my code too too long. whoever AC this problem can tell how long your code is? | Tim Green | 1151. Radiobeacons | 27 Aug 2010 05:02 | 2 | Simple problem, I use brute force, size of my code less 50 lines. | Hint | VasilySlesarev | 1151. Radiobeacons | 7 Jul 2009 22:09 | 2 | Hint VasilySlesarev 7 Jul 2009 21:24 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. | Problem 1151 "Radiobeacons" has been rejudged (+) | Sandro (USU) | 1151. Radiobeacons | 3 Jun 2009 01:54 | 1 | New tests have been added. 78 authors have lost AC. | Who can explain me the problem,I think maybe I misunderstand it. | ABCDEFG | 1151. Radiobeacons | 12 Apr 2005 19:33 | 6 | 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. | Is sample output correct? | Danica Porobic | 1151. Radiobeacons | 17 Jul 2004 15:05 | 1 | Why sample output isn't for example: 5:UNKNOWN 16:UNKNOWN or 5:12,12 16:8,8? | What are the ranges of coordinates and M? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1151. Radiobeacons | 11 Jul 2004 21:12 | 2 | | Can two beacons be at the same place?Can a beacon and a checkpoint be at the same place? | Lin | 1151. Radiobeacons | 9 Mar 2003 12:44 | 2 | | Why I got "wrong answer"? This is the program.Can anyone help me? | Lin | 1151. Radiobeacons | 3 Oct 2002 15:16 | 1 | 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. | Can any one give me some testdata of 1151?Thanks!! | The Answer | 1151. Radiobeacons | 23 Jan 2002 07:53 | 1 | |
|
|