101 - The Blocks Problem

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

[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)
:-$

[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!!!!!!

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

[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! >

[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*/

[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]

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]

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]

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]

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]

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]

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]

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]

Search the board first. Don't open a new thread if there is one already.