Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Small clarification | andreyDagger | 1121. Филиалы | 13 ноя 2021 12:28 | 1 | You don't need to sum the branches, you need to do binary OR "|" on them. | Wa3 | Михаил | 1121. Филиалы | 3 авг 2020 14:43 | 1 | Wa3 Михаил 3 авг 2020 14:43 Таким образом, если для данного перекрёстка нет подразделений СКБ Контур находящихся ближе, чем в 6 кварталах, то мы обозначим его числом 0. Carefully read this part of text. | Any Good algorithm?? My algo is O( H * W * ( 5 + 5 + 1 )^2 ). | c_pp | 1121. Филиалы | 12 янв 2017 03:41 | 1 | Who know O(H*W) or, O(H*W*5) algo ??? | The problem description is very unclear: here is a clarification | Otrebus | 1121. Филиалы | 5 июн 2015 16:23 | 1 | Each crossroads in the input is the binary OR of its branches, so a 5 (binary 101) at some crossroads in the input means there are branches 4 (100) and 1 (001) there. As for the output, for each crossroads where there are no branches (each 0, let's call this crossroads P), repeat this: Find the Manhattan (vertical+horizontal) distance to the closest branch from C. In the description, this closest distance is 2. Next, find all branches that lie on this exact distance from C. In the description, these are branches with number 16, 8, and 4. The output at location P should reflect all types of branches at distance 2 by ORing these numbers together, and in the description we get 28 (binary 10000 | 1000 | 100). | I don't understand this problem. | raxtinhac | 1121. Филиалы | 2 июн 2013 16:18 | 5 | Please explain the test, I think there 're something wrong or I don't understand the task. I've read that problem twice, but i didn't undestand Sample is Correct, You misunderstanding the prob, we didn't add the number's together, we "bit or" the number Notice that the Branches ID is 1, 2, 4, 8, 16 ~~ and so on So if this cross road has a Number 5 it means 1001(in Binary), so it has 2 branches : type 1 and type 3 we must output the total sum of branch types, so when we meet two cross road with 5 and 1,we must use operation 'bit or' (in C, it's '|') to calculate the total sum of branch types. so you understand? Edited by author 27.08.2008 20:51 The obscurity of the statement is outrageous! For each point you need to increase distances until you find a distance, such that there are some non-zeros or you reach the distance of 5. Once you reach the distance you need to bitwise OR all the numbers at this distance. Thanks, this is helping. but its very difficult to get this point of stopping at distance when one gets or of values greater than zero. | WA17 | Samsonov Alex [SESC USU] | 1121. Филиалы | 30 янв 2011 08:25 | 3 | WA17 Samsonov Alex [SESC USU] 21 май 2005 17:17 Does anybody know anything special about 17th test? I've wrote a program, and it works on sample (I use OR, of course), and on all my tests, but... Re: WA17 [RSU_Tash]Nodirbek_Kuklamov 30 янв 2011 08:25 but I got WA 17. There may be big table. | What's the answer for this test? | Paul - Dan Baltescu | 1121. Филиалы | 30 янв 2011 07:34 | 4 | 15 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1671 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1091 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1942 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 822 0 0 0 0 0 0 0 0 1197 0 0 0 0 870 0 0 0 1719 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 640 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1871 0 0 0 0 57 0 0 0 0 0 0 0 0 0 500 0 0 0 0 0 0 0 0 0 0 0 0 1743 0 557 0 0 0 0 0 0 0 0 0 0 0 0 1153 0 0 0 0 768 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1364 0 0 0 0 0 0 1094 0 0 0 0 0 0 0 0 0 724 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 212 0 0 0 0 0 0 20 0 My AC says 1671 1671 1671 1671 870 870 0 1975 1975 822 1942 1942 1942 1091 1091 1091 1091 1091 1197 -1 1671 1671 1671 870 870 2039 1975 1975 822 1942 1942 1942 1091 1091 -1 1091 1091 1197 1671 1671 1671 870 870 870 2039 1975 1975 822 1942 -1 1942 1942 1091 1091 1091 1197 1197 1671 1671 870 870 870 870 2039 1975 1975 -1 822 1942 1942 1942 1091 1091 1197 1197 -1 1671 870 870 870 -1 870 2039 1719 -1 1975 640 1942 1942 1942 1871 1871 1197 1197 1197 1727 57 870 870 870 870 2039 1719 1719 640 -1 640 640 640 1871 1871 1871 1197 1197 57 57 57 870 870 2031 2047 1727 1719 640 640 1012 1012 1871 1871 1871 1871 1871 1197 57 57 57 57 2031 1743 2031 557 1727 1012 1012 500 500 1871 1871 -1 1871 1871 1871 57 -1 57 57 1743 1743 2031 557 557 500 500 -1 500 500 1871 1871 1871 1871 1871 1209 1209 1209 1743 1743 -1 2031 -1 557 557 500 500 500 500 1871 1871 1871 1871 1871 1153 -1 1153 1493 1364 1999 -1 813 813 1903 1094 1094 1094 1094 1871 1871 1871 20 20 1153 1153 724 1364 -1 1364 768 813 1903 1094 1094 -1 1094 1094 1094 1871 20 20 20 724 724 -1 724 1364 1364 768 813 2047 1238 1238 1094 1094 1094 1094 20 20 20 20 724 724 724 724 1364 1364 768 1021 212 212 212 1238 1238 1238 20 20 20 20 20 724 724 724 724 1364 1364 980 212 212 212 -1 212 212 212 20 20 20 -1 20 And my AC says quite different: 1711 1671 1671 1671 1671 1671 1671 1671 1671 1719 0 0 0 0 0 1711 1671 1671 1671 -1 1671 1671 1671 1671 1719 1719 0 0 0 0 1197 1091 1091 1091 -1 1091 1911 1911 2039 1719 1719 1719 0 0 0 1197 1983 1942 1942 -1 1942 822 822 1975 1719 1719 1719 1719 0 0 1197 1197 1983 1942 1942 886 -1 822 1975 1719 1719 1719 1719 2047 0 -1 1197 1197 870 870 -1 886 2039 1719 -1 1719 1719 1719 2047 2047 1709 1709 1709 870 870 870 886 2039 1719 1719 1719 1719 2047 1871 1871 -1 640 640 697 870 870 886 2039 1719 1719 1719 2047 1871 1871 1871 640 640 697 57 57 870 886 2039 1719 1719 2047 1999 1871 1871 1871 640 697 57 57 57 57 57 57 2047 2047 1999 1999 1871 -1 1871 697 57 57 -1 57 57 57 57 1743 1743 1743 1743 500 -1 500 768 768 57 57 57 57 57 1743 1743 1743 1743 -1 1775 -1 557 768 768 768 1405 1405 724 724 1153 1153 1153 1153 -1 1153 557 557 768 -1 768 1364 1364 724 724 1750 1094 1094 1094 1153 1153 557 557 768 768 1364 -1 1364 724 724 1750 1094 1094 -1 1094 1094 1647 1647 768 768 1364 1364 724 -1 724 724 1750 1094 1094 1094 1094 20 20 768 768 1364 1364 724 724 724 724 1750 1094 1094 1094 20 20 20 768 768 1364 1364 724 724 212 212 212 1238 1094 20 20 20 20 0 980 212 212 212 212 -1 212 212 212 20 20 20 -1 20 But my prog. outs: 1671 1671 1671 1671 870 870 0 2541 2541 822 1942 1942 1942 1091 1091 1091 1091 1091 1197 -1 1671 1671 1671 870 870 3411 2541 2541 822 1942 1942 1942 1091 1091 -1 1091 1091 1197 1671 1671 1671 870 870 870 3411 2541 2541 822 1942 -1 1942 1942 1091 1091 1091 1197 1197 1671 1671 870 870 870 870 3411 2541 2541 -1 822 1942 1942 1942 1091 1091 1197 1197 -1 1671 870 870 870 -1 870 2589 1719 -1 2541 640 2582 2582 2582 2962 2962 1197 1197 1197 1728 57 870 870 870 870 2589 1719 1719 640 -1 640 640 640 1871 1871 1871 1197 1197 57 57 57 870 870 2613 5657 2276 1719 640 640 1140 1140 1871 1871 1871 1871 1871 1197 57 57 57 57 2613 1743 3068 557 2276 1140 1140 500 500 1871 1871 -1 1871 1871 1871 57 -1 57 57 1743 1743 3068 557 557 500 500 -1 500 500 1871 1871 1871 1871 1871 1210 1210 1210 1743 1743 -1 3068 -1 557 557 500 500 500 500 1871 1871 1871 1871 1871 1153 -1 1153 2517 1364 2511 -1 1325 1325 2419 1094 1094 1094 1094 2965 1871 1871 20 20 1153 1153 724 1364 -1 1364 768 1325 2419 1094 1094 -1 1094 1094 1094 2965 20 20 20 724 724 -1 724 1364 1364 768 1325 2631 1306 1306 1094 1094 1094 1094 20 20 20 20 724 724 724 724 1364 1364 768 1537 212 212 212 1306 1306 1306 20 20 20 20 20 724 724 724 724 1364 1364 980 212 212 212 -1 212 212 212 20 20 20 -1 20 And I get Wrong Answer on test 17. If anybody knows this test, please tells me my mistake. What is there wrong? I think that b[1][8] = 1719 + 822 = 2541 And how can it be 1975? I am sorry for my bad language. Edited by author 30.01.2011 08:23 | Sample output is nuts | DarkeN | 1121. Филиалы | 8 апр 2009 15:53 | 1 | I seriously think that sample output is screwed up. For example, the lowest line reads: -1 1 4 - 1 4 But taking into account the proximity of the branch with ID=4 (bin: 100) and the branch with ID=1 (bin: 001) shouldn't all non-negative numbers in line equal 5( bin: 101), like -1 5 5 -1 5 ? Could someone make it clear for me? I would be very grateful;-) | Help please why i have TL on #13 test | Husan | 1121. Филиалы | 4 окт 2008 19:52 | 1 | #include<iostream> using namespace std; struct point{ int x,y,kol; }; int a[152][152]={{0}},val[152][152]={{0}}; int m,n; void query(int i1,int j1,int step=5) { int i,j,pr[152][152]={{0}},n1; int x1,y1; int x[5]={0,-1,0,1,0},y[5]={0,0,1,0,-1}; point q[1000]={0},k; i=n1=1; q[1].x=i1;q[1].y=j1; while(i<=n1) { k=q[i]; for(j=1;j<=4;j++) { x1=k.x+x[j];y1=k.y+y[j]; if(pr[x1][y1]==0 && k.kol<step && (x1>=1 && x1<=n && y1>=1 && y1<=m)) { if(a[x1][y1]!=0){val[i1][j1]|=a[x1][y1];if(k.kol<step)step=k.kol+1;} n1++; q[n1].x=x1; q[n1].y=y1; q[n1].kol=k.kol+1; pr[x1][y1]=1; }; } i++; } } int main() { int i,j,k; cin>>n>>m; for(i=1;i<=n;i++)for(j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]!=0)val[i][j]=-1;} for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(a[i][j]==0) { query(i,j,5); } } for(i=1;i<=n;i++) { cout<<endl; for(j=1;j<=m;j++)cout<<val[i][j]<<" "; } return 0; } | TL on Test#13 | MultiThread | 1121. Филиалы | 29 июл 2007 22:29 | 2 | I got TL on #13 :(. Does any body konw the test? I use BFS. You should do only 5-6 steps of BFS. Not full BFS. If the distance between start and end is greater than 6 you should stop BFS. | to get accepted | Paul Diac | 1121. Филиалы | 26 июл 2006 23:33 | 3 | To get AC you should not make the sum of all the types of nearest brangches but the "or" in pascal and "|" in c++. examle: 1+5+2=8 but you get WA 1|5|2=7 in c++ to get AC 1 or 5 or 2 =7 in pascal to get AC I don't know why, but this is the way to get accepted. Can anyone explain why? (the problem text seems ambiguos to me). You must find sum of (!) different branches for each cross-road. In your test: 1 = 1 2 = 2 5 = 1+4 So, there are 3 different branches(1,2,4) and sum = 7 Thanks a lot! To use or is more simple then solve that problem without it! ) | I got WA.....555555555.......Who can help me ? | hello | 1121. Филиалы | 19 июн 2004 23:59 | 5 | I got WA on test17. I can't find my mistakes.... I think the sample test is incorrect. My solution got the answer is : 2 2 -1 2 -1 3 2 2 7 2 1 8 7 5 7 1 6 5 -1 5 -1 1 4 -1 4 But the sample output is : 2 2 -1 2 -1 3 2 2 7 2 1 7 7 5 7 1 5 5 -1 5 -1 1 4 -1 4 I think the sample output is wrong , isn't it ??? Is my answer right ? Who can tell me ???? This is my code : const Maxn = 200 ; var h : Array [0..Maxn,0..Maxn] Of LongInt ; cost : Array [0..Maxn,0..Maxn] Of Int64 ; t : Array [0..6*Maxn] Of LongInt ; n , m , i , j , k , len : Integer ; Function check ( k : LongInt ) : Boolean ; var i : Integer ; begin check := false ; if k = 0 then exit ; for i := 1 to len do if k = t[i] then exit ; check := true ; end; procedure goin ( x , y , xi , yi : Integer ) ; begin if check ( h[xi,yi] ) then begin Inc ( cost[x,y] , h[xi,yi] ) ; Inc ( len ) ; t[len] := h[xi,yi] ; end; end; procedure Bfs ( x , y , k : Integer ) ; var i , j , xi , yi : Integer ; begin len := 0 ; for i := 1 to k - 1 do begin xi := x + i ; if xi > n then break ; if y + k - i <= m then goin ( x , y , xi , y + k - i ) ; if y - k + i > 0 then goin ( x , y , xi , y - k + i ) ; end; for i := 1 to k - 1 do begin xi := x - i ; if xi < 0 then break ; if y + k - i <= m then goin ( x , y , xi , y + k - i ) ; if y - k + i > 0 then goin ( x , y , xi , y - k + i ) ; end; if y + k <= m then goin ( x , y , x , y + k ) ; if y - k > 0 then goin ( x , y , x , y - k ) ; if x + k <= n then goin ( x , y , x + k , y ) ; if x - k > 0 then goin ( x , y , x - k , y ) ; end; begin read ( n , m ) ; for i := 1 to n do for j := 1 to m do read ( h[i,j] ) ; for i := 1 to n do for j := 1 to m do if h[i,j] = 0 then begin for k := 1 to 5 do begin Bfs ( i , j , k ) ; if len > 0 then break ; end; end else cost[i,j] := -1 ; for i := 1 to n do begin write ( cost[i,1] ) ; for j := 2 to m do write ( ' ' , cost[i,j] ) ; writeln ; end; end. According to the problem describe,you should sum up the nearest different types of valus.But it is wrong for the sample text. However,if you uses 'or' instead of '+',you will obtain the answer as sample output and got AC. You just have to do is: Change i:=i+j into i:=i or j I'm sorry . I don't know your meaning . I have some questions : 1: I think I just sumed up the nearest different types of valus. Am I right ? 2: What did you mean " 'or' instead Of '+' " ? 3: You said "You just have to do is: Change i:=i+j into i:=i or j " . But I can't find " i:=i+j " in my code . What did you mean ? Could you explain to me ? Thank you very much for helping me !!! Thank you very much !!!!!!! I know your meaning . I changed '+' to 'or' and got AC . Thanks again !!!! | Let me explain the data | Czw's Sister | 1121. Филиалы | 11 май 2004 08:29 | 3 | when you are caculating,don't use +,use or! caculating-->calculating..... Change Your name !!!! I don't understand what you said. Could you say more ? I got WA on test17. I can't find my mistakes.... I think the sample test is incorrect. My solution got the answer is : 2 2 -1 2 -1 3 2 2 7 2 1 8 7 5 7 1 6 5 -1 5 -1 1 4 -1 4 But the sample output is : 2 2 -1 2 -1 3 2 2 7 2 1 7 7 5 7 1 5 5 -1 5 -1 1 4 -1 4 I think the sample output is wrong , isn't it ??? Is my answer right ? Who can tell me ???? | can someone tell me the reason... | Pooya | 1121. Филиалы | 1 мар 2003 23:33 | 2 | I don't understand why the Answer is that in the input of the problem specialy the one [1,1]=2 {*2*} 2 -1 2 -1 3 2 2 7 2 1 7 7 5 7 1 5 5 -1 5 -1 1 4 -1 4 if you know the answer please help me. with best wishes pooya I forgot this problem but all i remember is that it uses XOR between numbers (Integer!) and it was so cute... mmm I think it also needs BFS to find nearst branch? is it right? Yours Aidin | Explaing of the test example | VladG | 1121. Филиалы | 16 дек 2002 11:16 | 1 | The confusion about the test example lies in the fact that if you carefully read the problem (after you tried to send a solution that got a WA :) you see that you need to sum up not all the values (a sum of branch types in the cell) in the given distance, but only values for different branch types. Although, I agree that the problem is not described very well. | I don't understand a sample test case | Badd | 1121. Филиалы | 29 ноя 2002 07:59 | 1 | why don't output in 3rd row , 2nd colum be 8 , fomr 1 + 5 + 2 explain me about this problem please. Sample Input 5 5 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 1 0 0 4 0 Sample Output 2 2 -1 2 -1 3 2 2 7 2 1 7 7 5 7 1 5 5 -1 5 -1 1 4 -1 4 | i wa too want some test data | ^oo^ | 1121. Филиалы | 11 ноя 2002 18:09 | 1 | const MAXN=15; type data=array[1..4] of 0..1; var d:array[1..MAXN,1..MAXN] of data; p:array[1..MAXN,1..MAXN] of 0..1; a:array[1..MAXN,1..MAXN] of integer; h,w,i,j,k,t,s,pi,pj:integer; mmm:data; function exto(a:data):integer; var i,s,t:integer; begin s:=0; t:=1; for i:=1 to 4 do begin s:=s+t*a[i]; t:=t*2; end; exto:=s; end; function equal(a,b:data):boolean; var i:integer; begin equal:=false; for i:=1 to 4 do if a[i]<>b[i] then exit; equal:=true; end; function ok(i,j:integer):boolean; begin if (i<1) or (j<1) or (i>h) or (j>w) then ok:=false else ok:=true; end; procedure add(var a:data; b:data); var i:integer; begin for i:=1 to 4 do if b[i]=1 then a[i]:=1; end; begin assign(input,'1121.in'); reset(input); read(h,w); for i:=1 to h do for j:=1 to w do begin read(s); if s<>0 then p[i,j]:=1; t:=8; for k:=4 downto 1 do begin if s-t>=0 then begin dec(s,t); d[i,j,k]:=1; end; t:=t div 2; end; writeln(s); end; for i:=1 to h do begin for j:=1 to w do begin a[i,j]:=-1; if p[i,j]=0 then begin for k:=1 to 5 do begin mmm:=d[i,j]; for pi:=-k to k do begin pj:=k-abs(pi); if (ok(i+pi,j+pj)) then add(mmm,d[i+pi,j+pj]); pj:=-pj; if (pj<>0) and (ok(i+pi,j+pj)) then add(mmm,d [i+pi,j+pj]); end; if not equal(d[i,j],mmm) then break; end; a[i,j]:=exto(mmm); end; write(a[i,j]:2,' '); end; writeln; end; end. | Help, WA! Give me some test please! | Algorithmus_UA(algorithmus@univ.kiev.ua) | 1121. Филиалы | 4 ноя 2002 03:00 | 1 | const MAXN = 150; type pointtype = record x,y:byte; end; var a,b:array[1..MAXN,1..MAXN]of integer; c:array[1..MAXN,1..MAXN]of byte; s1,s2:array[1..10000]of pointtype; N,M,h1,h2,tek,i,j:integer; procedure rec(x,y,k:byte); begin if (x=0)or(y = 0)or(x = N+1)or(Y = M+1) then exit; if (a[x,y] = 0)and((c[x,y] = 0)or(c[x,y] = tek)) then begin b[x,y]:=b[x,y] or k; if c[x,y] = 0 then begin c[x,y]:=tek; inc(h2); s2[h2].x:=x;s2[h2].y:=y; end; end; end; begin { assign(input,'1121.dat');reset(input);} readln(N,M); for i:=1 to N do for j:=1 to M do read(a[i,j]); for i:=1 to N do for j:=1 to M do if a[i,j]<>0 then begin inc(h1); s1[h1].x:=i;s1[h1].y:=j;{s1[h1].k:=a[i,j];} b[i,j]:=a[i,j]; end; tek:=0; while true do begin inc(tek);if tek = 6 then break; if h1 = 0 then break; h2:=0; for i:=1 to h1 do begin rec(s1[i].x+1,s1[i].y,b[s1[i].x,s1[i].y]); rec(s1[i].x-1,s1[i].y,b[s1[i].x,s1[i].y]); rec(s1[i].x,s1[i].y-1,b[s1[i].x,s1[i].y]); rec(s1[i].x,s1[i].y+1,b[s1[i].x,s1[i].y]); end; h1:=h2; for i:=1 to h1 do s1[i]:=s2[i]; end; for i:=1 to N do begin for j:=1 to M-1 do begin if a[i,j] = 0 then write(b[i,j],' ') else write(-1,' '); end; if a[i,M] = 0 then writeln(b[i,M]) else writeln(-1); end; end. | Please explain me the test. | Vokin Andrei (vokin_andrei@mail.ru) | 1121. Филиалы | 9 сен 2002 22:25 | 1 | I don't understand why answer for 5 5 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 1 0 0 4 0 must be 2 2 -1 2 -1 3 2 2 7 2 1 7 7 5 7 1 5 5 -1 5 -1 1 4 -1 4 i think that b[4, 2] must be 6 and b[3, 2] must be 8 Vokin Andrei e-mail: vok@sbor.ru |
|
|