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

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

sorry i don't know your program..

Post by sds1100 »

sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

manyyak69
New poster
Posts: 2
Joined: Wed Mar 08, 2006 10:27 pm

Post by manyyak69 »

i c that this topic is abandoned, but i need some help...i can*t get to work this problem...it says "wrong answer" when i submit the code...but i can*t find where the mistake is...

code:

Code: Select all

#include <iostream>
#include <queue>
#include <string>

using namespace std;

queue<int> red; //pomoćni red za skidanje

int hrpa[25][25]; //glavna varijabla sa blokovima 
int hrpa_kol[25]; //količina na svakom mjestu
int n; //količina mjesta u zadatku

void display(void)
{
  //funkcija za ispis statusa na ekran
  int j;
  for(int i=0; i<n; ++i)
  {
    cout << i << ":";
    j=0;
    while(j<hrpa_kol[i])
      cout << " " << hrpa[i][j++];        
    cout << endl;  
  }      
}

void trace_b(int koji_blok, int *x, int*y)
{
  //funkcija za traženje koordinata određenog bloka
  for(int i=0; i<n; ++i)
    for(int j=0; j<=hrpa_kol[i]; ++j)
      if(hrpa[i][j]==koji_blok)
      {
        *x=i;
        *y=j;
        return;                         
      }     
}

void push_b(int x, int y)
{
  //funkcija za stavljanje prvog bloka sa reda na blok 
  //sa koordinatama x(mjesto), y(visina)
  int blok=red.front();
  red.pop(); // uzimanje bloka sa reda;
  int t=0;
  for(int i=y+1; i<=hrpa_kol[x]; ++i)
  {
    //stavljanje bloka na mjesto x,y+1 i pomicanje svih
    //blokova koji su eventualno bili iznad za jedno mjesto gore
    t=hrpa[x][i];
    hrpa[x][i]=blok;
    blok=t;
  }
  hrpa_kol[x]++; //količina blokova na mjestu x se povečala za 1 */
}

void pop_b(int x, int y)
{
  //funkcija za uzimanje bloka sa koordinata x,y
  red.push(hrpa[x][y]); //spremanje bloka x,y na red
  for(int i=y; i<=hrpa_kol[x]; ++i)
  {
    //uzimanje bloka x,y i pomicanje svih blokova koji su eventualno bili
    //iznad njega za jedno mjesto dolje
    hrpa[x][i]=hrpa[x][i+1];
    hrpa[x][i+1]=-1;        
  }
  hrpa_kol[x]--; //količina blokova na mjestu x se smanjila za 1     
} 

int main(void)
{
  char naredba1[5], naredba2[5];
  int a, b, xa, ya, xb, yb, xt, yt;
  cin >> n;
  for(int i=0; i<n; ++i)
    hrpa_kol[i]=1;
  for(int i=0; i<n; ++i)
   for(int j=0; j<30; ++j)
     if(j==0) 
        hrpa[i][j]=i;
     else
        hrpa[i][j]=-1;     
  cin >> naredba1;
  while(string(naredba1)!="quit")
  {
    cin >> a >> naredba2 >> b;
    trace_b(a, &xa, &ya);
    trace_b(b, &xb, &yb);
    if(a!=b && a<n && b<n && xa!=xb)
    {
      if(string(naredba1)=="move")
      {
        pop_b(xa, ya);
        if(string(naredba2)=="onto")
           push_b(xb, yb);
          else
           push_b(xb, hrpa_kol[xb]-1);                             
      } else {
        while(hrpa[xa][ya]!=-1)
          pop_b(xa, ya);
        if(string(naredba2)=="onto")
        {
          xt=xb;
          yt=yb;  
          while(!red.empty())
            push_b(xt, yt++);
        } else {
          while(!red.empty())
            push_b(xb, hrpa_kol[xb]-1);
        }       
      }
    }
    
    display();         
    cin >> naredba1;                                
  }    
  display();  
  return 0;    
}
please ignore comments and some variables names...they are in croatian, since i am from croatina... :D :D :D

runtime
New poster
Posts: 3
Joined: Mon Jul 25, 2005 8:39 am
Contact:

Post by runtime »

this code is too much long
It's so difficult to debug
SHU-TE University @ Taiwan
Computer Science & Information Engineering

♨My Blog:
MSN MySpaces
♨My ACM:
RunTime

manyyak69
New poster
Posts: 2
Joined: Wed Mar 08, 2006 10:27 pm

Post by manyyak69 »

lol...i misunderstood the problem.... :lol:

aniketvast
New poster
Posts: 4
Joined: Wed Mar 09, 2005 8:30 am

101 Java WA

Post by aniketvast »

I have tried all the inputs on the board.
It is getting a WA after a few runs I guess since the time is .137

Attaching my code here....maybe it will help someone and inturn myself.
If anyone knows, where I am falling short, lemme know.

import java.io.IOException;
import java.util.StringTokenizer;

/**
* @author aniket vast
*
*/
class Main
{
public int [][] blockworld;
public int maxBlocks = 5;

public static void main(String[] args) throws Exception
{
Main acm101 = new Main();
String sMaxBlocks = acm101.ReadLn(10, true);
acm101.maxBlocks = Integer.parseInt(sMaxBlocks);
acm101.blockworld = new int [acm101.maxBlocks][acm101.maxBlocks];
acm101.initBlockWorld();
String operation1 = "";
String operation2 = "";
String fromBlock = "";
String toBlock = "";

String command = acm101.ReadLn(255, false);
while(!command.startsWith("quit"))
{
StringTokenizer st = new StringTokenizer(command);
if(st.hasMoreTokens())
operation1 = st.nextToken();
if(st.hasMoreTokens())
fromBlock = st.nextToken();
if(st.hasMoreTokens())
operation2 = st.nextToken();
if(st.hasMoreTokens())
toBlock = st.nextToken();
//System.out.println(operation1+" "+fromBlock+" "+operation2+" "+toBlock);
if(acm101.isLegalCommand(fromBlock,toBlock))
acm101.doOperation(operation1,fromBlock,operation2,toBlock);
command = acm101.ReadLn(255, false);
}

acm101.printBlockWorld();
}

public boolean isLegalCommand(String sfromBlock, String stoBlock)
{
if(sfromBlock == null || sfromBlock.trim().length() == 0)
return false;
if(stoBlock == null || stoBlock.trim().length() == 0)
return false;
int fromBlock = Integer.parseInt(sfromBlock);
int toBlock = Integer.parseInt(stoBlock);
if(fromBlock == toBlock)
return false;
if(fromBlock < 0 || fromBlock >= maxBlocks)
return false;
if(toBlock < 0 || toBlock >= maxBlocks)
return false;
for(int rctr = 0; rctr<maxBlocks; rctr++)
{
if(stackContains(rctr,fromBlock) && stackContains(rctr,toBlock))
return false;
}
return true;
}

public boolean stackContains(int rctr, int block)
{
for(int cctr=0; cctr<maxBlocks; cctr++)
{
if(blockworld[rctr][cctr] == block)
return true;
}
return false;
}

public void doOperation(String operation1, String fromBlock, String operation2, String toBlock)
{
if(operation1.equals("move") && operation2.equals("onto"))
doMoveOnto(fromBlock,toBlock);
if(operation1.equals("move") && operation2.equals("over"))
doMoveOver(fromBlock,toBlock);
if(operation1.equals("pile") && operation2.equals("onto"))
doPileOnto(fromBlock,toBlock);
if(operation1.equals("pile") && operation2.equals("over"))
doPileOver(fromBlock,toBlock);
}


public void doMoveOnto(String sfromBlock, String stoBlock)
{
int fromBlock = Integer.parseInt(sfromBlock);
int toBlock = Integer.parseInt(stoBlock);
clearStack(fromBlock);
clearStack(toBlock);
int fromRow = getBlockRow(fromBlock);
int fromCol = getBlockCol(fromBlock);
int toRow = getBlockRow(toBlock);
int toCol = getBlockCol(toBlock);
blockworld[toRow][toCol+1] = fromBlock;
blockworld[fromRow][fromCol] = -1;
}

public void doMoveOver(String sfromBlock, String stoBlock)
{
int fromBlock = Integer.parseInt(sfromBlock);
int toBlock = Integer.parseInt(stoBlock);
clearStack(fromBlock);
int fromRow = getBlockRow(fromBlock);
int fromCol = getBlockCol(fromBlock);
int toRow = getBlockRow(toBlock);
blockworld[toRow][getStackTop(toRow)] = fromBlock;
blockworld[fromRow][fromCol] = -1;
}

public void doPileOnto(String sfromBlock, String stoBlock)
{
int fromBlock = Integer.parseInt(sfromBlock);
int toBlock = Integer.parseInt(stoBlock);
clearStack(toBlock);
moveBlockStack(fromBlock, toBlock);
}

public void doPileOver(String sfromBlock, String stoBlock)
{
int fromBlock = Integer.parseInt(sfromBlock);
int toBlock = Integer.parseInt(stoBlock);
moveBlockStack(fromBlock, toBlock);
}

public void moveBlockStack(int fromBlock, int toBlock)
{
int fromRow = getBlockRow(fromBlock);
int fromCol = getBlockCol(fromBlock);
int toRow = getBlockRow(toBlock);
int destCol = getStackTop(toRow);
for(int cctr=fromCol;cctr<maxBlocks;cctr++, destCol++)
{
if(blockworld[fromRow][cctr] != -1)
{
blockworld [toRow][destCol] = blockworld[fromRow][cctr];
blockworld [fromRow][cctr] = -1;
}
}
}

public int getStackTop(int baseBlock)
{
for(int cctr=0; cctr<maxBlocks; cctr++)
{
if(blockworld[baseBlock][cctr] == -1)
return cctr;
}
return maxBlocks-1;
}

public void clearStack(int baseBlock)
{
int floatingBlock = -1;
int row = getBlockRow(baseBlock);
int col = getBlockCol(baseBlock);
for(int cctr=col+1; cctr<maxBlocks; cctr++)
{
floatingBlock = blockworld [row][cctr];
if(floatingBlock != -1)
{
blockworld [floatingBlock][0] = floatingBlock;
blockworld [row][cctr] = -1;
}
}
}

public int getBlockRow(int block)
{
for(int rctr =0; rctr<maxBlocks; rctr++)
{
for(int cctr=0; cctr<maxBlocks; cctr++)
{
if(blockworld[rctr][cctr] == block)
{
return rctr;
}
}
}
return 0;
}

public int getBlockCol(int block)
{
for(int rctr =0; rctr<maxBlocks; rctr++)
{
for(int cctr=0; cctr<maxBlocks; cctr++)
{
if(blockworld[rctr][cctr] == block)
{
return cctr;
}
}
}
return 0;
}


public void initBlockWorld()
{
for(int rctr=0; rctr<maxBlocks; rctr++)
{
blockworld[rctr][0] = rctr;
for(int cctr=1; cctr<maxBlocks; cctr++)
blockworld[rctr][cctr] = -1;
}
}

public void printBlockWorld()
{
for(int rctr=0; rctr<maxBlocks; rctr++)
{
System.out.print(rctr + ":");
for(int cctr=0; cctr<maxBlocks; cctr++)
{
if(blockworld[rctr][cctr] != -1)
System.out.print(" "+blockworld[rctr][cctr]);
}
System.out.println();
}
}

String ReadLn (int maxLg, boolean strip) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
if(strip)
return (new String (lin,0,lg-1));
return (new String (lin, 0, lg));
}
}

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

Wrong answer in Java can be runtime exception or runtime error.

And from your code, it is clear where the error is:

Code: Select all

public int [][] blockworld; 
public int maxBlocks = 5; 
Are you sure you really tried all the inputs in this board without getting any error? And have you tried the sample input and output? Your code gives:

0: 0

for the sample input.

In the problem, it is stated that:
The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25
But the maxBlocks variable you declared is only 5?
Explaining your algorithm will help others to help you with your problem instead of just pasting code here.

aniketvast
New poster
Posts: 4
Joined: Wed Mar 09, 2005 8:30 am

Post by aniketvast »

For a moment you scared me !!

Well yes the code works for the sample input fine....
Also notice that in the main method I am re-initializing the values of maxBlocks and the blockworld array. The '5' above is not presentable (I agree) but it is not used per se later on.

Thanks
Aniket

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

Sorry if the tone I used scares you. I compiled and ran the code you pasted here using Java 1.4 with the sample input, and your code still prints:

Code: Select all

0: 0
By the way, use code tags next time to make your code more readable.

I noticed in your code that you trim away one character when you read in the number of blocks. Is that necessary? That could be the cause of the WA.

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

Post by WRJ »

Thank you a lot ;)

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni »

hello

I got Presentation Error (but it works) in this problem using an array of stacks.
note that these stacks must to have a method to empty them

gooh luck

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

101 - invalid memory reference

Post by smilitude »

I cannot find the problem, why i am getting RE...

I will be really grateful to you... if you can...
This prog works great in my pc and my gcc compiler!

Code: Select all

--------------- The program I'll compile begins here: ---------------
/*
 * 101 the blocks problem
 * submission 0
 * c()ded at march 22, 2006 at 10:57pm 
 *
 */

#include <stdio.h>
#include <string.h>

struct {
    int block[25];
    int total;
}set[25];

void init(int n) {
    int i,j;
    for(i=0;i<n;i++) {
        set[i].total=1;
        set[i].block[0]=i;
    }
}

void move_onto(int a,int b,int n) {
    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    //this is to search the position of our desired a and b
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    //if there is more block on top of a 
    if(a1.num+1<set[a1.host].total) {
        for(i=a1.num+1;i<set[a1.host].total;i++) {
            set[set[a1.host].block[i]].block[0]=set[a1.host].block[i];
            set[set[a1.host].block[i]].total=1;
        }
        set[a1.host].total=a1.num; //cause we are going to take a out
    }else set[a1.host].total--;
    
    //if there is more block on top of b 
    if(b1.num+1<set[b1.host].total) {
        for(i=b1.num+1;i<set[b1.host].total;i++) {
            set[set[b1.host].block[i]].block[0]=set[b1.host].block[i];
            set[set[b1.host].block[i]].total=1;
        }
        set[b1.host].total=b1.num+1;
    }
    
    set[b1.host].block[set[b1.host].total]=a;
    set[b1.host].total++;
}

void move_over(int a,int b,int n) {
    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    //if there is more block on top of a 
    if(a1.num+1<set[a1.host].total) {
        for(i=a1.num+1;i<set[a1.host].total;i++) {
            set[set[a1.host].block[i]].block[0]=set[a1.host].block[i];
            set[set[a1.host].block[i]].total=1;
        }
        set[a1.host].total=a1.num; //cause we are going to take a out
    }else set[a1.host].total--;
    
    set[b1.host].block[set[b1.host].total]=a;
    set[b1.host].total++;
}

void pile_onto(int a, int b, int n) {
    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    //removing the blocks on the top of b 
    if(b1.num+1<set[b1.host].total) {
        for(i=b1.num+1;i<set[b1.host].total;i++) {
            set[set[b1.host].block[i]].block[0]=set[b1.host].block[i];
            set[set[b1.host].block[i]].total=1;
        }
        set[b1.host].total=b1.num+1;
    }
    
    //copying the total pile
    for(i=a1.num;i<set[a1.host].total;i++) {
        set[b1.host].block[set[b1.host].total++]=set[a1.host].block[i];
    }
    set[a1.host].total=a1.num;
}
 
void pile_over(int a,int b, int n) {

    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    if(a1.host==b1.host) return ;
    //copying the total pile
    for(i=a1.num;i<set[a1.host].total;i++) {
        set[b1.host].block[set[b1.host].total++]=set[a1.host].block[i];
    }
    set[a1.host].total=a1.num;
}

void print(int n) {
    int i,j;
    for(i=0;i<n;i++) {
        printf("%d:",i);
        for(j=0;j<set[i].total;j++) {
            printf(" %d",set[i].block[j]);
        }
    printf("\n");
    }
    
}

int main() {
    int n;
    char order[10];
    int a,b;
    char order2[10];
    char ch;
    
    while(scanf("%d",&n)==1) {
        init(n);
        while(scanf("%s",&order)==1) {
            if(!strcmp(order,"quit")) break;
            scanf("%d %s %d",&a,order2,&b);
            if(!strcmp(order,"move")) {
                if(!strcmp(order2,"onto")) move_onto(a,b,n);
                else move_over(a,b,n);
            }else if(!strcmp(order2,"onto")) pile_onto(a,b,n);
            else pile_over(a,b,n);
            //print(n); scanf("%c",&ch);
        }
    //printf("Final Print\n");
    print(n);
    }
return 0;
}


a lot of thanks from this novice ---
Last edited by smilitude on Sat May 13, 2006 1:02 am, edited 1 time in total.
fahim
#include <smile.h>

Einstein32
New poster
Posts: 1
Joined: Sun Apr 09, 2006 5:12 pm

Problem 101 WA

Post by Einstein32 »

I've tried to solve P101, and all test sequences given on this site/board give correct outputs, but when I send it in, the OJ gives me WA.. What to do?

Here's my code (Pascal)

P.S. Don't pay attention to the Var-Names, because some of them are in Dutch.

Code: Select all

Program P101 (input, output);

Const
     MaxDozen = 25;

Type
    PDoos = ^TDoos;
    TDoos = Record
              Prev  : PDoos;
              MyVal : integer;
              Next  : PDoos;
            End;

Var
   Dozen      : Array [0..MaxDozen] of PDoos;
   Doos       : PDoos;
   ActDozen   : integer;
   ParseReady : Boolean;
   S          : String;

Procedure init;
Var i : integer;
begin
  For i := 0 to MaxDozen-1 do
    Dozen[i] := nil;
  readln(ActDozen);
  ParseReady := Not (ActDozen In [1..MaxDozen]);
  If Not ParseReady Then
  For i := 0 to ActDozen-1 do
  begin
    New(Doos);
    With Doos^ do
    begin
      prev  := nil;
      next  := nil;
      MyVal :=  i ;
    End;
    Dozen[i] := Doos;
  End;
End;


Procedure EmptyStack(Nr : integer);
Var EmptyReady : Boolean;
    NextDoos, CurDoos   : PDoos;
Begin
  CurDoos := Dozen[nr];
  If (Curdoos^.Next <> nil) AND (Curdoos <> Nil) then
  Begin
    NextDoos := CurDoos^.Next;
    if NextDoos^.Next <> Nil then
      EmptyStack(NextDoos^.Myval);
    NextDoos^.prev := Nil;
    CurDoos^.Next  := Nil;
  end;
end;

Procedure AddStackTo(doel, bron : integer);
Var DoelDoos, BronDoos : PDoos;
Begin
  DoelDoos := Dozen[doel];
  BronDoos := Dozen[bron];
  While Doeldoos^.Next <> Nil do
    DoelDoos := DoelDoos^.next;
  If BronDoos^.Prev <> Nil then
    Brondoos^.Prev^.next := Nil;
  BronDoos^.Prev := Doeldoos;
  Doeldoos^.next := Brondoos;
end;

Function HomeDoos(Nr : Integer): integer;
Var CurDoos : PDoos;
Begin
  CurDoos := Dozen[Nr];
  While CurDoos^.Prev <> Nil Do
    CurDoos := CurDoos^.prev;
  HomeDoos := CurDoos^.Myval;
end;

Procedure DoMove(a, b : integer; Var Hoe : String);
Begin
  If Hoe = 'ONTO' then
  Begin
    EmptyStack(a);
    EmptyStack(b);
    AddStackTo(b, a);
  end;
  If Hoe = 'OVER' then
  Begin
    EmptyStack(a);
    AddStackTo(b, a);
  end;
end;


Procedure DoPile(a, b : integer; Var Hoe : String);
Begin
  If Hoe = 'ONTO' then
  Begin
    EmptyStack(b);
    AddStackTo(b, a);
  end;
  If Hoe = 'OVER' then
  Begin
    AddStackTo(b, a);
  end;
end;

Procedure DoOpdracht(var Aktie : String;
                         A     : integer;
                     Var Hoe   : String;
                         B     : integer);
Begin
  if (A <> B) AND (HomeDoos(a) <> HomeDoos(b)) then
  Begin
    If aktie = 'MOVE' then DoMove(a, b, Hoe);
    If aktie = 'PILE' then DoPile(a, b, Hoe);
  end;
end;


Procedure Parse(var S : String);
Var i, A, B, Dbg   : integer;
    Token1, Token2,
    sA, sB         : String;

Begin
  I := 1;
  Token1 := '';
  Token2 := '';
  sA     := '';
  sB     := '';
  While S[i] = ' ' do inc(i);
  While S[i] <> ' ' do
  Begin
    Token1 := Token1 + Upcase(S[i]);
    inc(i);
  end;
  ParseReady := Token1 = 'QUIT';

  If not ParseReady then
  Begin
    While S[i] = ' ' do inc(i);
    While S[i] <> ' ' do
    Begin
      sA := sA + Upcase(S[i]);
      inc(i);
    end;

    While S[i] = ' ' do inc(i);
    While S[i] <> ' ' do
    Begin
      Token2 := Token2 + Upcase(S[i]);
      inc(i);
    end;

    While S[i] = ' ' do inc(i);
    While S[i] in ['0'..'9'] do
    Begin
      sB := sB + Upcase(S[i]);
      inc(i);
    end;
    Val(sA, A, Dbg);
    Val(sB, B, Dbg);
    if (A in [0..Actdozen-1]) And (B In [0..ActDozen-1]) then
      DoOpdracht(Token1, A, Token2, B);
  end;
end;


Procedure PrintResult;
Var i        : integer;
    PrtReady : Boolean;
    Doos     : PDoos;
Begin
  For i := 0 to ActDozen-1 Do
  Begin
    Write(i, ':');
    Doos := Dozen[i];
    PrtReady := Doos^.Prev <> Nil;
    While not PrtReady do
    Begin
      Write(' ', Doos^.MyVal);
      Doos     := Doos^.next;
      PrtReady := Doos = Nil;
    end;
    Writeln;
  end;
end;




Begin
  init;
  While not ParseReady do
  Begin
    FillChar(S, SizeOf(S), ' ');
    Readln(s);
    Parse(s);
    If ParseReady then PrintResult;
  end;
End.

Dang Ha The Hien
New poster
Posts: 1
Joined: Sun Apr 16, 2006 4:49 am

Post by Dang Ha The Hien »

I have tried solving this Problem with an array of linked lists but I don't know why it not acepted. This's my code:

Code: Select all

Program ACM_101;
const
     maxn=25;
     number : set of char = ['0','1','2','3','4','5','6','7','8','9'];
type
    block = ^tblock;
    tblock= record
                 pre, next: block;
                 number, pack: integer;
    end;

var
   n, num1, num2, i, count,r, code: integer;
   command1, command2: string;
   s: string;
   pack: array [0..maxn] of block;
   a: array [0..maxn] of block;

Procedure init(u: integer);
var v: integer;
begin
     u:=a[u]^.next^.number;
     while a[u]^.next<>nil do
     begin
          v:=a[u]^.next^.number;
          a[u]^.next:=nil;
          a[v]^.pre:=nil;
          a[v]^.pack:=v;
          pack[v]:=a[v];
          u:=v;
     end;
     a[u]^.pre:=nil;
     a[u]^.pack:=u;
     pack[u]:=a[u];
end;
Procedure move_onto(u, v: integer);
begin
     if u=v then exit;
     if a[u]^.pack=a[v]^.pack then exit;
     if a[v]^.next<>nil then init(v);
     if a[u]^.next<>nil then init(u);
     if pack[a[u]^.pack]=a[u] then pack[a[u]^.pack]:=nil;
     if a[u]^.pre <> nil then
        a[a[u]^.pre^.number]^.next:=nil;
     a[v]^.next:=a[u];
     a[u]^.pre:=a[v];
     a[u]^.pack:=a[v]^.pack;
