Форум программистов, компьютерный форум, киберфорум
Наши страницы

Простенькая задачка из Timus Online Judge(1005. Куча камней) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Обучиться и самому написать толковый клиент\программу http://www.cyberforum.ru/cpp-beginners/thread355658.html
Здравствуйте нужно как можно быстрее обучиться языкам для написания программы. Она должна работать только по интернету. Что мне для этого нужно знать ? SQL, C++ ?.. Можно ли объединять в одной...
C++ Подсчитать количество слов и определить и вывести на экран максимальное и минимальное слова и их длину. Подсчитать количество слов и определить и вывести на экран максимальное и минимальное слова и их длину. Помогите написать...срочно очень нужно... есть фотография этой проги нужно ее... http://www.cyberforum.ru/cpp-beginners/thread355655.html
C++ Подсчитать средний код всех выведенных на экран символов
Написать программу, которая: - выводит на экран перечень городов в виде столбца, первые буквы строк которого составляют фамилию студента (буквы ‘ы’, ‘ь’, и ‘ъ’ фамилии исключаются); -...
Игра в города C++
Нужно реализовать в С++ Игра в города Условие задачи: Всем известны правила игры "в города": первый игрок называет произвольный город, следующий - город, название которого начинается на ту же...
C++ не выполнимое задание http://www.cyberforum.ru/cpp-beginners/thread355610.html
Задайте две таблицы. Одна содержит наименование услуг, а другая – расценки за эти услуги. Удалите из обеих таблиц все строки, которые предшествуют услуге, цена которой Р рублей. Даже не знаю как...
C++ Циклы и двумерные массивы 1. Цикл For... Среди всех n-значных чисел (n = 1,2,3,4) указать те, сумма цифр которых равна данному числу k. 2. двумерные массивы Дана целочисленная квадратная матрица. Найти в каждой строке... подробнее

Показать сообщение отдельно
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.09.2011, 16:38
Цитата Сообщение от Whiteha Посмотреть сообщение
Объясните пожалуйста алгоритм для решения этой задачи!
Алгоритм из моего решения - создаем массив знаков между числами. Получается двоичное число. Увеличивая это двоичное число мы получаем различные расстановки знаков между числами. При этом каждый раз считаем сумму чисел с учетом знаков. Если модуль числа меньше минимума, то оно - новый минимум. Могу еще динамику рюкзаком рассказать, но это уже сложнее.

Прокомментил код:
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
#include <iostream>
#include <cstdlib> //for abs
 
int q[24], w[24], n, s, i, x, m = 1e9;
//так как глобальная область, то все элементы массива равны нулю,
//т.е. изначально все знаки минусы, т.к. 0 соответствует минусу, а 1 - плюсу.
 
int main()
{   
    for (std::cin >> n; i < n;)
                std::cin >> w[i++];
    
    for ( ;!*q ;) //пока старший разряд равен нулю
    {
        for (x = *w, i = 0; ++i < n ; ) //находим сумму с учетом знаков
            x  += q[i] ?  w[i] : -w[i];
        
        m = std::min(abs(x), m); // сравниваем с минимум
        
        for ( ++q[n-1], i = n; --i && q[i] > 1; ++q[i-1]) //увеличиваем двоичное число
            q[i] = 0;
    }
    
    std::cout << m;
}
3
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru