101 - The Blocks Problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

hasan_mist
New poster
Posts: 5
Joined: Wed Apr 23, 2014 8:26 am

Re: Problem 101 Java Wrong Answer

Post by hasan_mist » Wed Apr 23, 2014 8:33 am

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

hasan_mist
New poster
Posts: 5
Joined: Wed Apr 23, 2014 8:26 am

Re: Problem 101 Java Wrong Answer

Post by hasan_mist » Wed Apr 23, 2014 8:40 am

brianfry713 wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Problem 101 Java Wrong Answer

Post by brianfry713 » Wed Apr 23, 2014 7:59 pm

Post your code.
Check input and AC output for thousands of problems on uDebug!

hasan_mist
New poster
Posts: 5
Joined: Wed Apr 23, 2014 8:26 am

Re: Problem 101 Java Wrong Answer

Post by hasan_mist » Thu Apr 24, 2014 7:12 am

brianfry713 wrote: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
New poster
Posts: 5
Joined: Wed Apr 23, 2014 8:26 am

Re: Problem 101 Java Wrong Answer

Post by hasan_mist » Thu Apr 24, 2014 7:13 am

hasan_mist wrote:
brianfry713 wrote: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
New poster
Posts: 5
Joined: Wed Apr 23, 2014 8:26 am

Re: Problem 101 Java Wrong Answer

Post by hasan_mist » Thu Apr 24, 2014 7:14 am

hasan_mist wrote:
hasan_mist wrote:
brianfry713 wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Problem 101 Java Wrong Answer

Post by brianfry713 » Thu Apr 24, 2014 8:31 pm

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.
Check input and AC output for thousands of problems on uDebug!

chenqian
New poster
Posts: 5
Joined: Wed Jun 25, 2014 12:21 am

Re: [Solved] 101 - The Blocks Problem | WA | C++

Post by chenqian » Wed Jun 25, 2014 12:22 am

Very useful!!! thx

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 101 - The Blocks Problem

Post by brianfry713 » Sat Oct 18, 2014 2:43 am

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
Check input and AC output for thousands of problems on uDebug!

milesstevenson
New poster
Posts: 10
Joined: Sat Oct 11, 2014 2:47 pm

Re: 101 - The Blocks Problem

Post by milesstevenson » Sat Oct 18, 2014 10:40 am

brianfry713 wrote: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
New poster
Posts: 10
Joined: Sat Oct 11, 2014 2:47 pm

Re: 101 - The Blocks Problem

Post by milesstevenson » Sat Oct 18, 2014 12:20 pm

Ahh. I was incorrectly reading the problem. My code below finally got AC. Thanks Brian!
Last edited by milesstevenson on Thu Mar 05, 2015 2:23 am, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 101 - The Blocks Problem

Post by lighted » Sat Oct 18, 2014 5:08 pm

It will be good if you remove your accepted code. It is a spoiler
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

efagerho
New poster
Posts: 2
Joined: Tue Dec 16, 2014 2:38 am

Re: 101 - The Blocks Problem

Post by efagerho » Tue Dec 16, 2014 4:41 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 101 - The Blocks Problem

Post by brianfry713 » Tue Dec 16, 2014 9:49 pm

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
Check input and AC output for thousands of problems on uDebug!

quanghm
New poster
Posts: 5
Joined: Sat Apr 25, 2015 4:00 pm

Re: 101 - The Blocks Problem

Post by quanghm » Sat Apr 25, 2015 4:19 pm

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"?

Post Reply

Return to “Volume 1 (100-199)”