120 - Stacks of Flapjacks

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

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Re: Please answer me this question about #120.

Post by teni_teni » Sat Feb 05, 2005 2:57 pm

The correct interpretation is,
2. The biggest at position 1, the second biggest at position 2, the third biggest at position 3 .... the smallest on the top.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sun Feb 06, 2005 5:36 am

Then Why I get WA? I think this process is quite simple and my answer is all right. Please view this post.
http://online-judge.uva.es/board/viewtopic.php?t=7380
I stay home. Don't call me out.

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni » Sun Feb 06, 2005 6:37 am

Test the following input:

Code: Select all

4 4 1
My output:

Code: Select all

4 4 1
1 0
And you'd better not use "\b" in printf to cancel the outputting of the last white space.
Because, when redirecting your output to a file, the file has '^H' (=0x08) characters which are the cause of WA.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sun Feb 06, 2005 5:49 pm

Thank you so much, teni_teni! Actually the "\b" is the error! I modified my code and get AC at once. And I have other three problems stuck by this error, they are now all solved. Thank you again.
I stay home. Don't call me out.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Apr 12, 2005 1:34 am

Sample I/O.
Let's hope it will be helpful for someone.

INPUT:

Code: Select all

1 2 3 4 5
5 4 3 2 1
5 1 2 3 4
10
4 4 1
4 4 5 4 4 1
4 4 5 4
99 7 99 0 7 99 0
2 4 4 4 2 4 
11 13 15 17 13 15 11
20 20 200 20 20 200 20 20

OUTPUT:

Code: Select all

1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0
10
0
4 4 1
1 0
4 4 5 4 4 1
4 1 0
4 4 5 4
2 1 0
99 7 99 0 7 99 0
1 3 2 1 3 6 4 1 5 0
2 4 4 4 2 4
3 2 0
11 13 15 17 13 15 11
4 1 2 3 4 5 0
20 20 200 20 20 200 20 20
3 1 4 2 0

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Wed Apr 13, 2005 10:59 am

Code: Select all

Given a stack of pancakes, you are to write a program that indicates how the stack can be sorted so that the largest pancake is on the bottom and the smallest pancake is on the top. The size of a pancake is given by the pancake's diameter. [b]All pancakes in a stack have different diameters.[/b]

This is given in the problem text (I especially mean the BOLD part). My solution is based on this! Could I be getting WA over this, or did your tests simply left this out??
Understanding a problem in a natural way will lead to a natural solution

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Apr 13, 2005 4:42 pm

I am pretty sure that in the Judge Input there are test
cases in which there are more than 1 pancakes with
equal diameters.

My first solution was also based on this ( I just
thought all pancakes have different diameters ).
Then I read somewhere that I should try the input

Code: Select all

4 4 1
So I started to adjust my code so that it works for
such cases too ( for cases in which you have >=2 pancakes
with same diameter ). And after these adjustments and changes
( which took me quite some time ) I managed to get ACC.

That is why I decided to post the
sample I/O which you see above.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare » Thu Apr 14, 2005 10:42 am

hi Sedefcho

is your output right??
i have just solved this problem
But my output is not the same as yours,when the input is ....99 7 99 0 7 99 0


its strange ......

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Thu Apr 14, 2005 10:48 am

Hi Sunnycare,

It's not so strange.

Maybe your output represents
a different solution.

It's obvious you have more than 1 solution ( always ).
I mean you have more than 1 sequence of moves ( flips )
which leads you to the final configuration.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare » Fri Apr 15, 2005 1:52 am

you're right.......
:lol:

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Mon Jul 04, 2005 6:19 pm

It isn't necessity to use deque, use just <stack> it's better to implement. Cause we put 'pancakes' on the top of stack and then put them off, so we need only some_stack.push(value), some_stack.top(),and some_stack.pop() and all's clear:)

Regards
keep it real!

devious
New poster
Posts: 13
Joined: Wed Feb 22, 2006 1:26 am

Post by devious » Thu Feb 23, 2006 3:50 pm

Hey, I think I am misinterpretting the problem with how I am suppose to output flips. But, can someone give me some test samples or something?

Code: Select all

import java.io.*;
import java.util.*;

class Main
{
	public static void main(String[] args)
	{
		String s,answer;
		StringTokenizer st;
		int flips,f;
		int[] flapjacks,remains;
		
		while((s = Main.readLn(24000).trim()) != null)
		{
			flips = 0;
			st = new StringTokenizer(s);
			flapjacks = new int[st.countTokens()];
			remains = new int[st.countTokens()];
			
			for(int i = 0; i < flapjacks.length; i++)
			{
				f = Integer.parseInt(st.nextToken());
				flapjacks[i] = f;
				remains[i] = f;
			}	
			System.out.println(s);
			flapjacks = Main.sort(flapjacks,remains,flips);
	//		for(int i = 0; i < flapjacks.length; i++)
	//			System.out.print(flapjacks[i] + " ");
		}
		
		
	}
	
	static  int[] sort(int[] a,int[] r,int flips)
	{
		int largest = 0, li=0,ai=0,temp, l;
		boolean sorted = true;
		
		for(int i = 0; i < a.length-1; i++)
			if(a[i]>a[i+1])
				sorted = false;
		if(!sorted)
		{
			//find largest
			for(int i = 0; i < r.length; i++) 
			{
				if(r[i] > largest) 
		 		{
		 			largest = r[i]; 
		 			li = i;    
		 		}
			}
						
			if(largest == 0) 
			{
				System.out.print("0\n"); 
				return a; 
			}
				
			for(int i = 0; i < a.length; i++)  
			{
				if(a[i] == largest)   
				{
					ai = i;  
					break;
				}	
			}
			
			r[li] = 0; //remove index
			
			//swap largest to top
		//	System.out.println("Setting a[0] to "+ a[ai]);
		//	System.out.println("Setting a["+ai+"] to " + a[0]);
			temp = a[0]; a[0] = a[ai]; a[ai] = temp; 
					
			//flip array
			l = a.length-1-flips;
			for(int i = 0; i < (l+1)/2; i++)
			{
		//		System.out.println("Setting a["+i+"] to " + a[(l-i)]);
		//		System.out.println("Setting a["+(l-i)+"] to " + a[i]);
				temp = a[i]; a[i] = a[(l-i)]; a[(l-i)] = temp;
			}
			flips++;
			
			System.out.print(flips + " ");
			
			a = Main.sort(a,r,flips);
		}
		else
			System.out.print("0\n");
		
		return a;
			
		
		
	}
   
   	static String readLn (int maxLg) 
	{
    	byte lin[] = new byte [maxLg];
    	int lg = 0, car = -1;
    	
    	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);
    	return (new String (lin, 0, lg));
   }			

}

devious
New poster
Posts: 13
Joined: Wed Feb 22, 2006 1:26 am

120 Flapjacks Misinterpreting output?

Post by devious » Fri Feb 24, 2006 4:17 am

Hey, I think I am misinterpretting the problem with how I am suppose to output flips. But, can someone give me some test samples or something?

Code: Select all

import java.io.*;
import java.util.*;

class Main
{
   public static void main(String[] args)
   {
      String s,answer;
      StringTokenizer st;
      int flips,f;
      int[] flapjacks,remains;
      
      while((s = Main.readLn(24000).trim()) != null)
      {
         flips = 0;
         st = new StringTokenizer(s);
         flapjacks = new int[st.countTokens()];
         remains = new int[st.countTokens()];
         
         for(int i = 0; i < flapjacks.length; i++)
         {
            f = Integer.parseInt(st.nextToken());
            flapjacks[i] = f;
            remains[i] = f;
         }   
         System.out.println(s);
         flapjacks = Main.sort(flapjacks,remains,flips);
   //      for(int i = 0; i < flapjacks.length; i++)
   //         System.out.print(flapjacks[i] + " ");
      }
      
      
   }
   
   static  int[] sort(int[] a,int[] r,int flips)
   {
      int largest = 0, li=0,ai=0,temp, l;
      boolean sorted = true;
      
      for(int i = 0; i < a.length-1; i++)
         if(a[i]>a[i+1])
            sorted = false;
      if(!sorted)
      {
         //find largest
         for(int i = 0; i < r.length; i++)
         {
            if(r[i] > largest)
             {
                largest = r[i];
                li = i;   
             }
         }
                  
         if(largest == 0)
         {
            System.out.print("0\n");
            return a;
         }
            
         for(int i = 0; i < a.length; i++) 
         {
            if(a[i] == largest)   
            {
               ai = i; 
               break;
            }   
         }
         
         r[li] = 0; //remove index
         
         //swap largest to top
      //   System.out.println("Setting a[0] to "+ a[ai]);
      //   System.out.println("Setting a["+ai+"] to " + a[0]);
         temp = a[0]; a[0] = a[ai]; a[ai] = temp;
               
         //flip array
         l = a.length-1-flips;
         for(int i = 0; i < (l+1)/2; i++)
         {
      //      System.out.println("Setting a["+i+"] to " + a[(l-i)]);
      //      System.out.println("Setting a["+(l-i)+"] to " + a[i]);
            temp = a[i]; a[i] = a[(l-i)]; a[(l-i)] = temp;
         }
         flips++;
         
         System.out.print(flips + " ");
         
         a = Main.sort(a,r,flips);
      }
      else
         System.out.print("0\n");
      
      return a;
         
      
      
   }
   
      static String readLn (int maxLg)
   {
       byte lin[] = new byte [maxLg];
       int lg = 0, car = -1;
       
       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);
       return (new String (lin, 0, lg));
   }         

}

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

no miss.

Post by sds1100 » Fri Mar 03, 2006 8:32 am

sorry
i can't your program miss

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

Post by sds1100 » Fri Mar 03, 2006 8:33 am

sorry
i can't your program miss

Post Reply

Return to “Volume 1 (100-199)”