Форум DL

Мой профиль

2018
Придуманы решения: M, A, J, C
Доделано решение: F
Итого: L, G, E, F, M, A, J, C
Остались: K, H, I

Мой профиль

В форуме описаны только 4 решения.
Где описания других решений?
Кто их будет делать?

Кто какие решения будет писать?

Мой профиль

A. Alice the Fan
УСЛОВИЕ
Есть две команды, играющие в игру в несколько раундов.
Для каждой команды нам дано количество голов(очков),
которые были забиты за все раунды.
Наша прога должна среди всех возможных игр с указанными голами найти такую,
в которой команда №1 выиграла как можно больше матчей в сравнении с командой №2.
Игра ведётся в несколько раундов. Играют до трёх побед.
Раунд заканчивается, когда какая-нибудь команда набирает не меньше 25 очков и
лидирует над другой командой на минимум 2 очка.
Исключение: в пятом раунде игра до 15 очков, не 25.

ПРИМЕР
Input: 90 90
90 -- это слишком много для трёх поражений, поэтому вторая команда должна
выиграть хотя бы один раз.
Таким образом оптимальный счёт: 3:1 в пользу первой команды.
Он может быть достигнут 4-мя раундами с такими очками:
Раунд №1: 15:25. Выиграла команда №2
Раунд №2: 25:23. Выиграла команда №1
Раунд №3: 25:23. Выиграла команда №1
Раунд №4: 25:19. Выиграла команда №1
Итого: 90:90 3:1

РЕШЕНИЕ
Перебираем все возможные соотношения выигранных матчей в порядке уменьшения
успехов первой команды:
3:0, 3:1, 3:2, 2:3, 1:3, 0:3
Для каждого соотношения пытаемся распределить по раундам очки так, чтобы
получить нужные нам количества побед каждой команды.
Распределяем так:
Сначала запихиваем по 25(или 15) очков в победные раунды.
Оставшиеся очки как-нибудь распределяем между всеми раундами.
Если получилось => выводим ответ.
Иначе рассматриваем следующее по оптимальности возможное
соотношение выигранных матчей.

ПРИМЕР
Input: 90 90
3:0
Расределяем по 3-м раундам по 25 очков команде #1:
25:0 25:0 25:0 осталось очков: 15:90
Распределяем оставшиеся очки:
30:28 30:28 30:28 осталось очков: 0:6
У нас остались лишние очки, которые некуда распределить, поэтому мы
вынуждены перейти к следующему возможному соотношению выигранных матчей.
3:1
Расределяем по 3-м раундам по 25 очков команде #1:
0:0 25:0 25:0 25:0 осталось очков: 15:90
Расределяем по 1-му раунду по 25 очков команде #2:
0:25 25:0 25:0 25:0 осталось очков: 15:65
Распределяем оставшиеся очки:
15:25 25:22 25:22 25:21 осталось очков: 0:0
Success!
Ответ: счёт 3:1 с раундами 15:25, 25:22, 25:22, 25:21.

Пишу я или Илья, если проявит инициативу.

Мой профиль

C. Cactus Search
УСЛОВИЕ
Есть кактус из 500 вершин.
Тестер загадывает вершину.
А нам нужно интерактивно найти эту вершину за 10 ходов.
За ход можно спросить в какой стороне вершина относительно какой-нибудь другой вершины.

РЕШЕНИЕ
1. Находим расстояние от каждой вершины до каждой.
2. Зная эти расстояния для каждой вершины для каждого её ребра
находим количество вершин, которые находятся по ту сторону ребра.
3. Выбираем вершину, у которой минимально минимальное кол-во вершин за ребром.
4. Спрашиваем: в какой стороне от этой вершины загаданная вершина.
5. Отрезаем ту часть кактуса, которая не в той стороне, в которую указал
тестер.
6. Повторяем 3..5 пока не угадаем загаданную вершину.

Пишу я или Илья, если проявит инициативу.

Мой профиль

M
УСЛОВИЕ
Дан ориентированный граф.
Каждая вершина графа олицетворяется с одной кубической комнатой 3d пещеры.
Мы должны построить такую пещеру, чтобы возможности попасть из одной комнаты в другую
соответствовали графу.
В 3d пещере можно ходить по земле и прыгать в ямки/туннели.

ПРИМЕР
Input: 1 -> 2 -> 3
Т.е. мы должны построить такую пещеру, что из комнаты №1 можно попасть
в комнату №2, а из неё можно попасть в комнату №3, но нельзя в №1.
Решением является вот такая пещера(вид сбоку):

^ z
|
|####################
|## 1 ##########
|####### #######
|####### 2 ####
|############ ###
|############ 3 ###
|#################### x
+--------------------->
В ней мы можем прыжком из комнаты 1 попасть в комнату 2, а из неё в 3.
Но из комнаты №3 нельзя допрыгнуть до комнаты №2.

РЕШЕНИЕ
Делаем топологическую сортировку графа.
Находим его компоненты сильной связности.
Выделяем под каждую компоненту по этажу. При этом этажи раполагаем в
порядке топологической сортироки, т.е. если есть стрелка U -> V,
то этаж с U делаем выше этажа с V, чтобы можно было из U упасть в V.
После этого добавляем дырки/туннели в соответствии со стрелочками графа.

ПРИМЕР
Input: 1 -> 2 -> 3 -> 4, 3 -> 2
Выполняем топологическую сортировку и находим компоненты сильной связности.
[1] -> [2, 3] -> [4]
Для вышеуказанных компонент связности делаем этажи:

  y
^     Этаж №3
|                     
|#########
|#### ####
|#### ####
|####1####
|#### ####
|#### ####
|#########             x
+--------------------->

  y
^     Этаж №2
|                     
|#########
|#### ####
|#### ####
|####2####
|####3####
|#### ####
|#########             x
+--------------------->

  y
^     Этаж №1
|                     
|#########
|#### ####
|#### ####
|####4####
|#### ####
|#### ####
|#########             x
+--------------------->

Следует отметить, что у каждого этажа должен быть пол чтобы отделить его от
остальных этажей. Поэтому на самом деле у нас будет 6 этажей.

  y
^         z = 6
|                     
|#########
|#### ####
|#### ####
|####1####
|#### ####
|#### ####
|#########             x
+--------------------->

  y
^         z = 5
|                     
|#########
|#########
|#########
|#########
|#########
|#########
|#########             x
+--------------------->

  y
^         z = 4
|                     
|#########
|#### ####
|#### ####
|####2####
|####3####
|#### ####
|#########             x
+--------------------->

  y
^         z = 3
|                     
|#########
|#########
|#########
|#########
|#########
|#########
|#########             x
+--------------------->

  y
^         z = 2
|                     
|#########
|#### ####
|#### ####
|####4####
|#### ####
|#### ####
|#########             x
+--------------------->

  y
^         z = 1
|                     
|#########
|#########
|#########
|#########
|#########
|#########
|#########             x
+--------------------->

Теперь добавляем туннели [1] -> [2, 3] и [2, 3] -> 4

  y
^         z = 6
|                     
|#########
|#### ####
|#### ####
|####1  ##
|#### ####
|#### ####
|#########             x
+--------------------->

  y
^         z = 5
|                     
|#########
|#########
|#########
|###### ##
|#########
|#########
|#########             x
+--------------------->

  y
^         z = 4
|                     
|#########
|#### ####
|#### ####
|####2  ##
|####3####
|####   ##
|#########             x
+--------------------->

  y
^         z = 3
|                     
|#########
|#########
|#########
|#########
|#########
|###### ##
|#########             x
+--------------------->

  y
^         z = 2
|                     
|#########
|#### ####
|#### ####
|####4####
|#### ####
|####   ##
|#########             x
+--------------------->

  y
^         z = 1
|                     
|#########
|#########
|#########
|#########
|#########
|#########
|#########             x
+--------------------->

Теперь из комнаты №1 можно упасть в комнату №2, но не наоборот.
Всё! Мы спроектировали пещеру.

Мой профиль

J.
УСЛОВИЕ.
Даны ключевые слова выдуманного языка программирования и какой-то код на нём.
Нужно удалить из кода комментарии и лишние пробелы.
А ещё переименовать переменные, чтобы они были в
лексикографическом порядке от "a" до "zzzz..."
П.С. комментарий -- это то, что после знака "#"

ПРИМЕР
Ключевые слова: print input
input: print hello world #some random text
output: print a b

РЕШЕНИЕ
Распарсить ввод. Вывести вывод.

Мой профиль

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

Мой профиль

Михаил Долинский:

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

Тесты точно буду я придумывать

Мой профиль

Михаил Долинский:

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

Делаю то, что не делает Илья.

Мой профиль

Осталось узнать, что делает Илья

Мой профиль

Здравствуйте, Михаил Семёнович.
Мне Егор сообщил, что я 100% решаю первые 3 задачи: L,E,G. Может ещё F задачу(там не дописано решение). Насчёт остальных, я просмотрю, если я смогу реализовать - реализую и отпишу.

Мой профиль

Егор Короткевич:

2018
Придуманы решения: M, A, J, C
Доделано решение: F
Итого: L, G, E, F, M, A, J, C
Остались: K, H, I

F доделано уже.
Пока Илья не определился с тем, что будет писать,
что Влад будет делать?
Ждать?

Мой профиль

2018

A
10
75 0
90 90
20 0
0 75
78 50
80 100
50 46
55 51
50 47
50 50
-----------
3:0
25:0 25:0 25:0
3:1
25:22 25:22 15:25 25:21
Impossible
0:3
0:25 0:25 0:25
3:0
25:11 28:26 25:13
3:2
25:17 0:25 25:22 15:25 15:11
2:0
25:23 25:23
2:0
25:23 30:28
2:1
25:0 25:22 0:25
2:2
25:0 25:0 0:25 0:25

C это интерактор так что я хз как ты проверять будешь
5 2
5 1 2 3 4 5
2 1 3
----------
5

6 1
7 1 2 5 6 2 3 4
----------
4

3 1
4 1 2 3 1
----------
1

5 2
3 1 3 5
3 1 2 4
----------
2

7 2
6 1 2 3 4 5 3
3 6 5 7
----------
6

15 6
13 1 2 3 4 1 5 6 7 8 9 7 10 5
2 10 11
2 10 12
2 9 13
2 9 14
2 9 15
----------
11

1 0
----------
1

2 1
2 1 2
----------
2

4 1
5 1 2 3 1 4
----------
2

5 1
6 1 2 3 1 4 5
----------
4

6 2
6 1 2 3 1 4 5
2 4 6
----------
4

E
2
----------
a8 h8

3
----------
b1 b8 h8

8
----------
b1 c1 d1 e1 f1 g1 g8 h8

9
----------
b1 c1 d1 e1 f1 g1 h1 h7 h8

11
----------
b1 c1 d1 e1 f1 g1 h1 h2 a2 a8 h8

13
----------
b1 c1 d1 e1 f1 g1 h1 h2 a2 b2 c2 c8 h8

17
----------
b1 c1 d1 e1 f1 g1 h1 h2 a2 b2 c2 d2 e2 f2 g2 g8 h8

18
b1 c1 d1 e1 f1 g1 h1 h2 a2 b2 c2 d2 e2 f2 g2 g3 g8 h8
----------

19
----------
b1 c1 d1 e1 f1 g1 h1 h2 a2 b2 c2 d2 e2 f2 g2 g3 h3 h7 h8

20
----------
b1 c1 d1 e1 f1 g1 h1 h2 a2 b2 c2 d2 e2 f2 g2 g3 h3 f3 f8 h8

48
----------
.... g6 g8 h8

49
----------
.... g6 h6 h7 h8

50
----------
.... g6 g7 g8 f8 h8

51
----------
.... g6 h6 h7 g7 g8 h8

52
----------
.... g6 h6 h7 g7 f7 f8 h8

58
----------
.... a8 g8 h8

59
----------
.... a8 b8 g8 h8

62
----------
.... e8 g8 h8

63
----------
.... e8 f8 g8 h8

F
2
----------
NO

6
----------
YES
2
1 2
1 3

3
----------
NO

4
----------
NO

5
----------
NO

8
----------
NO

10
----------
YES
2
2 5
1 2

30
----------
YES
2
1 2
7 15

G
3
2
0 1 0 0 0 0 0
100000000
1 0 0 0 1 0 1
1
1 0 0 0 0 0 0
3
0 1 0 0 1 0 1
----------
8
233333332
1
6

I
5 998244353
1
4
5
9
----------
1
2
6
28146

1 437122297
20
----------
67777575

J тест сломан

16
fun while return var { } ( ) , ; > = + ++ - --
9
fun fib(num) { # compute fibs
var return_value = 1, prev = 0, temp;
while (num > 0) {
temp = return_value; return_value = return_value + prev;
prev = temp;
num--;
}
return return_value;
}
---------
fun a(b){var c=1,d=0,e;while(b>0){e=c;c=c+d;d=e;b--;}return c;}

10
( ) + ++ : -> >> >>: b c)
2
($val1++ + +4 kb) >>

ut
b-> + 10 >>: t # using >>:
---------
(a+++ +4c )>> :d b->+10>>:e

K
19
? 3
+ 2 2
? 3
? 4
+ 5 2
? 5
? 6
+ 1 2
? 2
? 3
? 4
? 5
? 6
? 7
? 9
- 8
? 2
? 3
? 6
---------
0
1
0
2
1
3
2
1
2
1
0
0
2
1
1

L
8 7
1 1 3 1 5 3 7 1
5 7 4 8 1 3 5 2
-----------
10

3 3
3 1 2
5 3 4
-----------
0

1 1
1
5
-----------
0

3 1
1 1 1
5 2 3
-----------
0

3 2
1 2 1
5 2 3
-----------
0

3 2
1 1 1
5 2 3
-----------
2

M вывод лучше проверять в ручную
4
0 1 0 1
0 0 1 0
0 1 0 0
1 0 0 0

1
1

2
1 1
1 0

9
1 1 1 0 0 0 1 0 1
0 1 0 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1 1
0 0 1 1 1 1 0 1 0
0 0 0 1 0 0 0 0 0
1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 1 1 0
1 0 1 0 1 0 1 0 1

Мой профиль

Тестируем ascii-смайлики:

Мой профиль

Итоги сегодняшнего дня:
Написали A, J, M. Почти написали C, F
Решили H, K
Осталась нерешенной только I.
Итого решено: E, G, L, K, H, J, M, A, C, F
Итого написано: E, G, L, A, J, M
Илья пишет F
Влад пишет H, K, C
Егор решает I
Влад решает I
Егор придумывает тесты на F, E, G, L
Влад тоже придумывает тесты A, F