Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | TLE Test #8 | Sadeko | 1054. Ханойская башня | 25 ноя 2018 02:17 | 1 | | What is WA 2 ? | ProTreo | 1054. Ханойская башня | 29 ноя 2013 23:51 | 1 | What's the test number 2 ? | all tests are currect but WA 1 !!!! | Babken | 1054. Ханойская башня | 23 окт 2013 16:23 | 2 | 3 3 3 1 out:3 3 1 1 1 out:0 3 1 2 3 out:-1 3 2 2 2 out:7 | My programm accepted... | Jica | 1054. Ханойская башня | 7 авг 2012 10:00 | 1 | import java.util.Scanner; public class Hanoi_Tower { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int d[] = new int [n+1]; for (int i = 1; i <= n; i++) { d[i] = sc.nextInt(); } int x =n%2; int a[][] ={{3, 1, 2, 3}, {2, 1, 3, 2}}; double ans = 0; for (int i = n; i > 0; i--) { int y = (i+x)%2; double rep = (ans/Math.pow(2, i) + 1)%3; if (d[i] != a[y][(int)rep]){ if (d[i] != a[y][(int)(rep+1)]){ System.out.println("-1"); return; } ans += Math.pow(2, (i-1)); } } System.out.printf("%.0f",ans); } } | if you WA1 try this | yuzeming | 1054. Ханойская башня | 23 авг 2010 08:46 | 1 | | what case is not obeyed in my code?? | Ravi Maggon | 1054. Ханойская башня | 21 авг 2010 19:08 | 1 | Tried all test cases i know but it gives wrong answer for test#1. Can anyone please tell me what case is failing in my code? #include<stdio.h> int count=0,ni; int seq[31][31]; int a=-1,b=-1,c=-1,move=-1,movea=-1,moveb=-1,movec=-1,flag=0,go=0; void tower(int n,char beg,char aux,char end) { if(n==1) { int begin,ends,k,m; begin=(int)(beg-48)-1; ends=(int)(end-48)-1; count++; for(k=ni-1;k>0;k--) seq[ends][k]=seq[ends][k-1]; seq[ends][0]=seq[begin][0]; for(k=0;k<ni-1;k++) seq[begin][k]=seq[begin][k+1]; seq[begin][ni-1]=0; /*for(k=0;k<3;k++) { for(m=0;m<ni;m++) printf("%d",seq[k][m]); printf("\n"); } printf("\n"); */for(k=0;k<ni;k++) { if(seq[a][k]==1) { movea=1; break; } } for(k=0;k<ni;k++) { if(seq[b][k]==2) { moveb=1; break; } } for(k=0;k<ni;k++) { if(seq[c][k]==3) { movec=1; break; } } if(movea==1&&moveb==1&&movec==1&&flag==0) { flag=1; move=count; } movea=-1; moveb=-1; movec=-1; return; } else { tower(n-1,beg,end,aux); tower(1,beg,aux,end); tower(n-1,aux,beg,end); } } void assign() { int k,j; for(k=1;k<3;k++) { for(j=0;j<ni;j++) seq[k][j]=0; } for(j=0;j<ni;j++) seq[0][j]=(j+1); } int main() { scanf("%d",&ni); assign(); scanf("%d %d %d",&a,&b,&c); if(a==1) a--; else if(a==3) a=1; if(b==1) b--; else if(b==3) b=1; if(c==1) c--; else if(c==3) c=1; tower(ni,'1','2','3'); printf("%d",move); return 0; } | Can someone give me a example that its answer is "IMPOSSIBLE"? | Roger | 1054. Ханойская башня | 22 сен 2009 00:29 | 2 | For example, next input 3 1 2 3 | why wa on test 3? is there any '-1' exist?? | somebody | 1054. Ханойская башня | 26 янв 2008 20:12 | 5 | For example,if the text is: 3 1 2 3 you should output -1. Because there wasn't such sequence in the table! i think it is 7 times. 1-> 3, 1 (III) 2-> 2, (I) 1-> 2, 1 (I) 3-> 3 (II) 1-> 1 (III) 2-> 3, 2 (II) 1-> 3, 2, 1(II). | So Simple Move Back | Locomotive | 1054. Ханойская башня | 30 ноя 2007 22:54 | 2 | Hints: - Use 3variable which means first,too and last and - do for n downto 1 ... - use "1 shr i" to get 2^i.. - eachtime just swap 2 of (from,temp or too)... and... for i:=n downto 1 do begin if p[i]=temp then begin writeln(-1); exit; end else if p[i]=from then swap(temp,too) else begin inc(ans,(1 shl (i-1))); swap(from,temp); end; end; For more information: aidin_n7@hotmail.com | why WA? Is there any edge case I haven't covered? | AlainDelon | 1054. Ханойская башня | 11 окт 2007 19:01 | 1 | c++ code as below =================== #include <cstdio> #include <iostream> #define MAX_NUM 31 using namespace std; int g_Dseq[MAX_NUM] = {1}; int g_Dtargseq[MAX_NUM]; int g_count = 0; int N = 1; int g_done = 0; void movedisk(int n, int dsrc, int ddesc); void hanoi_proc(int n,int dsrc, int daid, int ddesc); int isdone(); void main() { int i=0; cin >> N; if(N <1 || N > 31) { cout<<-1; }else { for(i=0;i<N;++i) { cin>> g_Dtargseq[i]; g_Dseq[i] = 1; }
hanoi_proc(N, 1, 3, 2); if(g_done ==0) cout<<-1;
} } int isdone() { for(int i=0;i<N;++i) { if(g_Dseq[i] != g_Dtargseq[i]) return 0; } return 1; } void movedisk(int n, int dsrc, int ddesc) {
g_Dseq[n-1] = ddesc; ++g_count;
if(g_done ==0 && isdone() == 1) { cout<<g_count; g_done = 1; } } void hanoi_proc(int n,int dsrc, int daid, int ddesc) { if(n == 1) { movedisk(n, dsrc, ddesc); }else { hanoi_proc(n-1, dsrc, ddesc, daid);
movedisk(n, dsrc, ddesc); hanoi_proc(n-1, daid, dsrc, ddesc); } } ============================= | Look at this AC one! | mace | 1054. Ханойская башня | 3 июл 2007 18:29 | 3 | This Program Got AC within 0.01 Sec! ---------------------------------------------------------------------- program answer1054; const st:array[0..1,0..2]of 1..3=((1,2,3),(1,3,2)); var d:array[1..31]of 1..3; e:array[1..31]of 0..1; n,i,s,f,delta,j,s1:longint; function mi2(x:integer):longint;{mi2=2^x} var s:longint; i:integer; begin s:=1; for i:=1 to x do s:=s*2; mi2:=s; end; function c(x:integer):longint;{N-dished Hanoi tower step uses} begin if x=31 then c:=maxlongint else c:=mi2(x)-1; end; begin readln(n); for i:=1 to n do read(d[i]); s:=0;f:=c(n); fillchar(e,sizeof(e),0); for i:=n downto 1 do begin s1:=1;delta:=0; for j:=i+1 to n do begin delta:=delta+e[j]*s1; s1:=s1*2; end; if d[i]=st[(n+i) mod 2,delta mod 3] then begin f:=f-mi2(i-1); end else if d[i]=st[(n+i) mod 2,(delta+1) mod 3] then begin s:=s+mi2(i-1); e[i]:=1; end else begin writeln(-1); halt; end; end; writeln(s); end. | Get wrong answer on first test | Alexei Sukhonosov | 1054. Ханойская башня | 19 фев 2007 00:15 | 1 | Can anyone tell me what are the input data for this test? The program seems to work OK here are some test results: 3 3 3 1 3 3 2 2 2 7 3 1 2 2 6 2 2 1 -1 | my fast AC prog(input is O(n),but other is O(logn)) | odp | 1054. Ханойская башня | 24 дек 2006 17:14 | 5 | //I have delete the code. if you want it ,i will send it. Edited by author 13.02.2005 07:00 Well, I'm very interested in what you mean by O(logn). Please send your solution to me (urrel@rambler.ru) iff you find it possible... send it to me - gr_dimon@rambler.ru ok, send it to me as well, thanks. starforever00@gmail.com | What formula? | Zubyk Taras(Khmelnitsky) | 1054. Ханойская башня | 6 июн 2006 14:08 | 1 | What can I make with this formula to receive is Accepted? This formula calculates quantity of rearrangements of disks: T (n) =2^n-1 Help me, to deduce the formula which calculates quantity of steps. Help!!! Many thanks, beforehand!
| look at this AC one,it's very easy to understand!! | geniushjs | 1054. Ханойская башня | 24 авг 2004 16:42 | 2 | program hanoi; var step:longint; i,n:integer; goal:array[1..31] of byte; procedure p(k:integer;a,b,c:integer); begin if k=0 then exit; if goal[k]=b then begin step:=step+trunc(exp((k-1)*ln(2))); p(k-1,c,b,a); end else if goal[k]=c then begin writeln(-1); halt; end else p(k-1,a,c,b); end; begin readln(n); for i:=1 to n do read(goal[i]); step:=0; p(n,1,2,3); writeln(step); end. here's mine #include <stdio.h> int n, s[50], s1[] = {0, 1, 2, 2, 3, 3, 1, 1, 2, 2, 3, 3, 1}, s2[] = {0, 1, 3, 3, 2, 2, 1, 1, 3, 3, 2, 2, 1}; int is(int lev, long pos) { if (pos % 12 == 0) pos++; return (lev & 1) ? s1[pos % 12] : s2[pos % 12]; } long baga_mare(int lev, long pos) { long fiu; if (lev == n) return pos; fiu = 2 * pos - 1; if (s[n - lev] == is(lev + 1, fiu)) return baga_mare(lev + 1, fiu); fiu = 2 * pos; if (s[n - lev] == is(lev + 1, fiu)) return baga_mare(lev + 1, fiu); return 0; } int main() { int i; scanf("%d", &n); for (i = 1; i <= n; scanf("%d", s + i++)); printf("%ld\n", baga_mare(0, 1) - 1); return 0; } | (WA) Here is my code in C, could anyone give me some test cases to break it please? | Jonathan Yu | 1054. Ханойская башня | 27 дек 2002 19:20 | 1 | /* Prog: acm_1054 results: */ #include <stdio.h> #include <math.h> int a = 1,b = 2,c = 4; int disks[5]; int numbers[5][101]; int dest[5][101]; int destdisks[5]; int count; int found; int num; int finish() { int i,j; found = 1;
for(i = 1;i<5;i++) { for(j = 0;j<=num;j++) { if(numbers[i][j]!=dest[i][j]) { found = 0; break; } } if(!found) break; } if(found)return 1; if(disks[b]==num) return 1; return 0; } void move(int s,int n, int d) { int k ; if(found||finish())return; if(n==1) { disks[d]++; numbers[d][disks[d]] = numbers[s][disks[s]]; numbers[s][disks[s]] = 0; disks[s]--;
count++;
}else { k = 7^(s|d);
move(s,n-1,k);
move(s,1,d); move(k,n-1,d); finish(); } } int main(int argc, char *argv[]) { int pos[100],i,j; int tmp[101]; scanf("%d",&num); disks[a] = num; for(i = 0;i<num;i++) numbers[a][i+1] = num-i; for(i = 1;i<=num;i++) { scanf("%d",&pos[i]); pos[i] =(int)pow(2,pos[i]-1); destdisks[pos[i]]++; dest[pos[i]][destdisks[pos[i]]] = i; } for(i = 1;i<5;i++) { for(j = 1;j<=destdisks[i];j++) tmp[destdisks[i]-j+1] = dest[i][j]; for(j = 1;j<=destdisks[i];j++) dest[i][j] = tmp[j]; }
move(a,num,b); if(found) printf("%d",count); else printf("%d",-1); return 0; } // Cheers! | How to find impossible sequense | Juri Krainjukov | 1054. Ханойская башня | 3 дек 2002 03:38 | 1 | I've written program that finds the number of steps but Can't determine whether it's possible or not. var N:integer; s,d:array[1..31] of integer; i,j,t:integer; K:longint; n2:array[0..30] of longint; begin readln(N); for I:=1 to n do read(s[i]); n2[0]:=1; for I:=1 to 30 do n2[i]:=n2[i-1]*2; for I:=1 to n do d[i]:=1; k:=0; for I:=n downto 1 do begin IF D[I]<>S[I] then begin K:=K+N2[i-1]; for j:=1 to 3 do if (s[i]<>j) and (d[i]<>j) then begin t:=j; break; end; for J:=1 to i-1 do if d[j]=d[i] then begin d[j]:=t; end; d[i]:=s[i]; end; end; writeln(k);
end. | how to find a consequence which can't be achieve? | Chen Xiaoke | 1054. Ханойская башня | 2 фев 2002 23:01 | 2 | | A simple problem-> a impossible solution | Simeon Kostenski | 1054. Ханойская башня | 2 фев 2002 15:26 | 5 | Can anyone of those who have solved the problem tell me how ? If you use recursion 31 is a extremely enormous limit and it works years. So a formula? How? it takes 2^k-1 steps to move k disk from one peg to another QH@ > Can anyone of those who have solved the problem tell me > how ? If you use recursion 31 is a extremely enormous limit > and it works years. So a formula? How? I am facing the same problem. Time limite exceeding. Could somone advise me how to optimize the algorithm ?.program hanoit; const maxN=31; var i,n,nmove:integer; current,target:array[1..maxN] of integer; function sama:boolean; var i:integer; begin sama:=true; for i:=1 to N do if current[i]<>target[i] then begin sama:=false; exit; end; end; procedure move(n,to_:integer); begin inc(nmove); current[n]:=to_; if sama then begin writeln(nmove); readln; halt; end; end; procedure hanoi (n, from, to_, temp : integer); begin if n > 0 then begin hanoi (n-1,from,temp,to_); move(n,to_); hanoi(n-1,temp,to_,from); end; end; begin nmove:=0; read(N); for i:=1 to N do begin read(target[i]); current[i]:=1; end; if sama then begin writeln(nmove); readln; halt; end else hanoi(N,1,2,3); writeln(-1 ); end. First of all you shouldn't use readln after you print the solution.It'll wait forever! Good luck! > I am facing the same problem. Time limite exceeding. Could > somone advise me how to optimize the algorithm ?.program > hanoit; > const maxN=31; > var i,n,nmove:integer; > current,target:array[1..maxN] of integer; > > function sama:boolean; > var i:integer; > begin > sama:=true; > for i:=1 to N do if current[i]<>target[i] then > begin > sama:=false; > exit; > end; > end; > > procedure move(n,to_:integer); > begin > inc(nmove); > current[n]:=to_; > if sama then begin writeln(nmove); readln; halt; end; > end; > > procedure hanoi (n, from, to_, temp : integer); > begin > if n > 0 then > begin > hanoi (n-1,from,temp,to_); > move(n,to_); > hanoi(n-1,temp,to_,from); > end; > end; > begin > nmove:=0; > read(N); > for i:=1 to N do > begin > read(target[i]); > current[i]:=1; > end; > if sama then begin writeln(nmove); readln; halt; end > else hanoi(N,1,2,3); > writeln(-1 ); > end. > > faint,of course can't do it in this way...you should find a formula... > > Can anyone of those who have solved the problem tell me > > how ? If you use recursion 31 is a extremely enormous > limit > > and it works years. So a formula? How? > I am facing the same problem. Time limite exceeding. Could > somone advise me how to optimize the algorithm ?.program > hanoit; > const maxN=31; > var i,n,nmove:integer; > current,target:array[1..maxN] of integer; > > function sama:boolean; > var i:integer; > begin > sama:=true; > for i:=1 to N do if current[i]<>target[i] then > begin > sama:=false; > exit; > end; > end; > > procedure move(n,to_:integer); > begin > inc(nmove); > current[n]:=to_; > if sama then begin writeln(nmove); readln; halt; end; > end; > > procedure hanoi (n, from, to_, temp : integer); > begin > if n > 0 then > begin > hanoi (n-1,from,temp,to_); > move(n,to_); > hanoi(n-1,temp,to_,from); > end; > end; > begin > nmove:=0; > read(N); > for i:=1 to N do > begin > read(target[i]); > current[i]:=1; > end; > if sama then begin writeln(nmove); readln; halt; end > else hanoi(N,1,2,3); > writeln(-1 ); > end. > > | Who solved problem1054,can you give me a example whose solution is "IMPOSSIBLE" or there is no such example? | Tests | 1054. Ханойская башня | 1 фев 2002 19:25 | 6 | const maxN = 100; pred : array[1..3]of longint = (3,1,2); succ : array[1..3]of longint = (2,3,1); var now,tar : array[0..maxN]of longint; ans,n : longint; procedure Move(v,whi : longint); var i,j,middle : longint; begin if whi=pred[now[v]] then middle:=succ[now[v]] else middle:=pred[now[v]]; for i:=v-1 downto 1 do if now[i]<>middle then Move(i,middle); ans:=ans+1; now[v]:=whi; end; var i : integer; begin read(n); for i:=1 to N do begin read(tar[i]); now[i]:=1; end; for i:=n downto 1 do if tar[i]<>now[i] then Move(i,tar[i]); writeln(ans); end. > 2 > 2 > 1 > > Good luck ! > > QH@ I think the answer is 3! 1 2 --> 2 --> --> 1 3 empty empty 3 empty 1 3 2 1 3 2 empty What wrong with the answer? Is my comprehesion wrong? > > 2 > > 2 > > 1 > > > > Good luck ! > > > > QH@ > > I think the answer is 3! > 1 > 2 --> 2 --> --> 1 > 3 empty empty 3 empty 1 3 2 1 3 2 empty > > What wrong with the answer? Is my comprehesion wrong? > your comprehesion is wrong. because you don't use the optimal agoriythm > > 2 > > 2 > > 1 > > > > Good luck ! > > > > QH@ > > I think the answer is 3! > 1 > 2 --> 2 --> --> 1 > 3 empty empty 3 empty 1 3 2 1 3 2 empty > > What wrong with the answer? Is my comprehesion wrong? > your comprehesion is wrong. because you don't use the optimal agoriythm |
|
|