OJ Board

I am truly stumped on this one

Any hints as to a simple way that this one can be done? Obviously trying every possibility isn't the answer...

hmm... I hope this isn't giving it away...

Look at how many turtles are properly in their increasing (not necessary consecutive) order. Then the solution should be obvious.

Good luck.

Thanks, yeah I figured that out a couple of days ago and finally got a AC on it.

farsight wrote:hmm... I hope this isn't giving it away...
Look at how many turtles are properly in their increasing (not necessary consecutive) order. Then the solution should be obvious.

I also thought it was obvious, but I am unable to formulate an algorithm for the set

• 7
  Yertle
  Oscar
  Baron
  Lord
  King
  White
  Kong
  Oscar
  Baron
  Lord
  Yertle
  King
  Kong
  White

Which should result in

• Kong
  King
  Yertle
  Lord
  Baron
  Oscar

Any hints? I have tried looking at increasing order and consecutive order, but I am unable to stop the algorithm from sorting 'white' (it should't)

Appreciate an answer

Just got ACC.

Hint: NO sorting is required

dopey: what do you mean by "unable to stop the algorithm from sorting 'white'"? Could you explain it a bit, plz? We really want to help...

This problem is pissing me off..

here are my questions:

1) Why is there "No Sorting"? Of course there should be: if a turtle is not in increasing order, throw it to the top.. do that until you have transformed it to the required stack.

2) What if there is only one turtle in the stack? what are you supposed to print?

3) What if the given stack is already sorted just like the required stack?

If somebody thinks that I am way off in my algorithm, please let me know..

THanks

>1) Why is there "No Sorting"? Of course there should be: if a turtle >is not in increasing order, throw it to the top.. do that until you >have transformed it to the required stack.
You actually do not have to do any manipulation of any sort

>2) What if there is only one turtle in the stack? what are you >supposed to print?
If only one, both stacks are alike, and noone moves...

>3) What if the given stack is already sorted just like the required >stack?
Then noone moves and nothing is printed out

>If somebody thinks that I am way off in my algorithm, please let me >know..
You haven't figured it out just yet :|

HINT: Count the number of shells that are misplaced
HINT2: Know that no sort of ANY kind need to be done. No manipulation
what so ever. Just counting!

Hello, I am having some problems with this problem. It seems to be working but i keep on getting wrong answer... I have an input file which i will include below and an output file and if anyone could give me a hint to this problem or any other possible cases which i haven't thought of, i would love you... lol

in.txt
--------------------------------------------------
4
3
Yertle
Duke of Earl
Sir Lancelot
Duke of Earl
Yertle
Sir Lancelot
9
Yertle
Duke of Earl
Sir Lancelot
Elizabeth Windsor
Michael Eisner
Richard M. Nixon
Mr. Rogers
Ford Perfect
Mack
Yertle
Richard M. Nixon
Sir Lancelot
Duke of Earl
Elizabeth Windsor
Michael Eisner
Mr. Rogers
Ford Perfect
Mack
7
Yertle
Oscar
Baron
Lord
King
White
Kong
Oscar
Baron
Lord
Yertle
King
Kong
White
3
Yertle
Duke of Earl
Sir Lancelot
Yertle
Duke of Earl
Sir Lancelot
--------------------------------------------------

out.txt
--------------------------------------------------
Duke of Earl

Sir Lancelot
Richard M. Nixon
Yertle

Kong
King
Yertle
Lord
Baron
Oscar


--------------------------------------------------
[/cpp]

Your output is correct, but if you don't tell us your algorithm... it's rather hard to help you. IMO this problem doesn't have tricky inputs.

Sorry, I pretty much saw this pattern... I have 2 arrays Sorted and unsorted. Pretty much i will make a variable called c, which the first time the value is set for each case is equal to n-1 (the amount of elements in array). I have a loop that goes from the bottom to the top of unsorted. I compare it with the value of sorted[c], to see if it is equal and if it is equal, than i know i don't need to move that element so i just simply erase that entry on the unsorted list and i subtract 1 from the c value to move to the next value. After i get though this loop, I then know what elements need to be moved so i go though and output the ones that need to be moved by how they appear in the sorted list (last to first).

Here is my chunk of code that i have doing this part of my program.

Code
----------------
// find the order
celement = n-1;
for (y=n-1; y>=0; y--) {
if (strcmp(nonsort[y], sorted[celement]) == 0) {
nonsort[y][0] = '\0';
celement--;
}
}
c=0;
for (y=n-1; y>=0; y--) {
for (z=0; z<n; z++) {
if (strcmp(nonsort[z], sorted[y]) == 0) {
cout << nonsort[z] << endl;
c++;
}
}
}
----------------

Hi...
Send me your code via PM. I added a few lines of input to your chunk and it got AC. Also you may want to edit your previous post to erase the code.

Hey, for anyone else that may be having problems, the resolution to my problem was that their compiler were having problems with using cin.getline. After switching all my getlines to gets(), it worked great.

I too am having troubles getting this problem accepted. My program seems to work for any input I can concieve of. It prints a blank line only between test cases, though I have also tried making it print a blank line at the end of any test case even if it is not followed by another case. I am using java (required in order to get credit for my class), and have used only System.in.read() to obtain data, as I am under the impression any more advanced methods cause the judge to freak out. Any theories on little things that might be bothering the judge, or some really bizarre test case that I might not have considered? My algorithm is admittedly inefficient, but that really shouldn't cause a problem. I can provide more information or code if that would help. Thanks in advance for any help.

Slowly going mad,
Craig

Just to clarify a little about the output format I am currently trying:
If the list is already sorted, it will print a single blank line.
It also prints a blank line after the end of the last test case (although I have tried it without this)
There is, of course, a blank line separating each test case.
There is no blank line before the first test case.

[/java]

Hi, I'm having troubles with this one, I