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

Какой момент не учитывает программа? - C++

Восстановить пароль Регистрация
 
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 14:53     Какой момент не учитывает программа? #1
Здравствуйте.

Задача - http://acm.timus.ru/problem.aspx?space=1&num=1025
Не могу успокоиться, пока не решу задачу. Уже были перепробованы, пожалуй, все варианты, оговорённые в задании , программа выдаёт правильный ответ,но тест задача всё ещё не проходит. Т.е. при определённых входящих цифрах, ответ не правильный. Но, по сути, всё же правильно... Или я что-то пропускаю.
На всякий случай:
Код
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 "stdafx.h"
#include "conio.h"
 
int max_people(int x){
    /*int max = x/2;
    if(x%2!=0)
        ++max;
    return max;*/
    if(x>0)
        return x/2+1;
    else return 0;
}
class Sort{
    int LAST[100],empty_peoples_left,max_index;
    void new_max_index(){
        int J=2;
        max_index=1;
        while(LAST[J]!=-1){
            if(LAST[J]>max_index)
                max_index=J;
            J++;
        }
    }
    void makelast(int x){
        if(LAST[max_index]>x){
            LAST[max_index]=x;
            new_max_index();
        }
    }
public:
    Sort(int a){
        empty_peoples_left=a;
        LAST[empty_peoples_left+1]=-1;
        max_index=1;
    }
    void ADD(int x){        
        if(empty_peoples_left!=0){
            LAST[empty_peoples_left]=x; 
            if(LAST[empty_peoples_left]>LAST[max_index])
                max_index=empty_peoples_left;
            --empty_peoples_left;   
        }
        else
            makelast(x);
    }
    int Get_Answer(){
        int answer=0,i=1;;
        while(LAST[i]!=-1){
            answer+=LAST[i];
            ++i;
        }
        return answer;
    }
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int K,var[101],c_max=0;
    scanf_s("%d",&K);
    Sort sort(max_people(K));
    for(int i=1; i<=K; ++i)
        scanf_s("%d",&var[i]);
    for(int i=1; i<=K; ++i){
        c_max+=var[i];
        sort.ADD(max_people(var[i]));
    }
    if(c_max<=9999)
        printf("%i",sort.Get_Answer());
    else printf("0");
    _getch();
}

p.s. Не знаю, правильно ли спрашивать здесь, но, может, получить бы хотя бы намёк на то, что мою было упущено. Ну как так, всё же правильно...
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 15:54     Какой момент не учитывает программа? #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
может просто при каких то исходных данных программа Вычисляет слишком долго? или вообще зависает

Добавлено через 3 минуты
C++
1
2
empty_peoples_left=a;
        LAST[empty_peoples_left+1]=-1;
LAST имеет 100 элементов, следовательно максимально допустимый индекс 99

C++
1
Sort sort(max_people(K));
тут в sort может передаваться число больше 99

Добавлено через 18 минут
ловите
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
#include<iostream>
#include <algorithm>
 
using namespace std;
 
bool myfunction (int& i,int& j) { return (i<j); }
 
int half(int &x)
{
return x/2+1;
}
 
int main(int argc, char*argv[])
{
int k;
cin >> k;
int * a = NULL;
a = new int[k];
for(int i = 0; i < k; i++)
{
cin >> a[i];
}
sort(a,a+k,myfunction);
int h = half(k);
int answere = 0;
for(int i = 0; i < h; i++)
{
answere +=half(a[i]);
}
cout<< answere;
delete[]a;
return 0;
}
Результат проверки: Accepted
Время работы: 0.015
Выделено памяти: 224Кб
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 15:56  [ТС]     Какой момент не учитывает программа? #3
Кстати да.
ставлю LAST[110]
Но, всё равно не помогло, компилятор же в обоих случаях одинаково считал.
Тут что-то другое...

Добавлено через 57 секунд
Ну ну ну ну не!
Так же не честно.
Но всё равно спасибо. Посмотрю, сравню что у меня не так было.
p.s. a = new int[k]; - какая полезная штука) Вот за неё спасибо)))))
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 15:59     Какой момент не учитывает программа? #4
Цитата Сообщение от Jer Посмотреть сообщение
Ну ну ну ну не!
Так же не честно.
не удержался сори, забудьте что написано выще
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 16:10  [ТС]     Какой момент не учитывает программа? #5
Уже не развидеть увиденное)
Судя по всему, у меня в каких-то редких случаях уходит по массиву не туда, а у вас там чётко границы, и такого не происходит.. Пойду поищу где.
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 16:11     Какой момент не учитывает программа? #6
C++
1
2
3
4
5
while(LAST[J]!=-1){
            if(LAST[J]>max_index)
                max_index=J;
            J++;
        }
потенциально бесконечный...
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 16:25  [ТС]     Какой момент не учитывает программа? #7
aLarman, А почему бесконечное? У нас же обязательно в LAST[] есть значение -1;
Или вы имеете ввиду что если K будет равно где-нибудь ~ 140 000, то в int не залезет и будет не то что мы хотели и т.д. ?
Мне казалось, раз там стоит ограничение (1<=K<=101), то других цифр и не будет при проверке.
Похоже, проще переписать весь код по-нормальному.Хотя уже есть такой. Но только надо свой, а то нечестно)
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 16:41     Какой момент не учитывает программа? #8
ну можете сами написать сортировку а не юзать стандартную
я думаю тут важнее понять решение задачи математическое, потому что не поняв "математики" можно "поехать в москву через америку"
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 17:08  [ТС]     Какой момент не учитывает программа? #9
Да вроде как раз математика и понятна.

Добавлено через 6 минут
даже с ограничениями не работает)
Кликните здесь для просмотра всего текста
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
int max_people(int x){
    /*int max = x/2;
    if(x%2!=0)
        ++max;
    return max;*/
    if(x>0)
        return x/2+1;
    else return 0;
}
class Sort{
    int LAST[110],empty_peoples_left,max_index;
    void new_max_index(){
        int J=2;
        max_index=1;
        while(LAST[J]!=-1){
            if(LAST[J]>max_index)
                max_index=J;
            J++;
        }
    }
    void makelast(int x){
        if(LAST[max_index]>x){
            LAST[max_index]=x;
            new_max_index();
        }
    }
public:
    Sort(int a){
        empty_peoples_left=a;
        LAST[empty_peoples_left+1]=-1;
        max_index=1;
    }
    void ADD(int x){        
        if(empty_peoples_left!=0){
            LAST[empty_peoples_left]=x; 
            if(LAST[empty_peoples_left]>LAST[max_index])
                max_index=empty_peoples_left;
            --empty_peoples_left;   
        }
        else
            makelast(x);
    }
    int Get_Answer(){
        int answer=0,i=1;;
        while(LAST[i]!=-1){
            answer+=LAST[i];
            ++i;
        }
        return answer;
    }
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int K,var[102],c_max=0;
    bool error=0;
    scanf_s("%d",&K);
    if(K<=102 && K>=0){
        Sort sort(max_people(K));
        for(int i=1; i<=K; ++i)
            var[i]=9999;
    //       scanf_s("%d",&var[i]);
        for(int i=1; i<=K; ++i){
            c_max+=var[i];
            sort.ADD(max_people(var[i]));
        }
        if(c_max<=9999)
            printf("%i",sort.Get_Answer());
        else printf("0");
    }
    else printf("0");
    _getch();
}
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 17:09     Какой момент не учитывает программа? #10
Цитата Сообщение от Jer Посмотреть сообщение
Да вроде как раз математика и понятна.
ну я слушаю
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 17:18  [ТС]     Какой момент не учитывает программа? #11
aLarman,
Что слушаете?)
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 17:21     Какой момент не учитывает программа? #12
Цитата Сообщение от Jer Посмотреть сообщение
Да вроде как раз математика и понятна.
расскажите, что Вам понятно)
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 17:24  [ТС]     Какой момент не учитывает программа? #13
если вы про математику, то:
1. берём макс. кол-во групп
2. сортируем по возрастанию
3. складываем макс. кол-во людей из каждой группы, пока кол-во групп не дойдёт до макс. кол-ва.
Да и у меня считает правильно... Почти.
Но интересно же найти ошибку...
aLarman
636 / 557 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 20:08     Какой момент не учитывает программа? #14
1 берем группы
2) сортируем их в порядке возрастания
3) берем первую половину групп (а точнее на одну больше половины что бы "за" выиграло)
4) делаем что бы каждая из этих групп выиграла (в каждой из них, больше половину проголосовало "за")
5) суммируем это
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 20:37  [ТС]     Какой момент не учитывает программа? #15
aLarman, Да. Это и имею ввиду. Я просто мысли в слова плохо переделываю.
Да новый код написать это не сложно. ( тем более, уже 100 процентов зная как лучше)
Интересно, что не так в старом. Какой вариант входящих цифр ни придумаю - всё правильно решает, как надо. А видно, не всё.
Ещё есть вариант посмотреть на этот код через год или два, и понятно будет, что всё-таки там не так.
Пойду напишу новый что-ли
aLarman
24.03.2014, 21:08
  #16

Не по теме:

честно, мне не хочется Ваш код разбирать детально

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2014, 12:49     Какой момент не учитывает программа?
Еще ссылки по теме:

Программа проверяет, содержится ли какой-либо предлог из массива в данной строчке C++
C++ Программа не останавливается в нужный момент
В какой момент вызывается конструктор для глобального объекта, использующего статическое выделение памяти? C++

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

Или воспользуйтесь поиском по форуму:
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
25.03.2014, 12:49  [ТС]     Какой момент не учитывает программа? #17
aLarman, Да не. Не надо ничего разбирать.
Я же просто говорю что мне было бы интересно потом узнать может быть.
Вы то мне и так здорово помогли, спасибо Вам!
Yandex
Объявления
25.03.2014, 12:49     Какой момент не учитывает программа?
Ответ Создать тему
Опции темы

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