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

mrunmoy
New poster
Posts: 17
Joined: Mon Apr 09, 2007 3:11 pm
Location: India
Contact:

RE:

Post by mrunmoy »

I can't post the entire code here cuz it does not belong to this category. I have posted it in problem category 101

Only one other questions: is it a problem if i use "fflush(stdin);" in my code?
Best Regards,
Mrunmoy.

I belong to { IDIOTS }
IDIOTS - Intelligent Dynamic & Innovative On-The-Spot!

mrunmoy
New poster
Posts: 17
Joined: Mon Apr 09, 2007 3:11 pm
Location: India
Contact:

Post by mrunmoy »

alright, i post my code here. can someone help me out with the RTE problem reported by online judge?

Code: Select all

*Hided*
i am able to get correct outputs for the sample inputs posted here and also in the problem statement. I have commented out the fflush(stdin); line without which the code wont work i guess (mm.... not sure)
:-$
Last edited by mrunmoy on Tue Dec 11, 2007 8:35 pm, edited 1 time in total.
Best Regards,
Mrunmoy.

I belong to { IDIOTS }
IDIOTS - Intelligent Dynamic & Innovative On-The-Spot!

mrunmoy
New poster
Posts: 17
Joined: Mon Apr 09, 2007 3:11 pm
Location: India
Contact:

Post by mrunmoy »

I read through the problem once again, saw that I was on teh boundary condition of the input length. I changed the length of the cmd[15] to cmd[20] and now it is getting TLE :-(

one thing for sure is. if the judge does something like this to my code to test it is gonna get TLE.

101 < input.dat (i mean redirect input files to my code, it simply does not work out!)

I don't know how to solve this problem. pls help!!!!!!
Best Regards,
Mrunmoy.

I belong to { IDIOTS }
IDIOTS - Intelligent Dynamic & Innovative On-The-Spot!

mrunmoy
New poster
Posts: 17
Joined: Mon Apr 09, 2007 3:11 pm
Location: India
Contact:

Post by mrunmoy »

guys i modified my code to get the input like this:-

Code: Select all

   
*Hided*
Now, the code supports input file redirection. but I am getting WA.

There may be some stupid problem which i am not able to notice.
my code gives the following output from all the sample inputs i collected over the forum:

Code: Select all

input:
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:
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

input:
19
move 1 onto 0
move 0 onto 1
move 0 onto 2
move 2 onto 1
move 4 over 5
move 7 onto 8
move 9 onto 7
move 7 over 9
move 9 over 7
move 11 over 10
move 12 over 10
move 13 over 10
move 14 over 10
move 16 over 15
move 17 over 15
move 18 over 15
move 16 onto 14
pile 17 onto 12
move 15 over 10
pile 17 onto 14
pile 15 over 7
pile 6 over 5
pile 3 onto 9
quit

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

input:
4
move 0 onto 1
move 0 over 2
move 3 onto 0
quit


output:
0:
1: 1
2: 2 0 3
3:
[to get more sample inputs to test your program do a search on 101]

any suggestions?
Last edited by mrunmoy on Tue Dec 11, 2007 8:38 pm, edited 2 times in total.
Best Regards,
Mrunmoy.

I belong to { IDIOTS }
IDIOTS - Intelligent Dynamic & Innovative On-The-Spot!

mrunmoy
New poster
Posts: 17
Joined: Mon Apr 09, 2007 3:11 pm
Location: India
Contact:

solved!

Post by mrunmoy »

thanks guys i got it AC now.

The problem was with the output that i was printing. There was an extra '\n' at the end of the output

<i really had fun solving this! > :lol:
Best Regards,
Mrunmoy.

I belong to { IDIOTS }
IDIOTS - Intelligent Dynamic & Innovative On-The-Spot!

lotoren
New poster
Posts: 6
Joined: Sun Dec 23, 2007 11:11 am
Location: China

Post by lotoren »

I also got RTE, but on POJ, I got AC.

http://acm.pku.edu.cn/JudgeOnline/problemlist

This is my code. Can anybody tell me why RTE on VOJ. Thanks A LOT!

Code: Select all


/*HIDE*/

Last edited by lotoren on Tue Dec 25, 2007 6:50 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Probably because you forgot to return 0 from main(). Non-zero exit code is treated as a runtime error now (as it should be).

lotoren
New poster
Posts: 6
Joined: Sun Dec 23, 2007 11:11 am
Location: China

Post by lotoren »

mf wrote:Probably because you forgot to return 0 from main(). Non-zero exit code is treated as a runtime error now (as it should be).
THANks A LOT, mf!
I GOT AC & Rank 31:)

mooseelkdog
New poster
Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights

Runtime Error

Post by mooseelkdog »

Can anyone see how this returns a runtime error?
I have tried everything it seems, other inputs people have, etc. (and I have looked at other posts too), but my code is accessing memory somewhere it shouldn't be.

Thanks for anything!

Code: Select all


Sorry, ended up being a vector which wasn't popped!!

Don't worry, I'll post again soon I am sure!!

gadams00
New poster
Posts: 1
Joined: Tue Jan 29, 2008 8:28 am

java problem 101 (the blocks problem) TLE

Post by gadams00 »

I keep getting TLE on problem 101, with a 3.000 sec run time, while using Eclipse 3.3 profiling on my laptop using sun JDK 1.6.0, I get execution times of .02-.03 seconds.

Here's my code:

Code: Select all

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws IOException {
		//BufferedReader lReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedReader lReader = new BufferedReader(new InputStreamReader(new FileInputStream("in.txt")));
		String lInput = lReader.readLine().trim();
		int lNumBlocks = Integer.parseInt(lInput);
		new Main(lNumBlocks).start(lReader);
	}
	
	public Main(int numBlocks) {
		blockSlots = new ArrayList<List<Integer>>(numBlocks);
		for (int i = 0; i < numBlocks; i++) {
			ArrayList<Integer> lNumList = new ArrayList<Integer>(1);
			lNumList.add(i);
			blockSlots.add(lNumList);
		}
	}
	
	public void start(BufferedReader lReader) throws IOException {
		Robot lRobot = new Robot();
		String lInput = lReader.readLine();
		while (!lInput.equals("quit")) {
			StringTokenizer lTokenizer = new StringTokenizer(lInput);
			String lCommand = lTokenizer.nextToken();
			if (lCommand.equals("print")) {
				print();
			} else if (lCommand.equals("move") || lCommand.equals("pile")) {
				int lArg1 = Integer.parseInt(lTokenizer.nextToken());
				String lCommandModifier = lTokenizer.nextToken();
				int lArg2 = Integer.parseInt(lTokenizer.nextToken());
				if (lCommand.equals("move")) {
					// move
					if (lCommandModifier.equals("onto")) {
						lRobot.moveOnto(lArg1, lArg2);
					} else if (lCommandModifier.equals("over")) {
						lRobot.moveOver(lArg1, lArg2);
					}
				} else {
					// pile 
					if (lCommandModifier.equals("onto")) {
						lRobot.pileOnto(lArg1, lArg2);
					} else if (lCommandModifier.equals("over")) {
						lRobot.pileOver(lArg1, lArg2);
					}
				}
			}
			lInput = lReader.readLine();
		}
		print();
		
		
	}
	
	private List<List<Integer>> blockSlots;
	
	private void print() {
		for (int i = 0; i < blockSlots.size(); i++) {
			StringBuilder lBuff = new StringBuilder();
			lBuff.append(i + ":");
			for (int lNum : blockSlots.get(i)) {
				lBuff.append(" " + lNum);
			}
			System.out.println(lBuff.toString());
		}
	}
	
	class Robot {
		void moveOnto(int a, int b) {
			if (a == b) return;
			for (List<Integer> lStack : blockSlots) {
				int lIndexOfA = lStack.indexOf(a);
				if (lIndexOfA != -1) {
					while(lStack.size() > lIndexOfA + 1) {
						blockSlots.get(lStack.get(lIndexOfA + 1)).add(lStack.remove(lIndexOfA + 1));
					}
					lStack.remove(lIndexOfA);
					break;
				}
			}
			for (List<Integer> lStack : blockSlots) {
				int lIndexOfB = lStack.indexOf(b);
				if (lIndexOfB != -1) {
					while(lStack.size() > lIndexOfB + 1) {
						blockSlots.get(lStack.get(lIndexOfB + 1)).add(lStack.remove(lIndexOfB + 1));
					}
					lStack.add(a);
					break;
				}
			}
		}
		
		void moveOver(int a, int b) {
			if (a == b) return;
			for (List<Integer> lStack : blockSlots) {
				int lIndexOfA = lStack.indexOf(a);
				if (lIndexOfA != -1) {
					while(lStack.size() > lIndexOfA + 1) {
						blockSlots.get(lStack.get(lIndexOfA + 1)).add(lStack.remove(lIndexOfA + 1));
					}
					lStack.remove(lIndexOfA);
					break;
				}
			}
			for (List<Integer> lStack : blockSlots) {
				if (lStack.contains(b)) {
					lStack.add(a);
					break;
				}
			}
		}
		
		void pileOnto(int a, int b) {
			if (a == b) return;
			List<Integer> lStackContainingB = null;
			for (List<Integer> lStack : blockSlots) {
				int lIndexOfB = lStack.indexOf(b);
				if (lIndexOfB != -1) {
					lStackContainingB = lStack;
					while(lStack.size() > lIndexOfB + 1) {
						blockSlots.get(lStack.get(lIndexOfB + 1)).add(lStack.remove(lIndexOfB + 1));
					}
					break;
				}
			}
			for (List<Integer> lStack : blockSlots) {
				int lIndexOfA = lStack.indexOf(a);
				if (lIndexOfA != -1) {
					while(lStack.size() > lIndexOfA) {
						lStackContainingB.add(lStack.remove(lIndexOfA));
					}
					break;
				}
			}
		}
		
		void pileOver(int a, int b) {
			if (a == b) return;
			List<Integer> lStackContainingB = null;
			for (List<Integer> lStack : blockSlots) {
				if (lStack.contains(b)) {
					lStackContainingB = lStack;
					break;
				}
			}
			for (List<Integer> lStack : blockSlots) {
				int lIndexOfA = lStack.indexOf(a);
				if (lIndexOfA != -1) {
					if (lStack != lStackContainingB) {
						while(lStack.size() > lIndexOfA) {
							lStackContainingB.add(lStack.remove(lIndexOfA));
						}
					}
					break;
				}
			}
		}
	}

}


IronPlatypi
New poster
Posts: 1
Joined: Tue Jan 29, 2008 8:06 pm

RTE as well ....

Post by IronPlatypi »

Hey I'm also getting a RTE for 101, it works fine on my home computer, but when I submit it, it gives me a RTE.

Code: Select all

#include <iostream>
#include <string>
using namespace std;

int bWorld[25][25];
int numBlocks;


void display(){
    int k = 0;
    for (int i = 0; i < numBlocks; i++){
        k = 0;
        cout << i << ": ";
        while (bWorld[i][k] != 100){
            cout << " " << bWorld[i][k];
            k++;
        }
        cout << endl;
    }
}

void Default(int num){
    for (int i = 0; i < numBlocks; i++){
        for (int j = 0; j < numBlocks; j++){
            bWorld[i][j] = 100;
        }  
    }
    
    for (int k = 0; k < num; k++)
        bWorld[k][0] = k;
}

void Reset(int pile, int start){
    while (bWorld[pile][start] != 100){
        bWorld[bWorld[pile][start]][0] = bWorld[pile][start];
        bWorld[pile][start] = 100;     
        start++;
    }
}


void Clean(int pile, int start){
    
    while (bWorld[pile][start] != 100){
        bWorld[pile][start] = 100;
        start++;
    }
}


int SearchRow(int findNum){
    for (int i = 0; i < numBlocks; i++){
        for (int j = 0; j < numBlocks; j++){
            if (bWorld[j][i] == findNum)
                return j;
        }  
    }
}

int SearchCol(int findNum){
    for (int i = 0; i < numBlocks; i++){
        for (int j = 0; j < numBlocks; j++){
            if (bWorld[j][i] == findNum)
                return i;
        }  
    }
}



void MoveOnto(int a, int b){
    int aRow, aCol;
    int bRow, bCol;
    
    aRow = SearchRow(a); 
    bRow = SearchRow(b);
    
    aCol = SearchCol(a);
    bCol = SearchCol(b);
    
    Reset(aRow, aCol + 1);
    Reset(bRow, bCol + 1);
    
    bWorld[bRow][bCol + 1] = bWorld[aRow][aCol];
    bWorld[aRow][aCol] = 100;
}

