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 *then the answer is (n-k-2)
(......[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 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 Roland is right example: 6 (1 Man, 2 Man, 3 empty, 4 empty, 5 empty, 6 You); answer - 3 Re: Solution 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 Veeeee Veeee1 Veee21 Vee321 Ve4321 V54321 The worst case. Answer - 3. Re: Solution 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 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
*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
*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* |