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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.72
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
#1

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

24.09.2011, 00:44. Просмотров 5847. Ответов 18
Метки нет (Все метки)

Собственно условие: http://acm.timus.ru/problem.aspx?space=1&num=1005
Моё решение:
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
#include <iostream>
using namespace std;
void main() 
{
    long int N = 0, A = 0, *W, *W1, *W2, a_buf1 = 0, a_buf2 = 0, buff = 0;
    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 i = buff, j = 0; i < N; ++i, ++j)
    {
        W2[j] = W[i];
    }
    int b = N, i1 = 0, i2 = 0, buf = 0, buf2 = 0;
    while (b > 0)
    {
        a_buf1 = 0;
        a_buf2 = 0;
        for(int i = 0; i < N; ++i) {if((W1[i] != -1) && (W1[i]))a_buf1 += W1[i];}
        for(int i = 0; i < N; ++i) {if((W2[i] != -1) && (W2[i]))a_buf2 += W2[i];}
        if (a_buf1 > a_buf2)
        {
            A = a_buf1 - a_buf2;
            for(int i = 0; W1[i] != 0; ++i)
            {
                if ((W1[i] < A) && W1[i] != -1)
                {
                    i2 = 0;
                    buf = W1[i];
                    W1[i] = -1;
                    while ((W2[i2] != 0) && (i2 < N)){i2++;}
                    W2[i2] = buf;
                    A = buf;
                }
            }
        }
        else if (a_buf1 < a_buf2)
        {
            A = a_buf2 - a_buf1;
            for(int i = 0; W2[i] != 0; ++i) 
            {
                if ((W2[i] < A) && W2[i] != -1)
                {
                    i1 = 0;
                    buf = W2[i];
                    W2[i] = -1;
                    while ((W1[i1] != 0) && (i1 < N)){i1++;}
                    W1[i1] = buf;
                    A = buf;
                }
            }
        }
        else
        {
            A = 0;
            break;
        }
        --b;
    }
    cout << A << endl;  
}
Проблема в том, что не взирая на получаемый правильный результат он-лайн проверка выдаёт Wrong answer.
В чём моя ошибка? Или это их глюк?(и то и то на мой взгляд равновероятно)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2011, 00:44     Простенькая задачка из Timus Online Judge(1005. Куча камней)
Посмотрите здесь:

C++ Простенькая задачка
простенькая задачка в среде программирования dev-cpp C++
Простенькая Задачка C++
Задача 1001 acm.timus.ru C++
C++ простенькая задачка
Задача Timus C++
Небольшая задачка. простенькая C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
24.09.2011, 00:52     Простенькая задачка из Timus Online Judge(1005. Куча камней) #2
Цитата Сообщение от Whiteha Посмотреть сообщение
В чём моя ошибка?
наверное в этом
Ограничение времени: 2.0 секунды
Ограничение памяти: 16 МБ

Добавлено через 3 минуты
не знаю какой компилятор это ест.
C++
1
W[i] = W1[i] = W2[i] = 0;
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
24.09.2011, 00:55  [ТС]     Простенькая задачка из Timus Online Judge(1005. Куча камней) #3
Нет, не в этом)
Тогда бы было сообщение не о неправильном ответе, а соответственно о нехватке отведённого времени или памяти. Тут это даже близко не стоит.)
P.S. Знаю что написано размашисто, буду признателен за более простые решения.


Добавлено через 3 минуты
не знаю какой компилятор это ест.
C++
1
W[i] = W1[i] = W2[i] = 0;
Любой) Тут ничего незаконного нет.
Jupiter
Каратель
Эксперт C++
6548 / 3968 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
24.09.2011, 01:04     Простенькая задачка из Timus Online Judge(1005. Куча камней) #4
Цитата Сообщение от Whiteha Посмотреть сообщение
W = new long int[N];
W1 = new long int[N];
W2 = new long int[N];
вот это жрет время, создайте статический массив на 20 камней
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
24.09.2011, 01:07     Простенькая задачка из Timus Online Judge(1005. Куча камней) #5
Цитата Сообщение от Whiteha Посмотреть сообщение
Любой) Тут ничего незаконного нет.
да, и вправду. даже нулями забил, но я все равно так не буду писать
понятно, все дело в польской записи
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
24.09.2011, 01:17  [ТС]     Простенькая задачка из Timus Online Judge(1005. Куча камней) #6
Хорошо хоть индусом не назвали
Хотя я пока и недалеко ушёл.
Насчёт времени повторюсь - исполняется всё за 0.031 с, памяти ест всего 192 КБ.
Дело не в этом!
Ихний компилятор пишет - неправильный Ответ.
А почему - я не знаю, у меня всё правильно считает.(
grizlik78
Эксперт С++
 Аватар для grizlik78
1892 / 1424 / 105
Регистрация: 29.05.2011
Сообщений: 2,980
24.09.2011, 01:21     Простенькая задачка из Timus Online Judge(1005. Куча камней) #7
Цитата Сообщение от Whiteha Посмотреть сообщение
А почему - я не знаю, у меня всё правильно считает.(
Правильно, говоришь?
А что она выдаёт для такого теста?
4
1 2 6 5
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
24.09.2011, 01:54  [ТС]     Простенькая задачка из Timus Online Judge(1005. Куча камней) #8
Мда, спасибо за наводку, осталось понять где утечка...
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.09.2011, 08:11     Простенькая задачка из Timus Online Judge(1005. Куча камней) #9
Я свой быдлоперебор с acmp переделал под тимус, прошел все тесты за 0.078 =)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdlib> //for abs
 
int q[24], w[24], n, s, i, x, m = 1e9;
 
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;
}
Хотя динамикой она красивее решается...
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
24.09.2011, 16:33  [ТС]     Простенькая задачка из Timus Online Judge(1005. Куча камней) #10
Я просёк свои ошибки, наставил костылей... и проблема пришла откуда не ждали - мой алгоритм г**но, работающее лишь в частных случаях.(
Объясните пожалуйста алгоритм для решения этой задачи!
Моя идея была такова:
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;
}
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.09.2011, 16:38     Простенькая задачка из Timus Online Judge(1005. Куча камней) #11
Цитата Сообщение от 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;
}
Whiteha
Программист
33 / 33 / 4
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
26.09.2011, 22:38  [ТС]     Простенькая задачка из Timus Online Judge(1005. Куча камней) #12
diagon, ещё раз большое спасибо! Правда хотелось бы узнать ещё две вещи для расширения кругозора - перебор это единственный вариант? И вариант с "динамикой рюкзаком" любопытно, это как?=)
Jupiter
Каратель
Эксперт C++
6548 / 3968 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.09.2011, 22:53     Простенькая задачка из Timus Online Judge(1005. Куча камней) #13
Цитата Сообщение от Whiteha Посмотреть сообщение
И вариант с "динамикой рюкзаком" любопытно, это как?=)
гуглите "задачу о ранце"
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.09.2011, 12:35     Простенькая задачка из Timus Online Judge(1005. Куча камней) #14
Цитата Сообщение от Whiteha Посмотреть сообщение
diagon, ещё раз большое спасибо! Правда хотелось бы узнать ещё две вещи для расширения кругозора - перебор это единственный вариант? И вариант с "динамикой рюкзаком" любопытно, это как?=)
Не единственный, рюкзаком за O(n * m) решается.
Тут про рюкзак хорошо написано.
baurgun
Сообщений: n/a
22.06.2012, 19:52     Простенькая задачка из Timus Online Judge(1005. Куча камней) #15
Вот мой код решения этой задачи
На Тимусе выдает неправильный ответ на 5 тесте. Сколько не прогонял считает все правильно, может тест подскажите какой?)
Алгоритм такой: функция max - ищет максимальный и зануляет его. в одну кучу кладем максимальный элемент, и во вторую также (тоесть следущий по максимальности). Если вес второй кучи больше первой, то добавляем максимальный в первую, иначе во вторую. Если же вес куч равен, то кладем в первую.


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
#include <stdio.h>
#include <new>
 
unsigned int n;
 
int max (int p[])
{int j,h=0,m=0;
    for(j=0;j<n;j++)
    {if(p[j]>=m) {m=p[j];h=j;}}
p[h]=0;
return m;}
 
 
void c(int **mass, unsigned int len)
{
    *mass = new int[len];
}
 
int main()
{unsigned int k1,k2,i,y;int l,*p,q;
        
scanf("%u",&n);
if( n<1 || n>20) return 0;
c(&p,n);
    
for( i=0;i<n;i++)
{scanf("%u",&p[i]); 
if (p[i]<1 || p[i]>100000) return 0;}
 
k2=max(p);
k1=max(p);
 
//printf("%d %d",k2,k1);}
 
for(y=1;y<=n-1;y++) 
{if(k2>=k1)
k1=k1+max(p);
else k2=k2+max(p);
 
}
q=k2-k1;
if(q<0) l=-q;
else l=q;
 
printf("%d",l);
 
delete[] p;return 0;
 
}
Nurik
3 / 3 / 0
Регистрация: 17.04.2012
Сообщений: 25
07.07.2012, 16:54     Простенькая задачка из Timus Online Judge(1005. Куча камней) #16
Этот тест у вас неправильный!
6
1 4 5 6 7 9
Почему 2?
9+7=16 и 1+4+5+6=16

Добавлено через 1 минуту
Этот тест у вас неправильный!
6
1 4 5 6 7 9
Почему 2?
9+7=16 и 1+4+5+6=16
Akaviri
Сообщений: n/a
17.04.2013, 17:05     Простенькая задачка из Timus Online Judge(1005. Куча камней) #17
Никак не могу понять где ошибка. Ответ неправильный на 7 тесте.
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
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
    int n;
    cin >> n;
    int w[n];
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        std::cin >> w[i];
        sum += w[i];
    }
    std::sort(w, w + n, greater<int>());
    int first = 0;
    for(int i = 0; i < n; i++)
    {
        if(first + w[i] <= sum / 2)
            first += w[i];
    }
    std::cout << sum - 2 * first << std::endl;
}
ВВП
Сообщений: n/a
03.05.2013, 16:40     Простенькая задачка из Timus Online Judge(1005. Куча камней) #18
Фишка в том, что необходимо сделать перебор 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
 
        }
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2015, 23:49     Простенькая задачка из Timus Online Judge(1005. Куча камней)
Еще ссылки по теме:

Напишите свой вариант решения, простенькая задачка C++
Подгонка решения задачи под тесты Timus Online Judge, С++ C++
Задача на Timus Online Judge, C++. Решена, но C++
Acm.timus Wrong answer C++
Acm.timus Wrong answer C++

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

Или воспользуйтесь поиском по форуму:
RomanAndreich
0 / 0 / 0
Регистрация: 20.12.2015
Сообщений: 1
21.12.2015, 23:49     Простенькая задачка из Timus Online Judge(1005. Куча камней) #19
Абсолютно нечитаемый код =) К сожалению.
Yandex
Объявления
21.12.2015, 23:49     Простенькая задачка из Timus Online Judge(1005. Куча камней)
Ответ Создать тему
Опции темы

Текущее время: 04:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru