11111 - Generalized Matrioshkas
Moderator: Board moderators
11111 - Generalized Matrioshkas
Everytime that i read the problem i get more confused, can somebody explain it to me?
Thanks
Thanks
____________________________
"Free software for a free society"
"Free software for a free society"
-
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
as the problem statement is too long,i haven't read the problem statement Completely during the Contest,
consider you have some boxes that some of them are nested in some other boxes , each box should begin with negative number and end with the absolute value of that negative number , the absolute value shows the size of box , and the sum of size of inside boxes should be less than the outside boxes , you are given sequence of the numbers , you should check whether it violates the above rules or not, that's all
Hope it helps
consider you have some boxes that some of them are nested in some other boxes , each box should begin with negative number and end with the absolute value of that negative number , the absolute value shows the size of box , and the sum of size of inside boxes should be less than the outside boxes , you are given sequence of the numbers , you should check whether it violates the above rules or not, that's all
Hope it helps
In being unlucky I have the record.
-
- New poster
- Posts: 17
- Joined: Wed Mar 01, 2006 8:34 pm
- Location: 2nd floor
To clear more , consider the following input:
this is a invalid input; -8 8 -5 5 is surrounded by -10 10 and 8+5=13 sized box cannot be allocated in a 10 sized box. but above input can be validated in this way-
Now it is possible. because, if the 5 sized box is placed in 8 sized box then it allocated in the 10 sized box easily. now see the picture below. fig 1 is for input 1 and fig 2 for input 2.
![Image](http://i12.tinypic.com/2f0dbi1.jpg)
But i got wa in this problem(?). i used stack of stl and a lot of checks.
i also checked on with this input:
my output is:
I inputed char wise and escaped the blank lines of the input.
Kindly any body helps me by giving more input.
Code: Select all
-10 -8 8 -5 5 10
Code: Select all
-10 -8 -5 5 8 10
![Image](http://i12.tinypic.com/2f0dbi1.jpg)
But i got wa in this problem(?). i used stack of stl and a lot of checks.
i also checked on with this input:
Code: Select all
-9 -7 -2 2 -3 -2 -1 1 2 3 7 9
-9 -7 -2 2 -3 -1 -2 2 1 3 7 9
-9 -7 -2 2 -3 -1 -2 3 2 1 7 9
-100 -50 -6 6 50 100
-100 -50 -6 6 45 100
-10 -5 -2 2 5 -4 -3 3 4 10
-9 -5 -2 2 5 -4 -3 3 4 9
-10 -5 -3 3 -1 1 5 -4 4 10
10
-10 10
-10
Code: Select all
:-) Matrioshka!
:-( Try again.
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
Kindly any body helps me by giving more input.
[ Common thing of every man is that, everyone thinks that he is uncommon ]
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
I also got WA many times on this problem
It needed many details to solve the problem, and my code fell on these
The correct answers are easy to know
Hope it helps
It needed many details to solve the problem, and my code fell on these
Code: Select all
-10 -5 3
-10 -5 -3 3 5 10 11
Hope it helps
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
I dont solve this problem, yet. But i think for your input, output should be:
Code: Select all
:-( Try again.
:-( Try again.
-
- New poster
- Posts: 17
- Joined: Wed Mar 01, 2006 8:34 pm
- Location: 2nd floor
Wei-Ming Chen, i can understand the problem of your code.Wei-Ming Chen wrote: and my code fell on theseCode: Select all
-10 -5 3 -10 -5 -3 3 5 10 11
you think the line of input as stack. when a positive number(let x) is inputed, then check that-
if(stack_size!=0 && top_of_stack == x ) pop the top num;
else print "try again".
My program generated correct output for your input.
please any one post more input.
[ Common thing of every man is that, everyone thinks that he is uncommon ]
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
input:
Output:
Code: Select all
-9 -7 7 -2 2 9
-9 -2 2 -1 1 -6 6 9
-9 -2 2 -1 -5 5 1 9
-9 -2 2 -1 1 -2 5 9
-9 -2 2 -1 1 -1 1 9
Code: Select all
:-( Try again.
:-( Try again.
:-( Try again.
:-( Try again.
:-) Matrioshka!
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
Code: Select all
-200 -180 -50 50 -60 60 -69 -50 -40 40 50 -11 11 69 180 200
-3 -1 1 -1 1 3
-3 -1 -1 1 1 3
-50 -20 20 -15 15
-8 7 -7 8
-60 -55 -53 -6 6 -12 12 -40 40 53 55 60
Code: Select all
:-) Matrioshka!
:-) Matrioshka!
:-( Try again.
:-( Try again.
:-( Try again.
:-( Try again.
-
- New poster
- Posts: 12
- Joined: Tue Sep 12, 2006 6:54 pm
Something is wrong about your code. My O(n) solution using recursion runs in time, and using stack is always faster than recursion. Probably your code has infinite loop.StanleY Yelnats wrote:my o(n) solution using stacks exceeds the time limit,
is there any faster aproach or there is something wrong about my code?
-
- New poster
- Posts: 17
- Joined: Wed Mar 01, 2006 8:34 pm
- Location: 2nd floor
-
- New poster
- Posts: 12
- Joined: Tue Sep 12, 2006 6:54 pm
what's the correct output for this :
Code: Select all
-9 -1 1 9 -9 9
-
- New poster
- Posts: 17
- Joined: Wed Mar 01, 2006 8:34 pm
- Location: 2nd floor
Obviously
(from my ac code)
Code: Select all
:-) Matrioshka!
[ Common thing of every man is that, everyone thinks that he is uncommon ]
Hello..~
I don't clearly understand this problem..
Please tell me what the correct output is for this input..
Thanks.. ![:D](./images/smilies/icon_biggrin.gif)
I don't clearly understand this problem..
Please tell me what the correct output is for this input..
Code: Select all
-10 -8 -5 5 8 10
![:D](./images/smilies/icon_biggrin.gif)
My ac code outputs
Code: Select all
:-) Matrioshka!