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

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

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

Показать сообщение отдельно
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
24.09.2011, 16:33  [ТС]     Простенькая задачка из Timus Online Judge(1005. Куча камней)
Я просёк свои ошибки, наставил костылей... и проблема пришла откуда не ждали - мой алгоритм г**но, работающее лишь в частных случаях.(
Объясните пожалуйста алгоритм для решения этой задачи!
Моя идея была такова:
1) Произвольно разбили камни на две кучки
2) Посчитали разность между ними
3) Из большей кучки нашли камень который по своему весовому значению максимально приближен к разности и меньше её, если такового нет - вывод ответа.
4)Перекладываем его в другую кучку
5)Повторяем с пункта 1 по п4 столько раз, сколько всего у нас камней.

На всякий случай вот код с последними костылями.
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
using namespace std;
long int N = 0, A = 0, *W, *W1, *W2, a_buf1 = 0, a_buf2 = 0,             //
         buff = 0, b = 0, i1 = 0, i2 = 0, buf = 0, buf2 = 0;             //
int rec();
void main() 
{
    cin >> N;
    W  = new long int[N];
    W1 = new long int[N];
    W2 = new long int[N];
    for(int i = 0; i < N; ++i) W[i] = W1[i] = W2[i] = 0;
    for(int i = 0; i < N; ++i) cin >> W[i];                                  
    buff = (N) / 2;
    for(int i = 0; i < buff; ++i)
    {
        W1[i] = W[i];
    }
    for(int j = 0, i = buff; i < N; ++i, ++j)
    {
        W2[j] = W[i];
    }
    //
    // До этого момента всё Ok
    //
    b = N;
    A = rec();
    //cout<<"___W1:"<<endl;
    for(int i = 0; i < N; ++i) {if(W1[i] > 0)cout<<W1[i]<<endl;}
    //cout<<"___W2:"<<endl;
    for(int i = 0; i < N; ++i) {if(W2[i] > 0)cout<<W2[i]<<endl;}
    //cout<<"___Answer:"<<endl;
    cout << A << endl;
    //system("pause");  
}
int ser(long int *y, int A)
{
    int g = 0;
    for(int i = 0; i < N; ++i){if(y[i]>0 && g<y[i] && y[i]<A)g = y[i];}
    return g;
}
int rec()
{
    while (b > 0)
    {
        a_buf1 = 0;
        a_buf2 = 0;
        for(int i = 0; i < N; ++i) {if(W1[i] > 0) a_buf1 += W1[i];}
        for(int i = 0; i < N; ++i) {if(W2[i] > 0) a_buf2 += W2[i];}
        if (a_buf1 > a_buf2)
        {
            A = a_buf1 - a_buf2; // A - начальная разность веса куч
            for(int i = 0; i < N && (i2==0); ++i)
            {
                if (W1[i] == ser(W1, A)&&W1[i]!=0)
                {
                    i2 = 0;
                    buf = W1[i];
                    W1[i] = -1;
                    while ((W2[i2] > 0) && (i2 < N)) i2++;
                    W2[i2] = buf;
                    //cout<<"Perestanovka1"<<endl;
                    rec();
                }
            }
        }
        else if (a_buf2 > a_buf1)
        {
            A = a_buf2 - a_buf1; // A - начальная разность веса куч
            for(int i = 0; i < N && (i1==0); ++i)
            {
                if (W2[i] == ser(W2, A)&&W2[i]!=0)
                {
                    i1 = 0;
                    buf = W2[i];
                    W2[i] = -1;
                    while ((W1[i1] > 0) && (i1 < N)) i1++;
                    W1[i1] = buf;
                    //cout<<"Perestanovka2"<<endl;
                    rec();
                }
            }
        }
        else
        {
            A = 0;
            break;
        }
        --b;
    }
    return A;
}
 
Текущее время: 00:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru