Задача 4

13 сентября 2004 Написать комментарий К комментариям

Специально для
Дан набор валют и их курсы по отношению друг к другу, необходимо выделить последовательность обменов валют друг на друга которая даст в итоге прибыль.
Например 1 доллар может купить 0.7 Британских Фунтов 1 Фунт может купить 9.5 французских франков и 1 Франк покупает 0.16 долларов США, тогда:
1×0.7×9.5×0.16 = 1.064 долларов, что дает 6,4 процента прибыли.

Формат входных данных: Дано число n — размер таблицы 2 <= n <= 20. Первая строка представляет собой курсы обмена валют между первой и n-1 другими странами.

Формат выходных данных:
Для каждой таблицы необходимо определить последовательность обменов которая дает в результате более чем 0.01 процент прибыли. Если таких последовательностей несколько то необходимо напечатать последовательность МИНИМАЛЬНОЙ ДЛИНЫ. Если последовательность не существует то необходимо напечатать: «no arbitrage sequence exists»

Categories: Программирование Tags:
  1. Turbo
    12 сентября 2004 в 22:19 | #1
    Ответить | Цитата

    Пример входных данных:

    3
    1.2 .89
    .88 5.1
    1.1 0.15
    4
    3.1 0.0023 0.35
    0.21 0.00353 8.13
    200 180.559 10.339
    2.11 0.089 0.06111
    2
    2.0
    0.45

    Ответ:

    1 2 1
    1 2 4 1
    no arbitrage sequence exists

  2. Turbo
    12 сентября 2004 в 22:26 | #2
    Ответить | Цитата

    Большой вход:
    20
    0.38 0.88 0.33 0.85 0.76 0.62 0.15 0.69 0.42 0.96 0.19 0.62 0.54 0.90 0.95 0.08 0.99 0.78 0.42
    0.51 0.86 0.43 0.20 0.21 0.27 0.24 0.21 0.20 0.37 0.11 0.74 0.50 0.44 0.52 0.71 0.62 0.49 1.03
    0.51 0.06 0.83 0.68 0.60 0.48 0.37 0.11 0.15 0.68 0.47 0.54 0.63 0.80 0.49 0.23 0.87 1.03 0.57
    0.37 0.62 0.55 0.94 0.58 0.61 0.09 0.85 0.69 0.78 0.92 0.89 0.76 0.46 0.25 0.83 0.21 0.49 0.12
    0.01 0.40 0.31 0.09 0.38 0.42 1.03 0.81 1.00 0.04 0.91 0.46 0.21 0.41 0.05 0.65 0.69 0.84 0.70
    0.88 1.04 0.69 0.38 0.61 0.57 0.36 0.24 0.72 0.12 0.95 0.71 0.98 0.56 0.34 0.76 0.33 0.68 0.94
    0.03 0.40 0.73 0.70 0.25 0.24 0.41 0.92 0.71 0.87 0.23 0.75 0.76 0.59 0.51 1.00 0.55 0.62 0.70
    0.65 0.72 0.95 0.65 0.40 0.99 0.59 0.25 0.85 0.80 0.45 0.64 0.46 0.36 0.77 0.28 0.92 0.24 0.92
    0.78 0.49 0.05 0.01 0.73 0.06 0.98 0.67 0.29 0.27 0.48 0.43 0.46 0.61 0.71 0.76 0.56 0.28 0.33
    0.81 0.73 0.92 0.16 0.97 0.77 1.03 0.86 0.38 0.62 0.89 0.48 0.45 0.08 1.04 0.76 0.11 0.20 0.18
    0.63 0.70 0.49 0.64 0.73 0.51 0.41 0.51 0.35 0.31 0.33 0.75 0.10 0.84 0.94 0.90 1.02 0.33 0.80
    0.67 0.57 0.94 0.86 0.02 0.67 0.14 0.49 0.75 0.82 0.41 0.28 0.45 0.31 0.31 0.32 0.21 0.03 0.78
    0.26 0.88 0.17 0.01 0.56 0.04 0.93 1.04 0.79 0.39 0.36 0.69 0.65 0.80 0.99 0.30 0.42 1.00 0.99
    0.42 0.10 0.00 0.35 0.38 0.56 0.64 1.01 0.67 0.55 0.56 0.41 0.05 0.16 0.42 0.74 0.40 0.26 0.83
    0.58 1.03 0.66 0.16 0.84 0.06 0.69 1.04 0.62 0.77 0.98 0.67 0.50 0.05 0.74 0.60 0.89 0.91 1.03
    0.57 0.68 0.95 0.99 0.27 0.14 1.02 0.34 0.23 0.97 0.22 0.66 0.70 0.09 0.64 0.20 0.39 0.14 1.04
    0.37 0.14 0.50 0.64 0.30 0.17 1.00 1.01 0.98 0.34 1.03 0.72 0.94 0.67 0.74 0.82 0.75 0.57 0.69
    0.84 0.29 0.53 0.01 0.77 0.09 0.93 0.94 0.11 0.32 0.36 0.11 1.00 0.38 0.30 0.74 0.80 0.77 0.94
    0.04 0.48 0.97 0.54 0.81 0.33 0.67 0.10 0.83 0.94 0.22 0.52 0.90 0.62 0.79 0.90 0.40 0.26 0.23
    0.55 0.48 0.75 0.96 0.65 0.21 0.98 0.71 0.91 0.63 0.94 0.62 0.56 0.90 0.89 0.00 0.43 0.43 0.08

    Выход:
    10 16 10 16 10

  1. Пока что нет уведомлений.