## 101 - The Blocks Problem

Moderator: Board moderators

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

### Re: 101 - The Blocks Problem

http://acm.uva.es/board/search.php?keyw ... &sr=topics
Then try the I/O posted there against your code. Your code fails for this I/O:
http://acm.uva.es/board/viewtopic.php?t=70902
You can also generate I/O at:
http://www.uvatoolkit.com/problemssolve.php
Check input and AC output for thousands of problems on uDebug!

gsingh93
New poster
Posts: 5
Joined: Sat Jan 07, 2012 8:29 am

### 101 WA Java

I'm getting a WA on problem 101. I'll paste my code and some sample inputs and outputs.

Code: Select all

``````import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class Main {

private static Map<Integer, Integer> posMap = new HashMap<Integer, Integer>();
private static List<Integer> lists[];

@SuppressWarnings("unchecked")
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

// Initialize the data structures
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
posMap.put(i, i);
}

// Parse the input
while (scanner.hasNext()) {
String w1 = scanner.next();
if (w1.equals("quit"))
break;

int n1 = scanner.nextInt();
String w2 = scanner.next();
int n2 = scanner.nextInt();

if (n1 == n2 || posMap.get(n1) == posMap.get(n2))
continue;

if (w1.equals("move")) {
if (w2.equals("onto")) {
moveOnto(n1, n2);
} else if (w2.equals("over")) {
moveOver(n1, n2);
}
} else if (w1.equals("pile")) {
if (w2.equals("onto")) {
pileOnto(n1, n2);
} else if (w2.equals("over")) {
pileOver(n1, n2);
}
}
}

printBlockPositions();
}

/**
* Moves block a onto block b after returning any blocks on top of a and b
* to their initial positions
*/
private static void moveOnto(int a, int b) {
clearStack(b);
clearStack(a);

move(a, b);
}

/**
* Moves block a onto the top of the stack containing block b, returning any
* blocks on top of a to their original positions
*/
private static void moveOver(int a, int b) {
clearStack(a);
move(a, b);
}

/**
* Moves block a and any blocks above block a on top of block b
*/
private static void pileOnto(int a, int b) {
clearStack(b);
movePile(a, b);
}

/**
* Moves block a and any blocks above block a on top of the stack containing
* block b
*
*/
private static void pileOver(int a, int b) {
movePile(a, b);
}

/**
* Prints the positions of all the blocks
*/
private static void printBlockPositions() {
for (int i = 0; i < lists.length; i++) {
List<Integer> list = lists[i];
System.out.print(i + ":");
if (!list.isEmpty())
System.out.print(" ");
for (int j = 0; j < list.size(); j++) {
System.out.print(list.get(j));
if (j != list.size() - 1) {
System.out.print(" ");
}
}
if (i != lists.length - 1)
System.out.println("");
}
}

/**
* Returns the blocks in the stack above the sentinel to their original
* locations
*/
private static void clearStack(int sentinel) {
int col = posMap.get(sentinel);

while (!lists[col].isEmpty()) {
// Get the top block in the same column as block b
int block = lists[col].get(lists[col].size() - 1);
if (block != sentinel)
resetBlock(block);
else
return;
}
}

/**
* Puts a block back in its original location
*/
private static void resetBlock(Integer block) {
lists[posMap.get(block)].remove(block);
posMap.put(block, block);
}

/**
* Moves block a to the stack containing block b
*/
private static void move(int a, int b) {
int posA = posMap.get(a);
int posB = posMap.get(b);

lists[posA].remove(Integer.valueOf(a));
posMap.put(a, posB);
}

/**
* Moves the pile above block a to the stack containing block b
*/
private static void movePile(int a, int b) {
List<Integer> list = lists[posMap.get(a)];
List<Integer> tempList = list.subList(list.indexOf(a), list.size());

tempList.clear();

Integer pos = posMap.get(b);
for (Integer integer : subList) {
posMap.put(integer, pos);
}
}
}
``````
Input 1

Code: Select all

``````10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit``````
Output 1

Code: Select all

``````0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:``````
Input 2

Code: Select all

``````21
move 2 onto 1
move 3 onto 2
move 4 onto 3
move 5 over 1
pile 1 over 10
move 9 over 8
move 11 over 8
pile 3 over 8
pile 8 over 3
move 20 over 19
pile 19 over 18
pile 18 onto 15
move 15 over 3
pile 20 onto 19
pile 19 onto 18
pile 18 over 17
quit``````
Output 2

Code: Select all

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

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

### 101-Blocks Problem

I am getting wrong answer each time i tried to submit it. If any one kindly help me to find out the problem i will be glad.
Here is my code
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>

#define SIZE 25

int table[SIZE];

void createlist(int n);
void move_onto(int box1,int box2,int n);
void move_over(int box1,int box2,int n);
void pile_onto(int box1,int box2,int n);
void pile_over(int box1,int box2,int n);
void print(int n);

struct node {
int value;
struct node *next;
};

struct node *a[SIZE];

int main()
{
int k,box1,box2;
char com1[6];
char com2[6];
int n;
scanf("%d",&n);
createlist(n);
while(1)
{
fflush(stdin);
scanf("%s",com1);
if(strcmp(com1,"quit")==0)
break;
scanf("%d %s %d",&box1,com2,&box2);
fflush(stdin);
if((box1 != box2) && (table[box1] != table[box2]))
{
if(strcmp(com1,"move") == 0)
{
if(strcmp(com2,"onto") == 0)
{
move_onto(box1,box2,n);
}
else
{
move_over(box1,box2,n);
}
}
else
{
if(strcmp(com2,"onto") == 0)
{
pile_onto(box1,box2,n);
}
else
{
pile_over(box1,box2,n);
}
}
}
}
print(n);
return 0;
}

void print(int n)
{
int i;
for(i=0; i<n; ++i)
{
printf("%d:",i);
{
}
printf("\n");
}
}

void createlist(int n)
{
int i;
struct node *p;
for(i=0; i<n; ++i)
{
a = (struct node *) malloc(sizeof(struct node));
a->value = i;
p = (struct node *) malloc(sizeof(struct node));
p->value = i;
p->next = NULL;
a->next = p;
table = i;
}
}

void move_onto(int box1,int box2,int n)
{
int tvalue1,tvalue2;
tvalue1 = table[box1];

{
q = q->next;
}
{
}
tvalue2 = table[box2];
{
}
{
table[box1] = tvalue2;
}
}

void move_over(int box1,int box2,int n)
{
int tvalue1,tvalue2,flag = 0;
tvalue1 = table[box1];

{
q = q->next;
}
{
}
tvalue2 = table[box2];
{
flag = 1;
q = q->next;
}
if(head == NULL && flag == 1)
{
q->next = p;
table[box1] = tvalue2;

}
}

void pile_onto(int box1,int box2,int n)
{
int tvalue1,tvalue2,flag1=0;

tvalue1 = table[box1];
front = q;
{
{
front = q;
flag1 = 1;
}
q = q->next;
{
tail = q;
}
}

tvalue2 = table[box2];
{
}
{
while(p != tail->next)
{
table[p->value] = tvalue2;
p = p->next;
}
}
}

void pile_over(int box1,int box2,int n)
{
int tvalue1,tvalue2,flag=0,flag1=0;

tvalue1 = table[box1];
front = q;
{
{
front = q;
flag1 = 1;
}
q = q->next;
{
tail = q;
}
}

tvalue2 = table[box2];
{
flag = 1;
q = q->next;
}
if((flag == 1) && (flag1 == 1)&& (head == NULL))
{
q->next = p;
tail->next = NULL;
while(p != tail->next)
{
table[p->value] = tvalue2;
p = p->next;
}
}
}
Fancy

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

### Re: 101-Blocks Problem

Check input and AC output for thousands of problems on uDebug!

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

### Re: 101 WA Java

Are you printing a newline at the end of the last line of the output?
Check input and AC output for thousands of problems on uDebug!

gsingh93
New poster
Posts: 5
Joined: Sat Jan 07, 2012 8:29 am

### Re: 101 WA Java

I have this code:

Code: Select all

``````if (i != lists.length - 1)
System.out.println("");``````
Which should print a newline.

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

### Re: 101-Blocks Problem

Thank you
Fancy

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

### Re: 101 WA Java

Doesn't that print a newline at the end of each line except the last one?
Check input and AC output for thousands of problems on uDebug!

Atkins
New poster
Posts: 2
Joined: Sat Sep 08, 2012 8:18 pm

### 101 , Code in C++, Runtime error

my code

Code: Select all

``````#include <iostream>
#include <vector>

class Block {
public:
Block(int n);
int number;
Block * next;
};

class Block_world {
public:
Block_world(int n);
std::vector<Block*> world;
void print();
Block * search(int const num);
int search_pile(int const num);
void null_pre(int const num);
void moveonto(int const a, int const b);
void moveover(int const a, int const b);
void pileonto(int const a, int const b);
void pileover(int const a, int const b);
void return_block(Block * const ptr);
};

