ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1725. Аншлаг, аншлаг!

Solution
Послано Roland 17 окт 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
Послано muhammad 29 ноя 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
Послано alexey saybel 23 янв 2010 14:17
Roland is right

example:
6
(1 Man, 2 Man, 3 empty, 4 empty, 5 empty, 6 You);
Re: Solution
Послано Andriy Kozachuk(VNTU) 9 апр 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
Послано dAFTc0d3r [Yaroslavl SU] 11 апр 2010 11:37
Veeeee
Veeee1
Veee21
Vee321
Ve4321
V54321
The worst case.
Re: Solution
Послано Andriy Kozachuk(VNTU) 12 апр 2010 16:51
Thank you
Re: Solution
Послано Nikita Doykov 8 дек 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
Послано Fastholf 14 дек 2010 09:33
Nikita Doykov писал(a) 8 декабря 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
Послано PrankMaN 30 авг 2011 05:36

Edited by author 30.08.2011 05:38
Re: Solution
Послано Pegasus 21 окт 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
Послано Nodir NAZAROV Komiljonovich 22 янв 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
Послано bostanmatei 11 сен 2016 19:41

Edited by author 11.09.2016 19:43

Edited by author 11.09.2016 19:43
Re: Solution
Послано Znol 23 янв 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