101 - The Blocks Problem

[hasan_mist]

Hello brianfry,
My Code passes your test case.but still WA

[hasan_mist]

Try the I/O I posted at http://online-judge.uva.es/board/viewtopic.php?t=71285

My Code passes all the test cases....but still WA...

[brianfry713]

Post your code.

[hasan_mist]

Post your code.

when i am printing "\n" after the last line...i am getting Presentation Error. But if i give a condition then it is Wrong answer!!!
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#include <stdio.h>

vector<int> block[25];
int track[25];

void removeBlocks(int a)
{
int j, k, t, g;

j = track[a];

for(k = 0; k < block[j].size(); k++) //this finds the block and removes blocks over it
{
if(block[j][k] == a)
{
for(t = k + 1; t < block[j].size(); t++)
{
g = block[j][t];

block[g].push_back(g);

track[g] = g;
}

block[j].erase(block[j].begin() + k + 1, block[j].end());

break;
}
}
}

void doPile(int a, int b)
{
int i, j, k , g, h;

j = track[a];

for(k = 0; k < block[j].size(); k++)
{
if(block[j][k] == a)
{
for(i = k; i < block[j].size(); i++)
{
g = block[j];

h = track;

block[h].push_back(g);

track[g] = track;
}

block[j].erase(block[j].begin() + k, block[j].end());

break;
}
}
}


int main()
{
freopen("in.txt", "r", stdin);
string c, d;

int n, i, j;
int a, b;

cin >> n;

for(i = 0; i < n; i++)
{
block.push_back(i);
track = i;
}

while(cin >> c)
{
if(c == "quit")
break;

cin >> a >> d >> b;

if(a >= n || b >= n)
continue;

if(c == "move")
{
if(d == "onto")
{
if(a != b && track[a] != track)
{
removeBlocks(a);
removeBlocks(b);

j = track;
block[j].push_back(a);
block[track[a]].pop_back();
track[a] = j;
}
}

else
{
if(a != b && track[a] != track)
{
removeBlocks(a);

j = track;

block[j].push_back(a);

block[track[a]].pop_back();

track[a] = j;
}
}
}

else
{
if(d == "onto")
{
if(a != b && track[a] != track) {
removeBlocks(b);
doPile(a, b);
}
}

else
{
if(a != b && track[a] != track)
doPile(a, b);
}
}
}

for(i = 0; i < n; i++)
{
cout << i << " :";
int h = block.size();

for(j = 0; j < h; j++)
{
cout << " ";

cout << block[j];

if(j < h - 1)
cout << " ";
}

//if(i < n- 1) //removing this comment gives PE
cout << endl;
}

return 0;
}

[hasan_mist]

Post your code.

when i am printing "\n" after the last line...i am getting Presentation Error. But if i give a condition then it is Wrong answer!!!
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#include <stdio.h>

vector<int> block[25];
int track[25];

void removeBlocks(int a)
{
int j, k, t, g;

j = track[a];

for(k = 0; k < block[j].size(); k++) //this finds the block and removes blocks over it
{
if(block[j][k] == a)
{
for(t = k + 1; t < block[j].size(); t++)
{
g = block[j][t];

block[g].push_back(g);

track[g] = g;
}

block[j].erase(block[j].begin() + k + 1, block[j].end());

break;
}
}
}

void doPile(int a, int b)
{
int i, j, k , g, h;

j = track[a];

for(k = 0; k < block[j].size(); k++)
{
if(block[j][k] == a)
{
for(i = k; i < block[j].size(); i++)
{
g = block[j];

h = track;

block[h].push_back(g);

track[g] = track;
}

block[j].erase(block[j].begin() + k, block[j].end());

break;
}
}
}


int main()
{
string c, d;

int n, i, j;
int a, b;

cin >> n;

for(i = 0; i < n; i++)
{
block.push_back(i);
track = i;
}

while(cin >> c)
{
if(c == "quit")
break;

cin >> a >> d >> b;

if(a >= n || b >= n)
continue;

if(c == "move")
{
if(d == "onto")
{
if(a != b && track[a] != track)
{
removeBlocks(a);
removeBlocks(b);

j = track;
block[j].push_back(a);
block[track[a]].pop_back();
track[a] = j;
}
}

else
{
if(a != b && track[a] != track)
{
removeBlocks(a);

j = track;

block[j].push_back(a);

block[track[a]].pop_back();

track[a] = j;
}
}
}

else
{
if(d == "onto")
{
if(a != b && track[a] != track) {
removeBlocks(b);
doPile(a, b);
}
}

else
{
if(a != b && track[a] != track)
doPile(a, b);
}
}
}

for(i = 0; i < n; i++)
{
cout << i << " :";
int h = block.size();

for(j = 0; j < h; j++)
{
cout << " ";

cout << block[j];

if(j < h - 1)
cout << " ";
}

//if(i < n- 1) //removing this comment gives PE
cout << endl;
}

return 0;
}

[hasan_mist]

Post your code.

when i am printing "\n" after the last line...i am getting Presentation Error. But if i give a condition then it is Wrong answer!!!
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#include <stdio.h>

vector<int> block[25];
int track[25];

