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

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 Jun 19, 2012 11:13 pm

First search for existing threads. Post to an existing thread if you can't figure out your problem so there won't be 139 threads about the same 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

Post by gsingh93 » Mon Jul 09, 2012 1:16 am

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.LinkedList;
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();
		lists = new LinkedList[n];
		for (int i = 0; i < n; i++) {
			posMap.put(i, i);
			lists[i] = new LinkedList<Integer>();
			lists[i].add(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);
		lists[block].add(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);
		lists[posB].add(a);
	}

	/**
	 * 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());
		List<Integer> subList = new LinkedList<Integer>(tempList);

		tempList.clear();

		Integer pos = posMap.get(b);
		lists[pos].addAll(subList);
		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

Post by Sabiha_Fancy » Mon Jul 16, 2012 3:52 pm

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)
{
struct node *head;
int i;
for(i=0; i<n; ++i)
{
head = a;
head = head->next;
printf("%d:",i);
while(head != NULL)
{
printf(" %d",head->value);
head = head->next;
}
if(head == NULL)
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)
{
struct node *p,*q,*head;
int tvalue1,tvalue2;
tvalue1 = table[box1];

head = a[tvalue1];
q = head;
head = head->next;
while((head->value != box1) && (head != NULL))
{
head = head->next;
q = q->next;
}
if((head != NULL) && (head->value == box1))
{
p = head;
q->next = head->next;
}
tvalue2 = table[box2];
head = a[tvalue2];
head = head->next;
while((head->value != box2) && (head != NULL))
{
head = head->next;
}
if((head != NULL) && (head->value == box2))
{
p->next = head->next;
head->next = p;
table[box1] = tvalue2;
}
}

void move_over(int box1,int box2,int n)
{
struct node *p,*q,*head;
int tvalue1,tvalue2,flag = 0;
tvalue1 = table[box1];

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

}
}

void pile_onto(int box1,int box2,int n)
{
struct node *p,*q,*head,*tail,*front;
int tvalue1,tvalue2,flag1=0;

tvalue1 = table[box1];
head = a[tvalue1];
q = head;
front = q;
head = head->next;
while(head != NULL)
{
if(head->value == box1)
{
p = head;
front = q;
flag1 = 1;
}
head = head->next;
q = q->next;
if(head == NULL)
{
tail = q;
}
}

if(head == NULL)
front->next = head;

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

void pile_over(int box1,int box2,int n)
{
struct node *p,*q,*head,*tail,*front;
int tvalue1,tvalue2,flag=0,flag1=0;

tvalue1 = table[box1];
head = a[tvalue1];
q = head;
front = q;
head = head->next;
while(head != NULL)
{
if(head->value == box1)
{
p = head;
front = q;
flag1 = 1;
}
head = head->next;
q = q->next;
if(head == NULL)
{
tail = q;
}
}

if(head == NULL)
front->next = head;

tvalue2 = table[box2];
head = a[tvalue2];
q = head;
head = head->next;
while(head != NULL)
{
if(head->value == box2)
flag = 1;
head = head->next;
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

Post by brianfry713 » Mon Jul 16, 2012 11:31 pm

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

Post by brianfry713 » Mon Jul 16, 2012 11:34 pm

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

Post by gsingh93 » Tue Jul 17, 2012 2:22 am

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

Post by Sabiha_Fancy » Tue Jul 17, 2012 9:52 pm

Thank you
Fancy

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

Re: 101 WA Java

Post by brianfry713 » Wed Jul 18, 2012 12:05 am

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

Post by Atkins » Sat Sep 08, 2012 8:23 pm

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 :roll:

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

101 , Code in C++, Runtime error

Post by Atkins » Sat Sep 08, 2012 10:03 pm

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 :roll:

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

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

Post by SirHero » Thu Sep 13, 2012 10:21 pm

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

Post by aaa111 » Wed Sep 19, 2012 2:06 pm

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  *Head;
	Node  *Owner;
	Node  *Moved_To;
}List;

void Init_Data(List *list,int size);
void Init(List *list);
void Add_Node(List *list,int Data,int flag);
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->Head  = (Node *)malloc(sizeof(Node)*1);
	
	list->Start		  = list->Head;
	list->Head->Next  = list->Head;
	list->Head->Prev  = list->Head;	
	list->Moved_To    = list->Head;	
	list->Owner       = NULL;
	list->Head->value = 0;
}

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

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

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)
	{
		list[node->value].Moved_To = list[node_b->value].Head;	
		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;

	list->Head->Prev   = node_a_end;		
}

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)
	{
		list[node->value].Moved_To = list[num2].Head;	
		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;

	list->Head->Prev   = node_a_end;		
}

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

		list[Curr->value].Owner->Prev = list[Curr->value].Head;
		list[Curr->value].Owner->Next = list[Curr->value].Head;		
		list[Curr->value].Head->Next  = list[Curr->value].Owner;
		list[Curr->value].Head->Prev  = list[Curr->value].Owner;
		list[Curr->value].Moved_To    = list[Curr->value].Head;

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

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

	free(list->Owner);

	free(list->Head);

	list->Head = NULL;
}

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

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

	return node;
}

void Add_Node(List *list,int Data,int flag)
{
	Node *node = Create_Node();
	
	Node *Head  = list->Head;
	node->value = Data;
	
	node->Prev       = Head->Prev;
	node->Next       = Head;
	Head->Prev->Next = node;
	Head->Prev		 = node;
	
	if(flag)
		list->Owner      = node;
}

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

	if(list->Head->Prev == list->Head || list->Head->Next == list->Head)
	{
		return;
	}

	Curr = list->Head->Next;

	while(Curr != list->Head)
	{
		printf("%d",Curr->value);
		Curr = Curr->Next;
		if(Curr != list->Head)
			printf(" ");
	}	
}

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

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

Post by mainul07 » Fri Oct 05, 2012 1:56 pm

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

Post by IvanLH » Thu Nov 08, 2012 3:11 am

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());}
}//Fin del método operadores.
}//Fin de la clase.

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

Re: 101 The Blocks Problem - Runtime Error

Post by brianfry713 » Fri Nov 09, 2012 12:56 am

Don't put any trailing spaces on a line
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”