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

Простенькая задачка из 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. двумерные массивы Дана целочисленная квадратная матрица. Найти в каждой строке... подробнее

Показать сообщение отдельно
ВВП
Сообщений: n/a
03.05.2013, 16:40
Фишка в том, что необходимо сделать перебор 2^(N-1)-1 куче, т.к. нет формулы для решения. Организаторы не зря выбрали 20 максимум,т.к. не все языки успеют это сделать.
1) выбрать элементы, которые будем перебирать.
2) Собрать кучки и запомнить минимум.
3) заново провернуть операцию (пока не сделаем все переборы)
Пример правильного решения, но на C#
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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            #region запись чисел в массив и подсчет суммы
            byte am =byte.Parse(Console.ReadLine());
            string[] str = Console.ReadLine().Split(' ');
            int[] str_int = new int[str.Length];
            int sum = 0; //общая сумма
            for (int i = 0; i < am; ++i)
            {
                str_int[i] = int.Parse(str[i]);
                sum += str_int[i];
            }
            #endregion
 
            #region поиск минимальной разницы
            int min = sum;
            int non = (int)(Math.Pow(2, am - 1) - 1);//всего переборов
            for (int i = 0; i < non; ++i)
            {
            int num=i + 1;
            byte[] a = new byte[am];
            int t = 0;
            for (; num != 1; ++t)
            {
                a[t] = (byte)(num % 2);
                num /= 2;
            }
            a[t] = 1;
            int data = 0; // число для счетов
                for (int k = 0; k < am; k++)
                    if (a[k] == 1)
                        data += str_int[k];
                int data2 = sum - data;
                if (min > Math.Abs(data - data2))
                    min = Math.Abs(data - data2);
            }
            Console.WriteLine(min);
            #endregion
 
        }
    }
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru