понедельник, 24 октября 2016 г.

Разбор задач 1 личного тура

Разбор задач приводит А.Ю. Кораблев в своем блоге, посвященном программированию sportprog.ru  Перейдите по ссылке.

Отмечу, что в ряде случаев Time limit возникал не из-за неправильного решения. Иногда участники забывали убрать из текста программы задержку, что-нибудь вреде Readln(n)

 Так как тексты задач в разборе не приводятся, помещаю их здесь.

A. Лифты
Лифты – очень сложные устройства. Лифты бывают пассажирские и грузовые, скоростные и не очень, дорогие и подешевле. Разобраться в том, какой лифт перед тобой не всегда просто, но мы постараемся.
Пассажирские лифты предназначены для перевозки людей и небольшого груза. Обычно грузоподъёмность таких лифтов не превосходит 400 килограмм. Грузовые лифты напротив ориентированы на перевозку больших и габаритных предметов, поэтому производители делают их грузоподъёмность больше 400 килограмм.
Скорость обычных, так называемых медленных лифтов меньше 4 м/с, все остальные обычно относят к скоростным. Кстати, в некоторых дубайских небоскрёбах скорости лифтов достигают 18 м/с!
Формат ввода:
В первой строке ввода содержится три целых числа – описание здания: N – количество этажей, H – высота каждого этажа в метрах, M – количество лифтов (числа не превосходят 100).
В последующих M строках содержатся описания лифтов. Каждое описание состоит из двух вещественных чисел: T – время в секундах за которое лифт может доехать от первого этажа до последнего, W – грузоподъёмность лифта в килограммах.
Формат вывода:
В M строках выведите описание каждого лифта, состоящее из двух слов по критериям грузоподъёмности и скорости. Пассажирские лифты обозначаются словом PASS, грузовые – CARGO, скоростные – FAST, медленные – SLOW.
Input
Output
10 3 2
50.2 345
3.4 1064.4
PASS SLOW
CARGO FAST


B. Нужный этаж

В очень больших зданиях обычно есть очень много лифтов. Системы управления лифтами настраивают профессионалы с учётом потребностей посетителя каждого конкретного здания. Например, скоростные лифты могут не останавливаться на некоторых этажах, чтобы сэкономить время, а медленные лифты часто не ездят выше определённого количества этажей.
Одному сотруднику одного очень большого офисного здания очень везло. Он всегда перемещался по этажам здания максимально быстро. Так уж получалось, что когда сотрудник приезжал на этаж, другие лифты, которые останавливались на этом этаже уже ждали его, поэтому ему удавалось мгновенно пересаживаться с одного лифта на другой. Так могло происходить многократно и, надо сказать, противоречило законам физики!
Формат ввода:
В первой строке ввода содержится три целых числа – описание здания: N – количество этажей, M – количество лифтов (числа не превосходят 100).
В последующих M строках содержатся описания лифтов. Каждое описание состоит из целых чисел. Первое число – время в секундах, за которое лифт проезжает один этаж. Второе число – количество этажей на которых останавливается лифт. Остальные числа – номера этажей, на которых останавливается конкретный лифт.
В последней строке ввода содержится два целых числа. Первое – номер этажа с которого сотрудник намеревается уехать. Второе – номер этажа, на который хочет попасть сотрудник.
Формат вывода:
В единственной строке выведите время в секундах, которое понадобится сотруднику, чтобы преодолеть на лифтах путь от одного этажа до другого. Если сотрудник никогда не доберётся до нужного этажа, выведите -1.
Input
Output
4 3
15 4 1 2 3 4
3 3 1 3 4
4 3 2 3 4
1 2
10

C. Дорога к начальнику


Одного офисного сотрудника одного большого офисного здания вызвал начальник. Между этажом, на котором находится сотрудник и этажом, где его ждёт начальник ходит лифт. Между этажами начальника и подчинённого находится L этажей. Лифт может ехать только так, чтобы любой отрезок пути длиной K этажей проезжать ровно за H секунд. Через какое минимальное и максимальное время сотрудник сможет доехать на лифте до начальника.
Формат ввода:
В единственной строке через пробел записаны целые числа L, K и H (1<=K<=L<=1000, 1<=H<=1000).
Формат вывода:
Выведите через пробел минимальное и максимальное время за которое подчинённый сможет доехать на лифте до начальника с точностью не менее 10^-5.
Input
Output
30 10 1
3.00000000 3.00000000

D. Быстрый спуск


Один сотрудник оказался на верхнем (n-м) этаже небоскрёба и хочет спуститься на первый. На табло он видит, что лифт в данный момент едет вниз до первого этажа и находится точно на кровне k-го этажа. Сотрудник смекнул, что, возможно, будет быстрее спуститься на несколько этажей вниз и вызвать лифт оттуда. Помогите сотруднику определить до какого этажа ему надо спуститься пешком, чтобы как можно быстрее оказаться на первом этаже.
Лифт проезжает этаж за v секунд, а сотрудник пробегает его за u секунд. Когда лифт спустится на первый этаж, он должен будет простоять там 15 секунд, после чего сможет ехать вверх. Если сотрудник вызовет лифт не сразу, то можно считать, что его никто не «угонит». На посадку в лифт сотрудник потратит 5 секунд. Всеми остальными временными задержками можно пренебречь.
Формат ввода:
В единственной строке задано 4 число – n, k, u и v (1
Формат вывода:
Выведите единственное число – этаж, до которого нужно спуститься сотруднику. Если есть несколько равноценных вариантов, то выведите такой, при котором сотрудник меньше пройдёт пешком.
Input
Output
50 49 4.8 0.2
45

E. Половина лифтов


Помните старые лифты, в которых нужно было договариваться на какой этаж лифт поедет сначала, а на какой потом? В одном небоскрёбе были как раз такие – лифты ехали сначала на тот этаж, который нажимали первым.
Однажды в этом здании проходила большая и представительная конференция. Организаторы подготовились на славу. Они решили выделить людей, которые должны были встречать лифты с участниками. Чтобы оптимизировать расходы на персонал организаторы решили, что будет достаточно, если количество встречающих будет рассчитано таким образом, что их количество не будет больше, чем половина лифтов, которые находятся в здании.
С утра к зданию начали подъезжать автобусы с участниками конференции. Они стали заходить в лифты… Также в лифтах оказались люди, которые ехали по другим этажам. Как же решить, на какой этаж лифт поедет сначала, а на какой потом? Решение простое – нужно проголосовать и большинством голосов решить.
Формат ввода:
В первой строке записано нечётное число K – количество лифтов в здании (0
Формат вывода:
Выведите минимальное количество участников конференции, которое должно находится во всех лифтах, чтобы организаторам не хватило встречающих.
Input
Output
3
5 7 5
6

F. Задачка для лифтёров


На секунду представим, что нам нужно построить лифт на Луне. Чтобы посетителям лифта было комфортно, в шахту лифта нужно закачать воздух. Возникает вопрос – сколько воздуха нужно, чтобы заполнить шахту лифта целиком.
Один космический лифтёр придумал интересный способ. Он залезал в шахту лифта и измерял в метрах любое из наибольших расстояний между стенками шахты в любом горизонтальном сечении шахты. Для простоты обозначим это расстояние за А. Потом лифтёр мерял высоту шахты лифта, обозначим её за B.
После этого он считал загадочное число лифтёра путём перемножения числа А на самого себя и на высоту шахты лифта.
Но самая настоящая магия происходила потом! Он умножал загадочное число лифтёра на ещё более загадочное число инопланетного происхождения равное
Так он и получал объём воздуха в кубометрах, который нужно было закачать в шахту.
Формат ввода:
В первой строке ввода содержится два вещественных числа. Первое – число А, второе – объём воздуха в литрах, который закачивали в шахту.
Формат вывода:
Выведите число В – высоту шахты лифта.
Input
Output
2 100000
31.830988618379067













воскресенье, 23 октября 2016 г.

Фотографии с личного тура

45 студентов и школьников приняли участие в личном туре. Контест получился очень нервный, победили сильнейшие, кто бы сомневался. Задачи подготовил Кораблев А.Ю. в свойственной ему манере. На вид простые, но все с подвохом. Полный фотоальбом здесь.

На этой фотографии победитель личного тура Шморгунов Александр, ученик 10 класса гимназии им. А.С.Пушкина, запечатлен с красивой блондинкой из технологического лицея, а я ее не знаю.
Шморгунов Александр на втором плане
Виноградову Олегу, ученику 11 класса ФМЛИ, не повезло с компьютером.

Третье место у Александрова Максима, ученика 9 класса ФМЛИ. Я его пока не знаю. Вероятно, он на этом фото на втором плане.

Из студентов 1 курса ИТНИТ лучшим был Лапшин Валерий, 115 группа. Тоже  на втором плане.

И хотя Валерий решил только одну задачу, он ее решил с первой попытки, как и победитель этого тура.




суббота, 22 октября 2016 г.

Результаты личного тура "Первокурсник"

Личный тур начался своевременно, но его прохождение сопровождалось неполадками с проверяющей системой. В результате тур был продлен почти на час. После завершения тура жюри перепроверило все решения с пометкой Time limit и 7 участников переместились вверх в турнирной таблице. Перед вами протокол личного тура открытого чемпионата СыктГУ по программированию:

R
Участник
A
B
C
D
E
F
+
T
Лифты
Нужный этаж
Дорога к нача...
Быстрый спуск
Половина лифтов
Задачка для ...
1
Шморгунов Александр Алексеевич
+
00:11
+
00:45
+3
03:29
+
01:46
+
02:15
+2
02:16
6
742
2
Виноградов Олег Дмитриевич
+1
00:14
-3
03:47
+3
00:49
+2
00:53
+1
02:21
+2
01:10
5
507
3
Александров Максим Андреевич
+5
03:27

 
+
03:03
+9
03:47
+5
03:37
+
02:14
5
1348
4
Рябинин Андрей Олегович
+1
00:14
-3
02:48
+
00:49
-3
02:35
-3
03:23
+
00:23
3
106
5
Зизганова Елена Сергеевна
+
00:20

 
+
02:31
-2
02:53
-1
02:44
+
00:46
3
217
6
Вологдин Максим Дмитриевич
+4
00:59

 
+
01:14

 

 
+1
01:08
3
301
7
Надуткин Фёдор
+
00:40

 
-2
03:29
+
02:24

 
+
02:29
3
333
8
Осипов Михаил Леонидович
+3
00:38

 
+3
02:36
-1
01:50
-1
00:55
+
00:35
3
349
9
Попов Антон Дмитриевич
+
00:16

 
+8
03:42
-6
03:47
-1
01:45
+
00:47
3
445
10
Тропин Иван
+1
01:08

 

 
-1
03:44
+
02:39
+1
03:47
3
494
11
Зиновьев Илья Сергеевич
+
00:17
-2
01:13
-2
02:47

 

 
+
00:43
2
60
12
Рогов Юрий Павлович
+
00:19

 
-2
01:05
-1
01:51

 
+
00:42
2
61
13
Рыбин Иван Сергеевич
+1
00:19

 
-1
00:30

 

 
+
00:44
2
83
14
Десятников Григорий Евгеньевич
+
00:25

 

 
-1
01:51

 
+1
00:43
2
88
15
Торкунов Евгений Игоревич
+1
00:42

 
-2
01:47
-3
02:41

 
+
00:39
2
101
16
Терентьев Даниил Васильевич
+
00:32

 
-3
02:38
-1
02:27

 
+1
00:59
2
111
17
Смирнов Владислав Дмитриевич
+
00:21

 

 
-1
02:45

 
+
01:47
2
128
18
Матвеев Константин Дмитриевич
+3
01:11

 
+1
03:45
-1
02:22

 
-1
02:21
2
376
19
Колегов Андрей Александрович
+
00:15

 

 

 
-2
00:55
-1
00:53
1
15
20
Носов Роман Александрович
+
00:23

 
-1
02:21
-1
01:47

 
-3
01:57
1
23
21
Чупров Максим Дмитриевич
+
00:27

 
-2
02:28
-3
03:48

 

 
1
27
22
Лапшин Валерий Олегович
+
00:28

 

 

 

 

 
1
28
23
Гришин Дмитрий Алексеевич
+
00:33

 
-2
02:29
-4
03:43

 

 
1
33
24
Вереитин Вячеслав Анатольевич
+1
00:21

 

 
-1
01:48

 
-2
01:05
1
41
24
Рябий Максим Петрович
+1
00:21

 

 

 

 

 
1
41
25
Пешкин Юрий Сергеевич
+1
00:23

 
-2
01:58

 
-1
02:33

 
1
43
26
Шевелев Роман Русланович
+1
00:30

 

 
-1
01:53

 

 
1
50
27
Ивашева Валерия Михайловна
+1
00:36

 
-3
02:42

 

 
-2
02:40
1
56
28
Черных Елена Алексеевна
-6
01:16

 

 

 

 
+
01:12
1
72
29
Костылева Валентина
+1
00:56

 
-2
02:21

 

 

 
1
76
30
Перков Дмитрий Георгиевич
+1
01:50

 
-1
01:51

 

 

 
1
130
31
Валов Никита Леонидович

 

 
-2
03:08
-3
03:11

 
+
02:24
1
144
32
Чекменёв Владимир
+3
01:51

 
-3
02:22
-5
03:46

 
-1
03:14
1
171
33
Рубцов Павел Александрович
+1
02:50

 

 
-2
03:39

 

 
1
190
34
Евсеева Наталья
+3
02:16

 
-1
02:39

 

 

 
1
196
35
Чухарев Сергей Михайлович
-2
03:13

 

 

 
+
03:19
-3
03:48
1
199
36
Катаев Егор Евгеньевич
+3
02:28
-3
03:21

 
-1
03:49

 
-5
03:41
1
208
37
Изъюров Лев Николаевич
+5
01:50

 

 

 

 
-1
02:09
1
210
38
Колпаков Владимир
-1
01:14

 

 
-2
02:52

 
+1
03:23
1
223
Напалков Владислав Николаевич
-1
00:52

 
-1
01:16

 

 

 
0
0
Ищук Виталий Владимирович
-4
03:18

 
-5
03:21
-1
00:23
-4
03:23

 
0
0
Гусаров Руслан Михайлович
-3
00:55

 
-1
01:07
-1
01:46

 

 
0
0
Приходько Дмитрий Евгеньевич
-2
02:00

 

 
-2
02:00

 

 
0
0
Яковлев Артем Владиславович
-1
01:51

 

 
-1
01:53

 

 
0
0
Дмитрачков Иван Владимирович

 

 
-2
01:52

 

 

 
0
0
Кармадонов Иван Алексеевич
-1
01:12

 
-4
02:17

 

 

 
0
0
Алексеев Валерий Михайлович
-2
01:01

 

 

 

 

 
0
0
Вещицкий Глеб Алексеевич
-2
02:12

 

 

 

 

 
0
0
Бажукова Виктория Владимировна
-2
03:16

 
-2
03:13

 
-1
03:24

 
0
0
Доронин Алексей Андреевич
-2
01:13

 
-1
02:24

 

 

 
0
0
Сажина Алена
-2
02:23

 
-1
00:59

 
-1
01:53

 
0
0
Кудинов Денис Дмитриевич
-2
01:59

 
-1
02:24

 

 

 
0
0
Попыток
110
12
76
64
26
48
Из них зачтено
35
1
9
4
5
20
Не зачтено
75
11
67
60
21
28