end;
Procedure move_over(u, v: integer);
begin
     if u=v then exit;
     if a[u]^.pack=a[v]^.pack then exit;
     if a[u]^.next<>nil then init(u);
     while a[v]^.next<>nil do
           v:=a[v]^.next^.number;
     move_onto(u, v);
end;
Procedure pile_onto(u, v: integer);
begin
     if u=v then exit;
     if a[u]^.pack=a[v]^.pack then exit;
     if a[v]^.next<>nil then init(v);
     if pack[a[u]^.pack]=a[u] then pack[a[u]^.pack]:=nil;
     if a[u]^.pre <> nil then
        a[a[u]^.pre^.number]^.next:=nil;
     a[v]^.next:=a[u];
     a[u]^.pre:=a[v];
     a[u]^.pack:=a[v]^.pack;
     while a[u]^.next<>nil do
     begin
          u:=a[u]^.next^.number;
          a[u]^.pack:=a[v]^.pack;
     end;
end;
Procedure pile_over(u, v: integer);
begin
     if u=v then exit;
     if a[u]^.pack=a[v]^.pack then exit;
     while a[v]^.next<>nil do v:=a[v]^.next^.number;
     pile_onto(u, v);
end;
Procedure output;
var u: block;
begin
     for i:=0 to n do
     begin
          u:=pack[i];
          write(i,': ');
         while u<>nil do
         begin
              write(u^.number,' ');
              u:=u^.next;
         end;
         writeln{(fo)};
     end;
end;
Begin
     readln(n);
     n:=n-1;
     for i:=0 to n do
     begin
          new(a[i]);
          a[i]^.pre:=nil;
          a[i]^.next:=nil;
          a[i]^.number:=i;
          a[i]^.pack:=i;
          pack[i]:=a[i];
     end;
     readln(s);
     while s[1]<>'q' do
     begin
          command1:= s[1];
          count:=6;
          while not (s[count] in number) do count:=count+1;
          val(s[count],num1,code);
          if s[count+1] in number then
          begin
               count:=count+1;
               val(s[count],r,code);
               num1:=num1*10+r;
          end;
          count:=count+1;
          while s[count]=' ' do count:=count+1;
          command2:=s[count]+s[count+1];
          count:=count+5;
          while not (s[count] in number) do count:=count+1;
          val(s[count],num2,code);
          if ((count+1)<=length(s)) and (s[count+1] in number) then
          begin
               count:=count+1;
               val(s[count],r,code);
               num1:=num1*10+r;
          end;
          if command1='m' then
          begin
             if command2='on' then
                  move_onto(num1, num2)
             else
                 move_over(num1, num2);
          end
          else
              if command2='on' then
                 pile_onto(num1, num2)
              else
                  pile_over(num1, num2);
          readln(s);
     end;
     output;
end.
Please help me!

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

finally...

Post by smilitude »

I finally find out a stupid problem with my code... but still the code isnt right ...
I am confused now... I need to see some IO. Cause the problem i have found in my code, could easily be detected if i tested it with some effiecient IO before submitting it ...

Code: Select all

/*
 * 101 the blocks problem
 * submission 1 RE - invalid memory ref
 * c()ded at march 22, 2006 at 10:57pm 
 *
 */

#include <stdio.h>
#include <string.h>

struct {
    int block[30];
    int total;
}set[30];

void init(int n) {
    int i,j;
    for(i=0;i<n;i++) {
        set[i].total=1;
        set[i].block[0]=i;
    }
}

void move_onto(int a,int b,int n) {
    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    //this is to search the position of our desired a and b
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    //if there is more block on top of a 
    if(a1.num+1<set[a1.host].total) {
        for(i=a1.num+1;i<set[a1.host].total;i++) {
            set[set[a1.host].block[i]].block[0]=set[a1.host].block[i]; //init position
            set[set[a1.host].block[i]].total=1;
        }
        set[a1.host].total=a1.num; //cause we are going to take a out
    }else set[a1.host].total--;
    
    //now search one more time for new address of b
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    
    //if there is more block on top of b 
    if(b1.num+1<set[b1.host].total) {
        for(i=b1.num+1;i<set[b1.host].total;i++) {
            set[set[b1.host].block[i]].block[0]=set[b1.host].block[i];
            set[set[b1.host].block[i]].total=1;
        }
        set[b1.host].total=b1.num+1;
    }
    
    set[b1.host].block[set[b1.host].total]=a;
    set[b1.host].total++;
}

void move_over(int a,int b,int n) {
    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    //if there is more block on top of a 
    if(a1.num+1<set[a1.host].total) {
        for(i=a1.num+1;i<set[a1.host].total;i++) {
            set[set[a1.host].block[i]].block[0]=set[a1.host].block[i];
            set[set[a1.host].block[i]].total=1;
        }
        set[a1.host].total=a1.num; //cause we are going to take a out
    }else set[a1.host].total--;
    
    //now another search for b
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    
    set[b1.host].block[set[b1.host].total]=a;
    set[b1.host].total++;
}

void pile_onto(int a, int b, int n) {
    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    //removing the blocks on the top of b 
    if(b1.num+1<set[b1.host].total) {
        for(i=b1.num+1;i<set[b1.host].total;i++) {
            set[set[b1.host].block[i]].block[0]=set[b1.host].block[i];
            set[set[b1.host].block[i]].total=1;
        }
        set[b1.host].total=b1.num+1;
    }
    
    //now another search for b
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
        }
    }
    
    //copying the total pile
    for(i=a1.num;i<set[a1.host].total;i++) {
        set[b1.host].block[set[b1.host].total++]=set[a1.host].block[i];
    }
    set[a1.host].total=a1.num;
}
 
void pile_over(int a,int b, int n) {

    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
    
    if(a==b) return ;
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    if(a1.host==b1.host) return ;
    //copying the total pile
    for(i=a1.num;i<set[a1.host].total;i++) {
        set[b1.host].block[set[b1.host].total++]=set[a1.host].block[i];
    }
    set[a1.host].total=a1.num;
}

void print(int n) {
    int i,j;
    for(i=0;i<n;i++) {
        printf("%d:",i);
        for(j=0;j<set[i].total;j++) {
            printf(" %d",set[i].block[j]);
        }
    printf("\n");
    }
    
}

int main() {
    int n;
    char order[15];
    int a,b;
    char order2[15];
    char ch;
    
    while(scanf("%d",&n)==1) {
        init(n);
        while(scanf("%s",&order)==1) {
            if(!strcmp(order,"quit")) break;
            scanf("%d %s %d",&a,order2,&b);
            if(!strcmp(order,"move")) {
                if(!strcmp(order2,"onto")) move_onto(a,b,n);
                else move_over(a,b,n);
            }else if(!strcmp(order2,"onto")) pile_onto(a,b,n);
            else pile_over(a,b,n);
            //print(n); scanf("%c",&ch);
        }
    //printf("Final Print\n");
    print(n);
    }
return 0;
}
        
       
    
I dont want to bother you with my code... plz give me some good IO...
thanks in advance! :D
Last edited by smilitude on Thu Apr 20, 2006 7:21 am, edited 1 time in total.
fahim
#include <smile.h>

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

Code: Select all

void pile_over(int a,int b, int n) {

    int i,j;
    struct{
        int host;
        int num;
    }a1,b1;
   
    if(a==b) return ;
    for(i=0;i<n;i++) {
        for(j=0;j<set[i].total;j++) {
            if(set[i].block[j]==a) {
                a1.host=i;
                a1.num=j;
            }
            if(set[i].block[j]==b) {
                b1.host=i;
                b1.num=j;
            }
        }
    }
    [b]if(a1.host==b1.host) return ;[/b]    <----------------------- this
    //copying the total pile
    for(i=a1.num;i<set[a1.host].total;i++) {
        set[b1.host].block[set[b1.host].total++]=set[a1.host].block[i];
    }
    set[a1.host].total=a1.num;
}

if(a1.host==b1.host) return ;

Is this statement wrong ?? I am totally confused ...
fahim
#include <smile.h>

Post Reply

Return to “Volume 1 (100-199)”