Block::Block(int n)
:number(n), next(NULL)
{
}

Block_world::Block_world(int n)
{
for (int i=0; i<n; i++) {
Block * tmp;
tmp=new Block(i);
world.push_back(tmp);
}
}

void Block_world::print()
{
int size=(int)world.size();
Block * ptr=NULL;
for (int i=0; i<size; i++) {
ptr=world.at(i);
std::cout << i << ":";
while (ptr!=NULL) {
std::cout << " " << ptr->number ;
ptr=ptr->next;
}
std::cout << std::endl;
}

}

Block * Block_world::search(int const num)
{
Block * now = NULL;
for (int i=0; i<world.size(); i++) {
now=world.at(i);
if (now!=NULL) {
if (now->number==num) {
return now;
}
while (now->next!=NULL) {
now=now->next;
if (now->number==num) {
return now;
}
}
}
}
return now;
}

int Block_world::search_pile(int const num)
{
Block * now = NULL;
for (int i=0; i<world.size(); i++) {
now=world.at(i);
if (now!=NULL) {
if (now->number==num) {
return i;
}
while (now->next!=NULL) {
now=now->next;
if (now->number==num) {
return i;
}
}
}
}
return -1;
}

void Block_world::null_pre(int const num)
{

Block * now = NULL, * pre = NULL;
for (int i=0; i<world.size(); i++) {
now=world.at(i);
if (now!=NULL) {
if (now->number==num) {
world.at(i)=NULL;
return;
}
pre=now;
now=pre->next;
while (now!=NULL) {
if (now->number==num) {
pre->next=NULL;
return;
}
pre=pre->next;
now=now->next;
}
}
}
}

void Block_world::moveonto(int const a, int const b)
{
Block * aPtr, * bPtr;
if (search_pile(a)==search_pile(b)) {
return;
}
aPtr=search(a);
bPtr=search(b);
null_pre(a);
return_block(aPtr->next);
return_block(bPtr->next);
aPtr->next=NULL;
bPtr->next=aPtr;
}

void Block_world::moveover(int const a, int const b)
{
Block * aPtr, * b_pilePtr;
aPtr=search(a);
b_pilePtr=world.at(search_pile(b));
null_pre(a);
return_block(aPtr->next);
while (b_pilePtr->next!=NULL) {
b_pilePtr=b_pilePtr->next;
}
aPtr->next=NULL;
b_pilePtr->next=aPtr;
}

void Block_world::pileonto(int const a, int const b)
{
Block * aPtr, * bPtr;
if (search_pile(a)==search_pile(b)) {
return;
}
aPtr=search(a);
null_pre(a);
bPtr=search(b);
return_block(bPtr->next);
bPtr->next=aPtr;
}

void Block_world::pileover(int const a, int const b)
{
Block * aPtr, * pos;
int b_pile;
aPtr=search(a);
b_pile=search_pile(b);
null_pre(a);
if (world.at(b_pile)==NULL) {
world.at(b_pile)=aPtr;
return;
}
pos=world.at(b_pile);
while (pos->next!=NULL) {
pos=pos->next;
}
pos->next=aPtr;
}

void Block_world::return_block(Block * const ptr)
{
Block * now=ptr;
Block * next=NULL;
while (now!=NULL) {
next=now->next;

if (world.at(now->number)!=NULL) {
std::cout << "\nerror\n";
}
world.at(now->number)=now;
now->next=NULL;
now=next;
}
}

int main(int argc, const char * argv[])
{
int size, a, b;
char inst1[5], inst2[5];
std::cin >> size;
Block_world i (size);
while (std::cin >> inst1 ) {
if (inst1[0]=='q'&&inst1[1]=='u'&&inst1[2]=='i'&&inst1[3]=='t') {
i.print();
return 0;
}
else {
std::cin >> a >> inst2 >> b;
if (inst1[0]=='m'&&inst1[1]=='o'&&inst1[2]=='v'&&inst1[3]=='e') {
if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
i.moveonto(a, b);
} else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
i.moveover(a, b);
}
} else if (inst1[0]=='p'&&inst1[1]=='i'&&inst1[2]=='l'&&inst1[3]=='e') {
if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
i.pileonto(a, b);
} else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
i.pileover(a, b);
}
}
}
}
//std::cout << "Hello, World!\n";
return 0;
}``````
I try lots of test data on my program and it works!
But still got RE
Can anyone help me

Atkins
New poster
Posts: 2
Joined: Sat Sep 08, 2012 8:18 pm

### 101 , Code in C++, Runtime error

my code

Code: Select all

``````#include <iostream>
#include <vector>

class Block {
public:
Block(int n);
int number;
Block * next;
};

class Block_world {
public:
Block_world(int n);
std::vector<Block*> world;
void print();
Block * search(int const num);
int search_pile(int const num);
void null_pre(int const num);
void moveonto(int const a, int const b);
void moveover(int const a, int const b);
void pileonto(int const a, int const b);
void pileover(int const a, int const b);
void return_block(Block * const ptr);
};

Block::Block(int n)
:number(n), next(NULL)
{
}

Block_world::Block_world(int n)
{
for (int i=0; i<n; i++) {
Block * tmp;
tmp=new Block(i);
world.push_back(tmp);
}
}

void Block_world::print()
{
int size=(int)world.size();
Block * ptr=NULL;
for (int i=0; i<size; i++) {
ptr=world.at(i);
std::cout << i << ":";
while (ptr!=NULL) {
std::cout << " " << ptr->number ;
ptr=ptr->next;
}
std::cout << std::endl;
}

}

Block * Block_world::search(int const num)
{
Block * now = NULL;
for (int i=0; i<world.size(); i++) {
now=world.at(i);
if (now!=NULL) {
if (now->number==num) {
return now;
}
while (now->next!=NULL) {
now=now->next;
if (now->number==num) {
return now;
}
}
}
}
return now;
}

int Block_world::search_pile(int const num)
{
Block * now = NULL;
for (int i=0; i<world.size(); i++) {
now=world.at(i);
if (now!=NULL) {
if (now->number==num) {
return i;
}
while (now->next!=NULL) {
now=now->next;
if (now->number==num) {
return i;
}
}
}
}
return -1;
}

void Block_world::null_pre(int const num)
{

Block * now = NULL, * pre = NULL;
for (int i=0; i<world.size(); i++) {
now=world.at(i);
if (now!=NULL) {
if (now->number==num) {
world.at(i)=NULL;
return;
}
pre=now;
now=pre->next;
while (now!=NULL) {
if (now->number==num) {
pre->next=NULL;
return;
}
pre=pre->next;
now=now->next;
}
}
}
}

void Block_world::moveonto(int const a, int const b)
{
Block * aPtr, * bPtr;
if (search_pile(a)==search_pile(b)) {
return;
}
aPtr=search(a);
bPtr=search(b);
null_pre(a);
return_block(aPtr->next);
return_block(bPtr->next);
aPtr->next=NULL;
bPtr->next=aPtr;
}

void Block_world::moveover(int const a, int const b)
{
Block * aPtr, * b_pilePtr;
aPtr=search(a);
b_pilePtr=world.at(search_pile(b));
null_pre(a);
return_block(aPtr->next);
while (b_pilePtr->next!=NULL) {
b_pilePtr=b_pilePtr->next;
}
aPtr->next=NULL;
b_pilePtr->next=aPtr;
}

void Block_world::pileonto(int const a, int const b)
{
Block * aPtr, * bPtr;
if (search_pile(a)==search_pile(b)) {
return;
}
aPtr=search(a);
null_pre(a);
bPtr=search(b);
return_block(bPtr->next);
bPtr->next=aPtr;
}

void Block_world::pileover(int const a, int const b)
{
Block * aPtr, * pos;
int b_pile;
aPtr=search(a);
b_pile=search_pile(b);
null_pre(a);
if (world.at(b_pile)==NULL) {
world.at(b_pile)=aPtr;
return;
}
pos=world.at(b_pile);
while (pos->next!=NULL) {
pos=pos->next;
}
pos->next=aPtr;
}

void Block_world::return_block(Block * const ptr)
{
Block * now=ptr;
Block * next=NULL;
while (now!=NULL) {
next=now->next;

if (world.at(now->number)!=NULL) {
std::cout << "\nerror\n";
}
world.at(now->number)=now;
now->next=NULL;
now=next;
}
}

int main(int argc, const char * argv[])
{
int size, a, b;
char inst1[5], inst2[5];
std::cin >> size;
Block_world i (size);
while (std::cin >> inst1 ) {
if (inst1[0]=='q'&&inst1[1]=='u'&&inst1[2]=='i'&&inst1[3]=='t') {
i.print();
return 0;
}
else {
std::cin >> a >> inst2 >> b;
if (inst1[0]=='m'&&inst1[1]=='o'&&inst1[2]=='v'&&inst1[3]=='e') {
if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
i.moveonto(a, b);
} else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
i.moveover(a, b);
}
} else if (inst1[0]=='p'&&inst1[1]=='i'&&inst1[2]=='l'&&inst1[3]=='e') {
if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
i.pileonto(a, b);
} else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
i.pileover(a, b);
}
}
}
}
//std::cout << "Hello, World!\n";
return 0;
}``````
I try lots of test data on my program and it works!
But still got RE
Can anyone help me

SirHero
New poster
Posts: 1
Joined: Thu Sep 13, 2012 10:14 pm

### Re: 101 , Code in C++, Runtime error

Code: Select all

``````#include <iostream>
#include <vector>
#include <string>
using namespace std;
int pos[27];
vector<vector<int> > move_onto(vector<vector<int> > v,int a,int b)
{
if(pos[a]!=pos[b])
{
int pos1=pos[a],pos2=pos[b];
int i;
for(i=0;v[pos1][i]!=a;++i);
i++;
for(;i<v[pos1].size();++i)
{
v[v[pos1][i]].push_back(v[pos1][i]);
pos[v[pos1][i]]=v[pos1][i];
v[pos1].erase(v[pos1].begin()+i);
--i;
}
for(i=0;v[pos2][i]!=b;++i);
i++;
for(;i<v[pos2].size();++i)
{
v[v[pos2][i]].push_back(v[pos2][i]);
pos[v[pos2][i]]=v[pos2][i];
v[pos2].erase(v[pos2].begin()+i);
--i;
}
v[pos[b]].push_back(a);
v[pos[a]].erase(v[pos[a]].end()-1);
pos[a]=pos[b];
}
return v;
}
vector<vector<int> > move_over(vector<vector<int> > v,int a,int b)
{
if(pos[a]!=pos[b])
{
int pos1=pos[a],pos2=pos[b];
int i;
for(i=0;v[pos1][i]!=a;++i);
i++;
for(;i<v[pos1].size();++i)
{
v[v[pos1][i]].push_back(v[pos1][i]);
v[pos1].erase(v[pos1].begin()+i);
pos[v[pos1][i]]=v[pos1][i];
--i;
}
v[pos[b]].push_back(a);
v[pos[a]].erase(v[pos[a]].end()-1);
pos[a]=pos[b];
}
return v;
}
vector<vector<int> > pile_onto(vector<vector<int> > v,int a,int b)
{
if(pos[a]!=pos[b])
{
int pos1=pos[a],pos2=pos[b];
int i;
for(i=0;v[pos2][i]!=b;++i);
++i;
for(;i<v[pos2].size();++i)
{
v[v[pos2][i]].push_back(v[pos2][i]);
pos[v[pos2][i]]=v[pos2][i];
v[pos2].erase(v[pos2].begin()+i);
--i;
}
for(i=0;v[pos[a]][i]!=a;++i);
for(;i<v[pos1].size();++i)
{
v[pos[b]].push_back(v[pos[a]][i]);
v[pos1].erase(v[pos1].begin()+i);
pos[v[pos[a]][i]]=pos[b];
--i;
}
}
return v;
}
vector<vector<int> > pile_over(vector<vector<int> > v,int a,int b)
{
if(pos[a]!=pos[b])
{
int pos1=pos[a],pos2=pos[b];
int i;
for(i=0;v[pos1][i]!=a;++i);
for(;i<v[pos1].size();++i)
{
v[pos2].push_back(v[pos1][i]);
int tt=v[pos1][i];
v[pos1].erase(v[pos1].begin()+i);
pos[tt]=pos2;
--i;
}
}
return v;
}

int main()
{
int n;
cin >> n;
vector<vector<int> > v;
for(int i=0;i<n;++i)
{
pos[i]=i;
vector<int> temp;
temp.push_back(i);
v.push_back(temp);
}
while(1)
{
/*for(int i=0;i<v.size();++i)
{
cout << i << ":" << " ";
for(int j=0;j<v[i].size();++j)
{
cout << v[i][j] << " ";
}
cout << endl;
}
for(int i=0;i<v.size();++i) cout << pos[i] << " ";*/
//cout << endl;
string s;
cin >> s;
if(s=="quit")
{
for(int i=0;i<v.size();++i)
{
cout << i << ":" << " ";
for(int j=0;j<v[i].size();++j)
{
cout << v[i][j] << " ";
}
cout << endl;
}
break;
}
else
{
if(s=="move")
{
int a;
cin >> a;
cin >> s;
if(s=="onto")
{
int b;
cin >> b;
v=move_onto(v,a,b);
}
else if(s=="over")
{
int b;
cin >> b;
v=move_over(v,a,b);
}
else
{
break;
}
}
else if(s=="pile")
{
int a;
cin >> a;
cin >> s;
if(s=="onto")
{
int b;
cin >> b;
v=pile_onto(v,a,b);
}
else if(s=="over")
{
int b;
cin >> b;
v=pile_over(v,a,b);
}
else
{
break;
}
}
else
{
break;
}
}
}
return 0;
}
``````
Help me too.
I try to many type of programming but receive only runtime error!

aaa111
New poster
Posts: 14
Joined: Sat Nov 21, 2009 2:55 pm

### Re: 101 , Code in C++, Runtime error

Please Help, I am getting Time Limit each time i submit. I guess my program fell into infinite loop somewhere. Can anybody provide me some critical input.

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>

using namespace std;

#define TRUE  1
#define FALSE 0

typedef struct Node
{
int    value;
struct Node *Next;
struct Node *Prev;
}Node;

typedef struct List
{
Node  *Start;
Node  *Owner;
Node  *Moved_To;
}List;

void Init_Data(List *list,int size);
void Init(List *list);
Node *Create_Node(void);
void Traverse_List(List *list);
void Move_Onto(List *list,int size,int num1,int num2);
void Move_Over(List *list,int size,int num1,int num2);
void Move_Block_Node(List *list,Node *node_a,Node *node_a_end,Node *node_b);
void Remove_Tops(List *list,Node *index,Node *Pos);
void Delete_List(List *list);
void MoveOnto(List *list,List *l1,Node *index,Node *node_a,Node *node_b);
void MoveOver(Node *a_index,Node *b_index,Node *node_a,Node *node_b);
void Pile_Onto(List *list,int size,int num1,int num2);
void PileOnto(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b);
void Pile_Over(List *list,int size,int num1,int num2);
void PileOver(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b);

int main(void)
{
int n;
int i = 0;
int  cmd_a,cmd_b;
int  number_1,number_2;
string ca,cb;
List *list = NULL;

cin >> n;

list = (List *)malloc(sizeof(List) * n);

Init_Data(list,n);

for(i = 0 ; i < n; ++i)
{
printf("%d: ",i);
Traverse_List(&list[i]);
printf("\n");
}

number_1 = number_2 = 0;

while(cin >> ca && ca != "quit")
{
cin >> number_1 >> cb >> number_2;

cmd_a = (ca == "move")? 1 : 2;
cmd_b = (cb == "onto")? 1 : 2;

if(number_1 == number_2)
cmd_a = 3;

switch(cmd_a)
{
case 1:
if(cmd_b == 1)
Move_Onto(list,n,number_1,number_2);
else
Move_Over(list,n,number_1,number_2);
break;
case 2:
if(cmd_b == 1)
Pile_Onto(list,n,number_1,number_2);
else
Pile_Over(list,n,number_1,number_2);
break;
default:
break;
}

for(i = 0 ; i < n; ++i)
{
printf("%d: ",i);
Traverse_List(&list[i]);
printf("\n");
}
}

for(i = 0 ; i < n; ++i)
Delete_List(&list[i]);

free(list);

return 0;
}

void Init(List *list)
{

list->Owner       = NULL;
}

void Init_Data(List *list,int size)
{
int i;

for(i = 0 ; i < size ; ++i)
{
Init(&list[i]);
}
}

void Move_Onto(List *list,int size,int num1,int num2)
{
int  i = 0;
Node *node_a,*node_b;

if(list[num1].Moved_To == list[num2].Moved_To)
return;

node_a = list[num1].Owner;
node_b = list[num2].Owner;

Remove_Tops(list,list[num1].Moved_To,node_a);
Remove_Tops(list,list[num2].Moved_To,node_b);

MoveOnto(&list[num2],&list[num1],list[num1].Moved_To,node_a,node_b);

list[num1].Moved_To = list[num2].Moved_To;
}

void MoveOnto(List *list,List *l1,Node *index,Node *node_a,Node *node_b)
{
if(index->Next == node_a)
{
index->Prev = index;
index->Next = index;
}

node_a->Prev->Next = node_a->Next;

node_a->Next = node_b->Next;
node_a->Prev = node_b;
node_b->Next = node_a;

list->Moved_To->Prev = node_a;
}

void Move_Over(List *list,int size,int num1,int num2)
{
int  i = 0;
Node *node_a,*node_b;

if(list[num1].Moved_To == list[num2].Moved_To)
return;

node_a = list[num1].Owner;
node_b = list[num2].Owner;

Remove_Tops(list,list[num1].Moved_To,node_a);

MoveOver(list[num1].Moved_To,list[num2].Moved_To,node_a,node_b);

list[num1].Moved_To = list[num2].Moved_To;
}

void MoveOver(Node *a_index,Node *b_index,Node *node_a,Node *node_b)
{
if(a_index->Next == node_a)
{
a_index->Prev = a_index;
a_index->Next = a_index;
}

a_index->Prev = node_a->Prev;

node_a->Prev->Next = node_a->Next;

b_index->Prev->Next = node_a;
node_a->Next	    = b_index;
node_a->Prev	    = b_index->Prev;
b_index->Prev		= node_a;
}

void Pile_Onto(List *list,int size,int num1,int num2)
{
int  i = 0;
Node *node,*node_a_start,*node_a_end,*node_b,*node_b_list;

if(list[num1].Moved_To == list[num2].Moved_To)
return;

node_a_start = list[num1].Owner;
node_a_end   = list[num1].Moved_To->Prev;

node_b		 = list[num2].Owner;

Remove_Tops(list,list[num2].Moved_To,node_b);

PileOnto(&list[num2],list[num1].Moved_To,node_a_start,node_a_end,node_b);

node = node_a_start;

while(node != list[num2].Moved_To)
{
node = node->Next;
}
}

void PileOnto(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b)
{
if(index->Next == node_a_start)
{
index->Prev = index;
index->Next = index;
}
else
{
index->Prev = node_a_start->Prev;
}

node_a_start->Prev->Next = node_a_end->Next;

node_a_end->Next   = node_b->Next;
node_a_start->Prev = node_b;
node_b->Next	   = node_a_start;

}

void Pile_Over(List *list,int size,int num1,int num2)
{
int  i = 0;
Node *node,*node_a_start,*node_a_end,*node_b,*node_b_list;

if(list[num1].Moved_To == list[num2].Moved_To)
return;

node_a_start = list[num1].Owner;
node_a_end   = list[num1].Moved_To->Prev;

node_b		 = list[num2].Moved_To->Prev;

node = node_a_start;

PileOver(&list[num2],list[num1].Moved_To,node_a_start,node_a_end,node_b);

while(node != list[num2].Moved_To)
{
node = node->Next;
}
}

void PileOver(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b)
{
if(index->Next == node_a_start)
{
index->Prev = index;
index->Next = index;
}
else
{
index->Prev = node_a_start->Prev;
}

node_a_start->Prev->Next = node_a_end->Next;

node_a_end->Next   = node_b->Next;
node_a_start->Prev = node_b;
node_b->Next	   = node_a_start;

}

void Remove_Tops(List *list,Node *index,Node *Pos)
{
Node *Curr = Pos->Next;
Node *Tmp;

while(Curr != index)
{
Tmp = Curr->Next;

Curr = Tmp;
}

Pos->Next = index;
list[Pos->value].Moved_To->Prev = Pos;
}

void Delete_List(List *list)
{
Node *Curr;

free(list->Owner);

}

Node *Create_Node(void)
{
Node *node = (Node *)malloc(sizeof(Node)*1);

node->Next = NULL;
node->Prev = NULL;

return node;
}

{
Node *node = Create_Node();

node->value = Data;

if(flag)
list->Owner      = node;
}

void Traverse_List(List *list)
{
Node *Curr;

{
return;
}

{
printf("%d",Curr->value);
Curr = Curr->Next;
printf(" ");
}
}
``````

mainul07
New poster
Posts: 8
Joined: Fri Oct 05, 2012 1:35 pm
Location: Chittagong
Contact:

### Re: 101 , Code in C++, Runtime error

Your program can not get any input....modify it than it will work and Runtime error will overcome
Mainul Hassan
Website:http://www.teronga.com/

IvanLH
New poster
Posts: 3
Joined: Thu Nov 08, 2012 12:33 am

### 101 The Blocks Problem - Runtime Error

Hello, i've tried the problem 101 and i get a runtime error even thought when i run my program with commands directly written in the console, and reading form an input file it doesn't shows any exceptions, so here's my code, is in java 6.
import java.util.*;

public class Main{
public static void main(String args[]){
//Declaración de variables, arrays y stacks
Scanner in = new Scanner (System.in);
int numero = in.nextInt();//Lector de numero de cajas.
int op1 = 0;
int op2 = 0;
int d1 = 0;
int d2 = 0;
String c1 = "";
String c2 = "";
Stack[] pos = new Stack[numero];//Array de almacenamiento de los objetos "caja" en forma de stacks
int[] posact = new int[numero];//Array de posicion de cada caja
int bandera = 0;

for(int i = 0; i < posact.length; i++)//Inicialización de las posición de las cajas
posact = i;

for(int i = 0; i < pos.length; i++){//Creación de los stacks de cada columna
pos= new Stack();
pos.push(i);
}

String entr = in.nextLine();//Lector de comandos.

if (entr.equals("quit"))
bandera = 1;

while (bandera != 1){
StringTokenizer t = new StringTokenizer(entr);
try{
c1 = t.nextToken();
d1 = Integer.parseInt(t.nextToken());
c2 = t.nextToken();
d2 = Integer.parseInt(t.nextToken());
}
catch(NoSuchElementException e){}
if (c1.equals("move"))
op1 = 1;

if (c1.equals("pile"))
op1 = 2;

if (c2.equals("onto"))
op2 = 1;

if (c2.equals("over"))
op2 = 2;

if (d1 != d2 && pos[d1] != pos[d2])
operador(pos, posact, op1, op2, d1, d2);

entr = in.nextLine();

if (entr.equals("quit"))
bandera = 1;
}
Stack[] pos2 = new Stack[pos.length];

for ( int i = 0;i < pos2.length; i++){
pos2 = new Stack();

while(!pos.empty()){
int a = Integer.parseInt((pos.pop()).toString());
pos2.push(a);}}

for (int i = 0; i < pos2.length; i++){
System.out.print(i + ": ");

while(pos2.empty() == false){
System.out.print(pos2.pop());
System.out.print(" ");}

System.out.println();}
}//Fin del método main.

public static void operador (Stack[] ma, int[] pos, int oper1, int oper2 , int num1, int num2 ){
if (oper1 == 1 && oper2 == 1){

String a = (ma[pos[num1]].peek()).toString();
String b = (ma[pos[num2]].peek()).toString();
int numt1 = Integer.parseInt(a);
int numt2 = Integer.parseInt(b);

while (numt1 != num1){
int nump1 = Integer.parseInt((ma[pos[num1]].pop()).toString());
ma[numt1].push(nump1);
pos[nump1] = nump1;
numt1 = Integer.parseInt((ma[pos[num1]].peek()).toString());
}

while (numt2 != num2){
int nump2 = Integer.parseInt((ma[pos[num2]].pop()).toString());
ma[numt2].push(nump2);
pos[nump2] = nump2;
numt2 = Integer.parseInt((ma[pos[num2]].peek()).toString());
}

ma[pos[num2]].push(Integer.parseInt((ma[pos[num1]].pop()).toString()));
pos[num1] = pos[num2];
}
if (oper1 == 1 && oper2 == 2){

String a = (ma[pos[num1]].peek()).toString();
int numt1 = Integer.parseInt(a);

while (numt1 != num1){
int nump1 = Integer.parseInt((ma[pos[num1]].pop()).toString());
ma[numt1].push(nump1);
pos[nump1] = nump1;
numt1 = Integer.parseInt((ma[pos[num1]].peek()).toString());
}
ma[pos[num2]].push(Integer.parseInt((ma[pos[num1]].pop()).toString()));
pos[num1] = pos[num2];

}
if(oper1 == 2 && oper2 == 1){

String b = (ma[pos[num2]].peek()).toString();
int numt2 = Integer.parseInt(b);

while (numt2 != num2){
int nump2 = Integer.parseInt((ma[pos[num2]].pop()).toString());
ma[numt2].push(nump2);
pos[nump2] = nump2;
numt2 = Integer.parseInt((ma[pos[num2]].peek()).toString());
}
int bandera = 0;
Stack[] temp = new Stack[ma.length];
temp[1] = new Stack();

while(bandera != 1){
if (ma[pos[num1]].peek().equals(num1))
bandera = 1;
int rec = Integer.parseInt((ma[pos[num1]].pop()).toString());
pos[rec] = pos[num2];
temp[1].push(rec);}

while(!temp[1].empty())
ma[pos[num2]].push(temp[1].pop());
}
if (oper1 == 2 && oper2 == 2){
int bandera = 0;
Stack[] temp = new Stack[ma.length];
temp[1] = new Stack();

while(bandera != 1){

if (ma[pos[num1]].peek().equals(num1))
bandera = 1;
int rec = Integer.parseInt((ma[pos[num1]].pop()).toString());
pos[rec] = pos[num2];
temp[1].push(rec);}

while(!temp[1].empty())
ma[pos[num2]].push(temp[1].pop());}