120 - Stacks of Flapjacks

[teni_teni]

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.

[ImLazy]

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

[teni_teni]

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.

[ImLazy]

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.

[Sedefcho]

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]

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

[Sedefcho]

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]

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 ......

[Sedefcho]

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]

you're right.......

[jaracz]

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

[devious]

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]

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]

sorry
i can't your program miss

[sds1100]

sorry
i can't your program miss