Версия для печати
Убрать все задачи

---

Задано арифметическое выражение, содержащее операции сложения, умножения, круглые скобки и операнды, которыми являются буквы английского алфавита. Нас будет интересовать скорость вычисления таких выражений на многопроцессорной машине, поэтому скобки в них будем расставлять в обязательном порядке для указания порядка проведения операций.

Известно, что сложение двух чисел занимает время p, а умножение – время q. Время, необходимое для вычисления сложного выражения A^oB, равно времени, затрачиваемому на выполнение операции ^o, плюс максимальное из двух чисел – времени вычисления подвыражения A и времени вычисления подвыражения B. Время вычисления операнда полагаем равным нулю. Требуется написать программу, которая: 
    1. Определяет время, необходимое для вычисления заданного выражения на многопроцессорной машине. 
    2. Находит эквивалентное заданному арифметическое выражение с минимальным временем вычисления и само это время.

Выражения называется эквивалентными, если одно из них можно получить из другого последовательностью следующих преобразований:
    x + y → y + x ,                    x * y → y * x                    (коммутативный закон),
    x + (y + z) → (x + y) + z ,    x * (y * z) → (x * y) * z    (ассоциативный закон).

Входные данные
В первой строке входного файла содержатся два целых числа p и q (1 ≤ p,q ≤ 1000), во второй – арифметическое выражение длиной не более 200 символов.

Выходные данные
Первая строка выходного файла должна содержать ответ на первый пункт задачи. Во вторую строку выведите эквивалентное заданному выражение с минимальным временем вычисления, а в третью – само это время.

Пример входного файла
1 1
((a+(b+(c+d)))*e)*f

Пример выходного файла
5
((a+b)+(c+d))*(e*f)
3

   Решение

---

Пусть A — произвольный угол, B и C — острые углы. Всегда ли существует такой угол X, что

(Из `` Воображаемой геометрии'' Н. И. Лобачевского).

   Решение

Страница: 1 2 3 4 >> [Всего задач: 18]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 77901

Темы:   [ Взвешивания ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3 Классы: 8,9

Имеется 555 гирь весом: 1 г, 2 г, 3 г, 4 г,...555 г. Разложить их на 3 равные по весу кучи.

Прислать комментарий

Решение

---

Задача 77905

Тема:   [ Тригонометрические неравенства ]

Сложность: 3 Классы: 10,11

Пусть A — произвольный угол, B и C — острые углы. Всегда ли существует такой угол X, что

(Из `` Воображаемой геометрии'' Н. И. Лобачевского).

Прислать комментарий

Решение

---

Задача 77902

Тема:   [ Углы, опирающиеся на равные дуги и равные хорды ]

Сложность: 3 Классы: 8,9

Даны 3 окружности O₁, O₂, O₃, проходящие через одну точку O. Вторые точки пересечения O₁ с O₂, O₂ с O₃ и O₃ с O₁ обозначим соответственно через A₁, A₂ и A₃. На O₁ берем произвольную точку B₁. Если B₁ не совпадает с A₁, то проводим через B₁ и A₁ прямую до второго пересечения с O₂ в точке B₂. Если B₂ не совпадет с A₂, то проводим через B₂ и A₂ прямую до второго пересечения с O₃ в точке B₃. Если B₃ не совпадет с A₃, то проводим через B₃ и A₃ прямую до второго пересечения с O₁ в точке B₄. Докажите, что B₄ совпадает с B₁.

Прислать комментарий

Решение

---

Задача 77903

Тема:   [ Против большей стороны лежит больший угол ]

Сложность: 3 Классы: 8,9

Пусть a, b, c — длины сторон треугольника; A, B, C — величины противоположных углов. Докажите, что

Прислать комментарий

Решение

---

Задача 77904

Тема:   [ Задачи на движение ]

Сложность: 3+ Классы: 8,9

Из пункта A в другие можно попасть двумя способами: 1) выйти сразу и идти пешком; 2) вызвать машину и, подождав ее определённое время, ехать на ней. В каждом случае используется способ передвижения, требующий меньшего времени. При этом

Скорости пешехода и машины, а также время ожидания машины, принимаются неизменными. Сколько понадобится времени для достижения пункта, отстоящего от A на 6 км?

Прислать комментарий

Решение

---

Страница: 1 2 3 4 >> [Всего задач: 18]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями