Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
dracon4ik
50 / 67 / 20
Регистрация: 26.06.2013
Сообщений: 194
1

Задача для подготовки к региональной олимпиаде

28.01.2014, 20:29. Просмотров 956. Ответов 18
Метки нет (Все метки)

Учительница математики попросила школьников составить арифметическое выражение, так чтобы его значение было равно данному числу N и записать его в тетради. Можно использовать натуральные числа не превосходящие K, операции сложения и умножения, а также скобку. В получившейся строке должно быть как можно меньше чисел.
Пример ввода/вывода
7 3 3+1+3
15 20 15
176 1 (1+1+1+1)*(1+1+1+1)*(1+1+(1+1+1)*(1+1+1))
Подскажите идея как решать, а то даже мыслей нет никаких
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2014, 20:29
Ответы с готовыми решениями:

Выбор учебника для подготовки к олимпиаде АЦМ
Какой лучше подойдет для прочтения перед олимпиадой по программированию АЦМ?

Задача из региональной олимпиады
Чемпионат по стрельбе Ограничения: время – 2 секунды , память – 256Мбайт Победитель школьного...

Задача по олимпиаде
Собственно это мой код . Program Olymp; var i,h,m,s,h1,m1,s1,hase,min,hou,sec,min1,hou1,sec1 :...

Задача об олимпиаде
Не совсем понимаю смысл выделенного: Школьная олимпиада по информатике проводилась для учеников...

Задача по Олимпиаде
Здравствуйте ) Буквально два дня назад написал Олимпиаду по программированию (Школьный этап)....

18
Kill100
425 / 291 / 81
Регистрация: 11.12.2010
Сообщений: 1,209
Завершенные тесты: 1
28.01.2014, 21:25 2
Моя идея.
Берем разложение числа на делители(множетели), -- это надо делать по любому
те которые больше К представляем в виде суммы чисел до К
В итоге все это умножаем.

Добавлено через 2 минуты

Не по теме:

Пс это олимпиадная задача? О_о случайно не A или B ? что то легкая :)


Есть вариант строить дерево, но если просто его строить получится слишком много памяти надо а если метод ветвей и границ то сложно

Ограничение на выполнение 2 сек, 32 мб?, цифры от скольки до скольки?
1
dracon4ik
50 / 67 / 20
Регистрация: 26.06.2013
Сообщений: 194
28.01.2014, 21:31  [ТС] 3
1 секунда, 64 мбайта, N и K до 10000
0
pycture
1183 / 575 / 86
Регистрация: 20.09.2012
Сообщений: 1,857
Завершенные тесты: 3
28.01.2014, 21:32 4
Лучший ответ Сообщение было отмечено dracon4ik как решение

Решение

1) Любое x можно записать как A * B + C
2) Стоимость (кол-во чисел для построения) элементов Ka, Kb, Kc, общая стоимость Kt = Ka + Kb + Kc
Ka и Kb = 1 если A и B <= K, иначе рекурсивно считать стоимость получения A и B
Kc = 0 для C = 0 и = 1 для остальных С
3) C перебираем от 0 до K, подбираем A и B что б в результате Kt было минимальным
1
28.01.2014, 21:32
dracon4ik
50 / 67 / 20
Регистрация: 26.06.2013
Сообщений: 194
28.01.2014, 21:32  [ТС] 5
Задача C
0
pycture
1183 / 575 / 86
Регистрация: 20.09.2012
Сообщений: 1,857
Завершенные тесты: 3
28.01.2014, 21:33 6
Цитата Сообщение от Kill100 Посмотреть сообщение
Берем разложение числа на делители(множетели), -- это надо делать по любому
те которые больше К представляем в виде суммы чисел до К
N = 66 K = 8 правильный ответ 2 + 8 * 8 => 3 числа. У вас сколько получится?
0
dracon4ik
50 / 67 / 20
Регистрация: 26.06.2013
Сообщений: 194
28.01.2014, 21:38  [ТС] 7
Я извиняюсь - условие задачи немного неправильно написал - не чисел, а символов.
0
Kill100
425 / 291 / 81
Регистрация: 11.12.2010
Сообщений: 1,209
Завершенные тесты: 1
28.01.2014, 21:38 8
Цитата Сообщение от pycture Посмотреть сообщение
N = 66 K = 8 правильный ответ 2 + 8 * 8 => 3 числа. У вас сколько получится?
Ага точно прокол. На 1 больше.
0
dracon4ik
50 / 67 / 20
Регистрация: 26.06.2013
Сообщений: 194
28.01.2014, 21:43  [ТС] 9
pycture, Kill100, спасибо, разобрался
0
rattrapper
foo();
872 / 574 / 222
Регистрация: 03.07.2013
Сообщений: 1,549
Записей в блоге: 2
30.01.2014, 22:24 10
dracon4ik, Kill100, pycture, сорри, но меня очень зацепила задача, а решения никак не добьюсь. Можно, хоть примерно, как должна выглядеть реализация алгоритма в коде (интересует именно с количеством символов, а не чисел), а то у меня то результат неадекватный, то StackOverflow, и никак вообще не получается. Спасибо
0
pycture
1183 / 575 / 86
Регистрация: 20.09.2012
Сообщений: 1,857
Завершенные тесты: 3
30.01.2014, 22:30 11
Цитата Сообщение от rattrapper Посмотреть сообщение
как должна выглядеть реализация алгоритма
Алгоритм выше. Оттого что будут считаться символы вместо чисел, он не меняется.
Меняются только незначительные детали реализации, а в целом все тоже самое.

Или вам весь код надо?
0
rattrapper
foo();
872 / 574 / 222
Регистрация: 03.07.2013
Сообщений: 1,549
Записей в блоге: 2
31.01.2014, 00:54 12
Цитата Сообщение от pycture Посмотреть сообщение
Или вам весь код надо?
просто я совсем не представляю, как это должно выглядеть, хотя бы псевдокод какой-нибудь, а то я в полном ступоре
0
Psilon
Master of Orion
Эксперт .NET
6039 / 4892 / 903
Регистрация: 10.07.2011
Сообщений: 14,495
Записей в блоге: 5
Завершенные тесты: 4
31.01.2014, 01:01 13
Бесят эти олимпиадные задачи. Чтобы узнать, знают ли школьники разложение на множители и какую-нибудь теорему вводят всяких Миш, Маш, их лучшего друга Петю, выдумывают истории их странных взаимоотношений, просят рассчитать погоду на Марсе с учетом того, что Бетельгейзе вошла в стрельца, вместо грамотного и четкого построения задачи...
2
tezaurismosis
31.01.2014, 10:15
  #14

Не по теме:

Psilon, это чтобы школьники умели отделить зёрна от плевел и не зацикливались на Машах/Мишах. Ведь чтобы адекватно самому ставить или решать реальные задачи, нужно уметь отделять важное от бесполезного.

0
Somebody
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
31.01.2014, 17:02 15
А мне всегда в задачах нравились золотые апельсины на яблонях и летающие над деревней центрифуги с близлежащего завода...
А код какой-то такой (на плюсах):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
 
enum class ExprType {number, sum, product};
 
struct Expr
{
    ExprType type;
    unsigned length;
    std::pair<unsigned, unsigned> operands;
};
 
template<class T>
std::string ExprToString(const T& exprs, unsigned n)
{
    const Expr& expr = exprs[n];
    switch (expr.type)
    {
    case ExprType::number:
        return std::to_string(n);
    case ExprType::sum:
        return ExprToString(exprs, expr.operands.first) + '+' +
            ExprToString(exprs, expr.operands.second);
    case ExprType::product:
        std::string op1 = ExprToString(exprs, expr.operands.first);
        std::string op2 = ExprToString(exprs, expr.operands.second);
        if (exprs[expr.operands.first].type == ExprType::sum)
            op1 = '(' + op1 + ')';
        if (exprs[expr.operands.second].type == ExprType::sum)
            op2 = '(' + op2 + ')';
        return op1 + '*' + op2;
    }
    throw "O_o";
}
 
int main()
{
    unsigned n, k;
    std::cin >> n >> k;
 
    std::vector<Expr> exprs(n + 1);
    for (unsigned i = 1; i <= k; i++)
        exprs[i] = {ExprType::number, unsigned(std::log10(i) + 1)};
    for (unsigned i = k + 1; i <= n; i++)
        exprs[i] = {ExprType::number, 100500};
 
    for (unsigned i = 1; i < n; i++)
    {
        for (unsigned j = 1; j <= std::min(i, n - i); j++)
        {
            unsigned s = i + j;
            unsigned lenS = exprs[i].length + exprs[j].length + 1;
            if (lenS < exprs[s].length)
                exprs[s] = {ExprType::sum, lenS, {i, j}};
        }
        for (unsigned j = 1; j <= std::min(i, n / i); j++)
        {
            unsigned p = i * j;
            unsigned lenP = exprs[i].length + exprs[j].length + 1 +
                2 * (exprs[i].type == ExprType::sum) +
                2 * (exprs[j].type == ExprType::sum);
            if (lenP < exprs[p].length)
                exprs[p] = {ExprType::product, lenP, {i, j}};
        }
    }
    std::cout << ExprToString(exprs, n);
}
0
rattrapper
foo();
872 / 574 / 222
Регистрация: 03.07.2013
Сообщений: 1,549
Записей в блоге: 2
31.01.2014, 17:14 16
Somebody, спасибо, жаль c++ не знаю, main() не осилил
0
pycture
1183 / 575 / 86
Регистрация: 20.09.2012
Сообщений: 1,857
Завершенные тесты: 3
31.01.2014, 21:04 17
Цитата Сообщение от Somebody Посмотреть сообщение
А код какой-то такой (на плюсах)
Я правильно понимаю что для N = 64 , K = 3 код дает
Код
(3*3*3+3+2)*2
?
1
Psilon
Master of Orion
Эксперт .NET
6039 / 4892 / 903
Регистрация: 10.07.2011
Сообщений: 14,495
Записей в блоге: 5
Завершенные тесты: 4
31.01.2014, 21:15 18
Somebody, не могу оценить код т.к. не совсем понимаю задание. Не могли бы нормально переформулировать? Входные данные не осилил. То что дерево выражений строите - понял, а вот что и как - не особо.
0
Somebody
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
31.01.2014, 22:19 19
Цитата Сообщение от pycture Посмотреть сообщение
Я правильно понимаю что для N = 64 , K = 3 код дает
Код
(3*3*3+3+2)*2
?
Ага, печаль. Уже было собрался делать отдельно массивы сумм и произведений, но нагуглил разбор решения. Видимо, достаточно в 66-й строчке <= поставить. Только пока не до конца понял почему... Понятно, что при одинаковой длине представление числа в виде произведения не хуже, чем в виде суммы. Понятно, что если сумма на два символа короче произведения, то она не хуже. Понятно, что если сумма на один символ короче произведения, то она может пригодиться только в качестве слагаемого другой суммы (которую можно составить по-другому, перегруппировав слагаемые). Но дальше пока не соображу...
0
31.01.2014, 22:19
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.01.2014, 22:19

Задача считалочка по олимпиаде
имя входного файла mult.in имя выходного файла mult.out максимальное время работы на одном тесте...

Ищу 11 класс для участие в командной уральской олимпиаде для школьников
Нужен 1 человек в команду. пишите

Приложение для подготовки документа на бланке
Здравствуйте! Помогите мне пожалуйста с заданием. Выдаёт ошибку моё приложение. Скрин:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru