10152 - ShellSort
Moderator: Board moderators
10152 - ShellSort
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...
Any hints as to a simple way that this one can be done? Obviously trying every possibility isn't the answer...
Not so obvious :|
I also thought it was obvious, but I am unable to formulate an algorithm for the setfarsight 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.
- 7
Yertle
Oscar
Baron
Lord
King
White
Kong
Oscar
Baron
Lord
Yertle
King
Kong
White
- Kong
King
Yertle
Lord
Baron
Oscar
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...
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...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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
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
I finally managed to solve it myself
>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!
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!
10152 - Shell Sort Not working :(
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]
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]
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
Sorry...
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++;
}
}
}
----------------
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++;
}
}
}
----------------
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
resolved!!!
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.
-
- New poster
- Posts: 2
- Joined: Thu Oct 23, 2003 11:33 pm
10152 - Shellsort
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
Slowly going mad,
Craig
-
- New poster
- Posts: 2
- Joined: Thu Oct 23, 2003 11:33 pm
Clarification
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]
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]
shellsort not working
Hi, I'm having troubles with this one, I