254  Towers of Hanoi
Moderator: Board moderators
254  Towers of Hanoi
So I have what appears to me to be a working solution to problem 254, but the judge seems to think otherwise . I have timed out. Not sure what my issue is, maybe i was given input that I did not account for. I could use a push in the right diretion. At least when I type valid data, the program appears to be fast. As far as invalid data, I haven't been able to input anything that will junk it up.
[cpp]
#include <iostream>
#include <cmath>
using namespace std;
const int PROGRAM_END = 0;
const int MAX_DISKS = 100;
const int TOWER_COUNT = 3;
int movesToMake = 0;
int moves = 0;
bool quit = false;
void Recurise (int tower[], int numb, int begin, int finish, int hold);
void moveRing(int tower[], int to, int from);
int main()
{
int tower[TOWER_COUNT];
int diskCount = 0;
while(cin >> diskCount >> movesToMake)
{
if (diskCount == 0 && movesToMake == 0)
return 0;
if (movesToMake < 0 
diskCount < 0 
diskCount > MAX_DISKS 
movesToMake > (pow(2,diskCount) 1))
{
continue;
}
moves = 0;
quit = false;
tower[0] = diskCount;
tower[1] = 0;
tower[2] = 0;
Recurise(tower,diskCount,0,1,2);
cout << tower[0] << " " << tower[1] << " " << tower[2] << endl;
}
return 0;
}
void Recurise (int tower[], int numb, int begin, int finish, int hold)
{
if (numb == 0)
return;
Recurise(tower, numb1,begin, hold, finish);
moveRing(tower, begin, finish);
if (quit)
return;
Recurise(tower, numb1,hold, finish, begin);
}
void moveRing(int tower[], int from, int to)
{
if (moves++ < movesToMake)
{
tower[to]++;
tower[from];
}
else
{
quit = true;
}
return;
}
[/cpp]
[cpp]
#include <iostream>
#include <cmath>
using namespace std;
const int PROGRAM_END = 0;
const int MAX_DISKS = 100;
const int TOWER_COUNT = 3;
int movesToMake = 0;
int moves = 0;
bool quit = false;
void Recurise (int tower[], int numb, int begin, int finish, int hold);
void moveRing(int tower[], int to, int from);
int main()
{
int tower[TOWER_COUNT];
int diskCount = 0;
while(cin >> diskCount >> movesToMake)
{
if (diskCount == 0 && movesToMake == 0)
return 0;
if (movesToMake < 0 
diskCount < 0 
diskCount > MAX_DISKS 
movesToMake > (pow(2,diskCount) 1))
{
continue;
}
moves = 0;
quit = false;
tower[0] = diskCount;
tower[1] = 0;
tower[2] = 0;
Recurise(tower,diskCount,0,1,2);
cout << tower[0] << " " << tower[1] << " " << tower[2] << endl;
}
return 0;
}
void Recurise (int tower[], int numb, int begin, int finish, int hold)
{
if (numb == 0)
return;
Recurise(tower, numb1,begin, hold, finish);
moveRing(tower, begin, finish);
if (quit)
return;
Recurise(tower, numb1,hold, finish, begin);
}
void moveRing(int tower[], int from, int to)
{
if (moves++ < movesToMake)
{
tower[to]++;
tower[from];
}
else
{
quit = true;
}
return;
}
[/cpp]
Sure, my algorithm is like this:
Given m, n
If k is the largest k such that m >= 2^k1, then we know that we are on the way to move k+1 rings from towr A to another tower(say B), and k rings already moved to another tower(tower C).
So we can directly move k rings to tower B, and then minus m by 2^k1.
For the new m, consider again how many rings are moved from tower B to tower C........and so on.....
Hope you understand what I am saying, I am not good in presentation of idea
Given m, n
If k is the largest k such that m >= 2^k1, then we know that we are on the way to move k+1 rings from towr A to another tower(say B), and k rings already moved to another tower(tower C).
So we can directly move k rings to tower B, and then minus m by 2^k1.
For the new m, consider again how many rings are moved from tower B to tower C........and so on.....
Hope you understand what I am saying, I am not good in presentation of idea

 New poster
 Posts: 1
 Joined: Mon Aug 19, 2002 4:36 pm