void MoveOver(int a, int b){
    int aRow, aCol;
    int bRow, bCol;
    
    aRow = SearchRow(a); 
    bRow = SearchRow(b);
    
    aCol = SearchCol(a);
    bCol = SearchCol(b);
    
    while (bWorld[bRow][bCol] != 100)
        bCol++;
        
    Reset(aRow, aCol + 1);
    
    bWorld[bRow][bCol] = a;
    bWorld[aRow][aCol] = 100;
}

void PileOnto(int a, int b){
    int aRow, aCol;
    int bRow, bCol;
    
    aRow = SearchRow(a);
    
    aCol = SearchCol(a);
    bCol = 0;
    
    Reset(b, bCol);

    while (bWorld[aRow][aCol] != 100){ 
        bWorld[b][bCol] = bWorld[aRow][aCol];
        bWorld[aRow][aCol] = 100;
        aCol++;
        bCol++;
    }
}

void PileOver(int a, int b){
    int aRow, aCol;
    int bRow, bCol;
    
    aRow = SearchRow(a); 
    
    aCol = SearchCol(a);
    bCol = 0;
    
    Reset(b, bCol + 1);

    while (bWorld[b][bCol] != 100)
        bCol++;

    while (bWorld[aRow][aCol] != 100){
        bWorld[b][bCol] = bWorld[aRow][aCol];
        bWorld[aRow][aCol] = 100;
        aCol++;
        bCol++;
    }
}

int main(){
    int pileA, pileB;
    string comm1, comm2;

    cin >> numBlocks;
    
    Default(numBlocks);
    
    for (;;){
        cin >> comm1; 
        if (comm1 == "quit")
            break; 
  
        cin >> pileA >> comm2 >> pileB;

        if (pileA != pileB && (pileA >= 0 && pileA < numBlocks) && (pileB >= 0 && pileB < numBlocks)){
            if (comm1 == "move"){
                if (comm2 == "onto")
                    MoveOnto(pileA, pileB);
                else if (comm2 == "over")
                    MoveOver(pileA, pileB);
            }
            else if (comm1 == "pile"){
                if (comm2 == "onto")
                    PileOnto(pileA, pileB);
                else if (comm2 == "over")
                    PileOver(pileA, pileB);
            }
        }
    }

    display();
    return 0;
}
Any help would be much appreciated.

PS: Does anyone know where the type of RTE is put up cuz I can't find that anywhere

Brainless
New poster
Posts: 11
Joined: Sat Dec 29, 2007 2:39 pm

Post by Brainless »

Hello,

Can someone help me for understanding the problem ?

Code: Select all

input :
3
move 1 onto 0
move 0 onto 1
move 0 onto 2
move 2 onto 1
make this output :

Code: Select all

0: 1 2
1: 
2: 0
So why in the sample output below the first 3 lines are :

Code: Select all

0: 0
1: 1 2
2:
Thanks !

smcdowel
New poster
Posts: 1
Joined: Mon Feb 11, 2008 12:15 am

Post by smcdowel »

After attempting to debug perfectly good code for an hour and browsing this and the 100 other threads on this problem I finally found out why my code got WA instead of AC....

despite what it says in the problem statement of "only writting n lines"!!! you must have a newline at the end of the last output so technically i'd call that n+1 lines

for example

0: 0\n
1: 1\n
2: 2\n
3: 3\n
4: 4\n

should be the output if you do this test case

5
quit
the last \n if missing will cause you to have a WA

prljaviGary
New poster
Posts: 1
Joined: Sat Apr 05, 2008 12:22 am
Contact:

101_Blocks in JAVA - RunTime Error

Post by prljaviGary »

Code: Select all

import java.io.*;

class Blocks{
	
	private int n; // broj blokova
	private int[][] bl; 
	private int[] posH; 
	private int[] posV; 
	private int[] h; 
	
	public Blocks() throws IOException{		
		// citanje n
		int a;
		String s = "";
		while(!Character.isWhitespace(a = System.in.read()))
			s += (char)a;
			
		n = Integer.parseInt(s);
		
		// inicijalizacija promenljivih
		bl = new int[n][n];
		posH = new int[n];
		posV = new int[n];
		h = new int[n];
		
		for(int i = 0; i < n; i++){
			for (int j = 0; j < n; j++)
				bl[i][j] = -1;
			bl[i][0] = i;
			posH[i] = i;
			posV[i] = 0;
			h[i] = 0;		
		}
	}
	
	public void moveover(int a, int b){
		int hposHa = h[posH[a]], posVa = posV[a], posHa = posH[a];
		
		h[posH[a]] -= (hposHa - posVa);
		
		for(int i = 0; i < hposHa - posVa; i++){
			int t = bl[posHa][posVa + i + 1];
			
			bl[t][0] = t;
			bl[posHa][posVa + i + 1] = -1;
			h[t] = 0;
			posH[t] = t;
			posV[t] = 0;
		}
		
		pileover(a, b);
	}
	
	
	public void moveonto(int a, int b){
		int hposHb = h[posH[b]], posVb = posV[b], posHb = posH[b];
		
		h[posH[b]] -= (hposHb - posVb);
		
		for(int i = 0; i < hposHb - posVb; i++){
			int t = bl[posHb][posVb + i + 1];
			
			bl[t][0] = t;
			bl[posHb][posVb + i + 1] = -1;
			h[t] = 0;
			posH[t] = t;
			posV[t] = 0;
		}
		
		moveover(a, b);
	}
	
	
	public void pileover(int a, int b){
		int hposHa = h[posH[a]], posVa = posV[a], posHa = posH[a];
		
		h[posH[a]] -= (hposHa - posVa + 1);
		
		for(int i = 0; i < hposHa - posVa + 1; i++){
			bl[posH[b]][++h[posH[b]]] = bl[posHa][posVa + i];
			bl[posHa][posVa + i] = -1;
			posH[bl[posH[b]][h[posH[b]]]] = posH[b];
			posV[bl[posH[b]][h[posH[b]]]] = h[posH[b]];
		}
	}
	
	
	public void pileonto(int a, int b){
		int hposHb = h[posH[b]], posVb = posV[b], posHb = posH[b];
		
		h[posH[b]] -= (hposHb - posVb);
		
		for(int i = 0; i < hposHb - posVb; i++){
			int t = bl[posHb][posVb + i + 1];
			
			bl[t][0] = t;
			bl[posHb][posVb + i + 1] = -1;
			h[t] = 0;
			posH[t] = t;
			posV[t] = 0;
		}
		
		pileover(a, b);
	}
	
	// ispis rezultata
	public void output(){
		for(int i = 0; i < n; i++){
			System.out.print(i + ":");
			for (int j = 0; j < h[i] + 1; j++)
				System.out.print(" " + bl[i][j]);
			//if(i != (n - 1))
				System.out.println();
		}
	}

	public static void main(String[] varg)throws FileNotFoundException, IOException{
		Blocks blk = new Blocks();
		
		start:
		while(true){
			String[] data = new String[4]; // sadrzi elemente jedne naredbe
			
			// citanje naredbe
			for(int i = 0; i < 4; i++){
				int x;
				while((x = System.in.read()) != -1 && Character.isWhitespace(x));
				
				String s = "" + (char)x;
				while((x = System.in.read()) != -1 && !Character.isWhitespace(x))
					s += (char)x;
					
				//if(s.equals("quit"))
				if(i == 0 && (s.substring(0, 4)).equals("quit"))
					break start;
				
				data[i] = s;
			}
			
			int a = Integer.parseInt(data[1]),
				b = Integer.parseInt(data[3]);
				
			// neregularna naredba
			if(a == b || blk.posH[a] == blk.posH[b])
				continue;
			
			// pozivanje metoda
			if(data[0].equals("move"))
				if(data[2].equals("over"))
					blk.moveover(a, b);
				else
					blk.moveonto(a, b);
			else
				if(data[2].equals("over"))
					blk.pileover(a, b);
				else
					blk.pileonto(a, b);
		}
		
		blk.output();
	}
	
}
I keep getting RunTime Error when I submit this code. It runs fine on my pc.
I think it has something to do with input.
Can anyone see what is wrong?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 101_Blocks in JAVA - RunTime Error

Post by Jan »

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 1 (100-199)”