ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1725. Sold Out!

Solution
Posted by Roland 17 Oct 2009 21:51
Very easy:)

*first if k>n/2 make it smaller n/2: k=n-k+1

(......[Vasya].......[n-1][n]
if [n-1] and [n] sit,then all people between
[Vasya] and [n-1] will stumble at Vasya.
And this will be the maximal answer )

*special case: n=2 => answer is 0
Re: Solution
Posted by muhammad 29 Nov 2009 16:59
i dnt understand ur soln. why it be so??
the prog sttmnt says visitor chooses left || right end based on minimal no. of people s/he need to stumble upon.
so let be test: 10 3
ur soln gives: 5
let last 2 and 1st 2 beseated. now why rest people should choose left end. prog sttmnt says it shd be right end. because
only 2 need to be stumbled upon if right else 3.
bt ur soln gives ac.
so i thnk the prog sttmnt is all wrong || i am weak in english || the author is!!!

Edited by author 29.11.2009 17:00
Re: Solution
Posted by alexey saybel 23 Jan 2010 14:17
Roland is right

example:
6
(1 Man, 2 Man, 3 empty, 4 empty, 5 empty, 6 You);
Re: Solution
Posted by Andriy Kozachuk(VNTU) 9 Apr 2010 16:09
Can you explain how do you get answer 3 for test 6,1?
My solution:
Veeeee
Veeee1
V2eee1
V2ee31
V24e31
V24531,
Where V - Vasya, e - empty place, 1,2,3... - visitors. Numbers 2 and 4 will stumble Vasyas feet, so my answer is 2.
Re: Solution
Posted by dAFTc0d3r [Yaroslavl SU] 11 Apr 2010 11:37
Veeeee
Veeee1
Veee21
Vee321
Ve4321
V54321
The worst case.
Re: Solution
Posted by Andriy Kozachuk(VNTU) 12 Apr 2010 16:51
Thank you
Re: Solution
Posted by Nikita Doykov 8 Dec 2010 14:43
I don`t understand why it works.
Example:
10 4

###[Vasya]######

At worst viewers with the numbers 1, 2 will come first:
[1][2]#[Vasya]######
and viewer 3 stumbles over Vasya`s feets.

Next come viewers with the numbers 9 and 10:
[1][2][3][Vasya]####[9][10]
and viewers 5, 6, 7, 8 stumble over feets.

So the answer is 5, but your program (AC program!) gives 4...

Edited by author 08.12.2010 14:45
Re: Solution
Posted by Fastholf 14 Dec 2010 09:33
Nikita Doykov wrote 8 December 2010 14:43
Next come viewers with the numbers 9 and 10:
[1][2][3][Vasya]####[9][10]
and viewers 5, 6, 7, 8 stumble over feets.

You should consider only those viewers who stumble Vasya's feet.

Write order for this test.

###[Vasya]######
###[Vasya]#####[1]
###[Vasya]####[2][1]
###[Vasya]###[3!][2][1]
###[Vasya]##[4!][3!][2][1]
###[Vasya]#[5!][4!][3!][2][1]
###[Vasya][6!][5!][4!][3!][2][1]

Edited by author 14.12.2010 09:37
No subject
Posted by PrankMaN 30 Aug 2011 05:36

Edited by author 30.08.2011 05:38
Re: Solution
Posted by Pegasus 21 Oct 2012 14:41
I think is 2    (1 man, 2 man ,3 empty, 4 man,5 man, 6 you)  ,the 3man may from left
Re: Solution
Posted by Nodir NAZAROV Komiljonovich 22 Jan 2014 22:05
My solution is shorter than that, 11 lines of code and best performance (0.015s, 112KB): http://acm.timus.ru/status.aspx?space=1&num=1725&author=126126

Instead of that, you can take min of (k-1) and (n-k)
Re: Solution
Posted by bostanmatei 11 Sep 2016 19:41

Edited by author 11.09.2016 19:43

Edited by author 11.09.2016 19:43
Re: Solution
Posted by Znol 23 Jan 2020 16:02
Why 3? i think it have to be 4. Like Veeee1 - 0, Veee21 - 1, Vee321 - 2, Ve4321 - 3, V54321 - 4. The first case has the same problem tho
Nvm, i get it. (the last sentence in first paragraph)

Edited by author 23.01.2020 16:05