254: n=0, m=0 ?
Is the following a valid set of inputs and outputs for problem 254? (Towers of hanoi; input: 'number of discs', 'move index'; output: discs in stack 'A', 'B', 'C' after the moves.)
Input:
0 0
0 0
Output:
0 0 0
This is said: "The input file will consist of a series of lines. Each line will contain two integers n, m: n, lying within the range [0,100], will denote the number of disks and m, belonging to [0,2^n1], will be the number of the last move. The file will end at a line formed by two zeros."
The phrase "The file will end at a line formed by two zeros." seems to be common to many problems, so I'd like to know how to interpret it exactly:
a) The last line of the input will consist of two zeros?
b) The first appearance of a line of two zeros denotes the end of the input?
Option b) would be easier to implement, but afaics option a) is just as valid an interpretation for problems where the end line is a valid line itself. (0 \in [0,100], 0 \in [0,2^0  1] = [0,0])
Mikael Sterner
Input:
0 0
0 0
Output:
0 0 0
This is said: "The input file will consist of a series of lines. Each line will contain two integers n, m: n, lying within the range [0,100], will denote the number of disks and m, belonging to [0,2^n1], will be the number of the last move. The file will end at a line formed by two zeros."
The phrase "The file will end at a line formed by two zeros." seems to be common to many problems, so I'd like to know how to interpret it exactly:
a) The last line of the input will consist of two zeros?
b) The first appearance of a line of two zeros denotes the end of the input?
Option b) would be easier to implement, but afaics option a) is just as valid an interpretation for problems where the end line is a valid line itself. (0 \in [0,100], 0 \in [0,2^0  1] = [0,0])
Mikael Sterner

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
254 Tower of Hanoi W.A
Hi, come kind soul please help me.
I keep getting W.A. for this question
Is there a faster solution rather than the solution that i am using now???
#include <iostream.h>
#include <math.h>
int main (void)
{
int N;
int moves, temp, temp2, k;
int one_c;
int one_now, one_nxt;
int AA, BB, CC;
while (cin >> N >> moves)
{
if (N == 0 && moves == 0)
{
break;
}
one_c = 1;
AA = N;
BB = 0;
CC = 0;
while (1)
{
k = 0;
for (k = 0; k <= moves; k++)
{
temp = (int)pow(2,k);
temp2 = (int)pow(2,k+1);
if (temp <= moves && temp2 > moves)
{
break;
}
}
one_now = one_c;
if (k == 0)
{
one_nxt = one_now + 1;
if (one_nxt > 3)
{
one_nxt = 3;
}
switch (one_now)
{
case 1: AA;
break;
case 2: BB;
break;
case 3: CC;
break;
default: cout << "something wrong" << endl;
break;
}
switch (one_nxt)
{
case 1: AA++;
break;
case 2: BB++;
break;
case 3: CC++;
break;
default: cout << "something wrong" << endl;
break;
}
break;
}
if (k%2 == 0)
{
one_nxt = one_c + 2;
if (one_nxt > 3)
{
one_nxt = one_nxt  3;
}
}
else if (k%2 == 1)
{
one_nxt = one_c + 1;
if (one_nxt > 3)
{
one_nxt = one_nxt  3;
}
}
switch (one_now)
{
case 1: AA = AA  k  1;
break;
case 2: BB = BB  k  1;
break;
case 3: CC = CC  k  1;
break;
default: cout << "something wrong" << endl;
break;
}
switch (one_nxt)
{
case 1: AA = AA + k;
break;
case 2: BB = BB + k;
break;
case 3: CC = CC + k;
break;
default: cout << "something wrong" << endl;
}
temp = one_nxt + one_c;
switch ((temp))
{
case 3: CC = CC +1;
break;
case 4: BB = BB +1;
break;
case 5: AA = AA +1;
break;
default: cout << "something wrong" << endl;
break;
}
moves = (long)pow(2,k);
if (moves <= 0)
{
break;
}
one_c = one_nxt;
}
cout << AA << " " << BB << " " << CC << endl;
}
return 0;
}
I keep getting W.A. for this question
Is there a faster solution rather than the solution that i am using now???
#include <iostream.h>
#include <math.h>
int main (void)
{
int N;
int moves, temp, temp2, k;
int one_c;
int one_now, one_nxt;
int AA, BB, CC;
while (cin >> N >> moves)
{
if (N == 0 && moves == 0)
{
break;
}
one_c = 1;
AA = N;
BB = 0;
CC = 0;
while (1)
{
k = 0;
for (k = 0; k <= moves; k++)
{
temp = (int)pow(2,k);
temp2 = (int)pow(2,k+1);
if (temp <= moves && temp2 > moves)
{
break;
}
}
one_now = one_c;
if (k == 0)
{
one_nxt = one_now + 1;
if (one_nxt > 3)
{
one_nxt = 3;
}
switch (one_now)
{
case 1: AA;
break;
case 2: BB;
break;
case 3: CC;
break;
default: cout << "something wrong" << endl;
break;
}
switch (one_nxt)
{
case 1: AA++;
break;
case 2: BB++;
break;
case 3: CC++;
break;
default: cout << "something wrong" << endl;
break;
}
break;
}
if (k%2 == 0)
{
one_nxt = one_c + 2;
if (one_nxt > 3)
{
one_nxt = one_nxt  3;
}
}
else if (k%2 == 1)
{
one_nxt = one_c + 1;
if (one_nxt > 3)
{
one_nxt = one_nxt  3;
}
}
switch (one_now)
{
case 1: AA = AA  k  1;
break;
case 2: BB = BB  k  1;
break;
case 3: CC = CC  k  1;
break;
default: cout << "something wrong" << endl;
break;
}
switch (one_nxt)
{
case 1: AA = AA + k;
break;
case 2: BB = BB + k;
break;
case 3: CC = CC + k;
break;
default: cout << "something wrong" << endl;
}
temp = one_nxt + one_c;
switch ((temp))
{
case 3: CC = CC +1;
break;
case 4: BB = BB +1;
break;
case 5: AA = AA +1;
break;
default: cout << "something wrong" << endl;
break;
}
moves = (long)pow(2,k);
if (moves <= 0)
{
break;
}
one_c = one_nxt;
}
cout << AA << " " << BB << " " << CC << endl;
}
return 0;
}