void removeBlocks(int a)
{
int j, k, t, g;

j = track[a];

for(k = 0; k < block[j].size(); k++) //this finds the block and removes blocks over it
{
if(block[j][k] == a)
{
for(t = k + 1; t < block[j].size(); t++)
{
g = block[j][t];

block[g].push_back(g);

track[g] = g;
}

block[j].erase(block[j].begin() + k + 1, block[j].end());

break;
}
}
}

void doPile(int a, int b)
{
int i, j, k , g, h;

j = track[a];

for(k = 0; k < block[j].size(); k++)
{
if(block[j][k] == a)
{
for(i = k; i < block[j].size(); i++)
{
g = block[j];

h = track;

block[h].push_back(g);

track[g] = track;
}

block[j].erase(block[j].begin() + k, block[j].end());

break;
}
}
}


int main()
{
string c, d;

int n, i, j;
int a, b;

cin >> n;

for(i = 0; i < n; i++)
{
block.push_back(i);
track = i;
}

while(cin >> c)
{
if(c == "quit")
break;

cin >> a >> d >> b;

if(a >= n || b >= n)
continue;

if(c == "move")
{
if(d == "onto")
{
if(a != b && track[a] != track)
{
removeBlocks(a);
removeBlocks(b);

j = track;
block[j].push_back(a);
block[track[a]].pop_back();
track[a] = j;
}
}

else
{
if(a != b && track[a] != track)
{
removeBlocks(a);

j = track;

block[j].push_back(a);

block[track[a]].pop_back();

track[a] = j;
}
}
}

else
{
if(d == "onto")
{
if(a != b && track[a] != track) {
removeBlocks(b);
doPile(a, b);
}
}

else
{
if(a != b && track[a] != track)
doPile(a, b);
}
}
}

for(i = 0; i < n; i++)
{
cout << i << ":";
int h = block.size();

for(j = 0; j < h; j++)
{
cout << " ";

cout << block[j];

if(j < h - 1)
cout << " ";
}

//if(i < n- 1) //removing this comment gives PE
cout << endl;
}

return 0;
}

[brianfry713]

Don't read from a file.

You're printing extra spaces, if you run your code on the sample input, it should match the sample output exactly.

There should be a newline char at the end of the last line.

[chenqian]

Very useful!!! thx

[brianfry713]

Input:

Code: Select all

3
move 0 onto 1
move 1 onto 2
quit

AC output:

Code: Select all

0: 0
1:
2: 2 1

[milesstevenson]

Input:

Code: Select all

3
move 0 onto 1
move 1 onto 2
quit

AC output:

Code: Select all

0: 0
1:
2: 2 1

How is it that this is a valid solution? Why isn't the valid solution the following:

Code: Select all

0:
1: 0
2: 2 1

[milesstevenson]

Ahh. I was incorrectly reading the problem. My code below finally got AC. Thanks Brian!

[lighted]

It will be good if you remove your accepted code. It is a spoiler

[efagerho]

There seems to be a possibility for an infinite loop in the current description. Assume that I have the situation:

0: a 1
1: b 0

If I now initiate the command "move a onto b", then the following happens:

1. I move the block on top of "a" to its initial position, so I put it on top of pile 1 and b has now "0 1" on top.

2. I move the blocks on top of "b" to their initial position, so now "a" has "0" on top.

Notice that after step (2) there is again a block on top of a. However, this is not considered an illegal move by the definition. A similar strange situation happens if I have

0: a 0

and I'm doing a move a onto b for any other b.

[brianfry713]

It looks like you don't understand the problem, read the description again.
The blocks are numbered 0 to n - 1.
There are no blocks a or b.
The command "move a onto b" is not valid input.
You can generate AC output for any input at:
http://www.udebug.com/UVa/101

[quanghm]

so my (rejected-time limit) program yields the same output with this guy (6th post)

my program couldn't be accepted from judge.
and error is

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

24
move 9 onto 1
move 23 onto 22
pile 21 over 20
move 16 over 1
pile 8 over 6
pile 1 over 5
move 19 over 1
move 18 over 19
move 10 onto 0
move 7 over 1
move 17 over 14
pile 6 over 1
pile 5 over 6
pile 4 over 0
move 3 over 0
move 2 over 9
move 15 over 1
move 13 over 17
move 12 over 15
move 11 onto 13
pile 0 over 6
pile 14 over 5
pile 20 over 22
pile 23 over 9
move 5 over 9
move 19 onto 2
pile 3 onto 2
pile 0 onto 0
move 23 onto 14
move 5 over 22
quit

my program terminating normally
follow is my answer:
0: 0
1: 1
2: 2 3
3:
4: 4
5:
6: 6
7: 7
8: 8
9: 9
10: 10
11: 11
12: 12
13: 13
14: 14 23
15: 15
16: 16
17: 17
18: 18
19: 19
20: 20
21: 21
22: 22 5
23:

While the 7th post said his accepted program yields

The following is the output from my accepted program:

0: 0
1: 1
2: 2
3: 3
4: 4
5:
6: 6
7: 7
8: 8
9: 9
10: 10
11: 11
12: 12
13: 13
14: 14
15: 15
16: 16
17: 17
18: 18
19: 19
20: 20
21: 21
22: 22 5
23: 23

Now how could that possible for 23 stays at 23 if the last command that touches 23 is "move 23 onto 14"?