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

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

Войти
Регистрация
Восстановить пароль
 
 
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
#1

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

24.03.2014, 14:53. Просмотров 385. Ответов 16
Метки нет (Все метки)

Здравствуйте.

Задача - 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. Не знаю, правильно ли спрашивать здесь, но, может, получить бы хотя бы намёк на то, что мою было упущено. Ну как так, всё же правильно...
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2014, 14:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Какой момент не учитывает программа? (C++):

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

Программа не останавливается в нужный момент - C++
Программа должна выводить близнецов не выше числа n*2, но она это делает. Вот условие, если кому то нужно: &quot;Дано натуральное число n....

Не учитывает дробные числа - C++
Помогите исправить программу, чтобы она учитывала ввод дробных чисел... #include &lt;cstdio&gt; #include &lt;iostream&gt; using namespace std;...

Наследование классов: почему производный класс не учитывает данные, введенные в базовом? - C++
Почему при компилляции производный класс не учитывает данные, введенные в базовом? #include &lt;iostream&gt; using namespace std; ...

Можно ли создать класс, который при вызове деструктора учитывает количество ссылок на него - C++
Короче можно ли сделать класс как в C# или java, чтобы объект удолялся только когда на него никто не ссылается. Желательно варианты без...

Когда запускаю и ввожу параметры, то, в момент когда программа должна выполнять действие, пишет ошибку - C++
Недавно начали изучать c++. так как в школе не было программирования (преподу пофиг было) я в универе отстаю ;c Написал программу по...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
aLarman
642 / 563 / 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Кб
0
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 15:56  [ТС] #3
Кстати да.
ставлю LAST[110]
Но, всё равно не помогло, компилятор же в обоих случаях одинаково считал.
Тут что-то другое...

Добавлено через 57 секунд
Ну ну ну ну не!
Так же не честно.
Но всё равно спасибо. Посмотрю, сравню что у меня не так было.
p.s. a = new int[k]; - какая полезная штука) Вот за неё спасибо)))))
0
aLarman
642 / 563 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 15:59 #4
Цитата Сообщение от Jer Посмотреть сообщение
Ну ну ну ну не!
Так же не честно.
не удержался сори, забудьте что написано выще
0
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 16:10  [ТС] #5
Уже не развидеть увиденное)
Судя по всему, у меня в каких-то редких случаях уходит по массиву не туда, а у вас там чётко границы, и такого не происходит.. Пойду поищу где.
0
aLarman
642 / 563 / 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++;
        }
потенциально бесконечный...
0
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 16:25  [ТС] #7
aLarman, А почему бесконечное? У нас же обязательно в LAST[] есть значение -1;
Или вы имеете ввиду что если K будет равно где-нибудь ~ 140 000, то в int не залезет и будет не то что мы хотели и т.д. ?
Мне казалось, раз там стоит ограничение (1<=K<=101), то других цифр и не будет при проверке.
Похоже, проще переписать весь код по-нормальному.Хотя уже есть такой. Но только надо свой, а то нечестно)
0
aLarman
642 / 563 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 16:41 #8
ну можете сами написать сортировку а не юзать стандартную
я думаю тут важнее понять решение задачи математическое, потому что не поняв "математики" можно "поехать в москву через америку"
0
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();
}
0
aLarman
642 / 563 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 17:09 #10
Цитата Сообщение от Jer Посмотреть сообщение
Да вроде как раз математика и понятна.
ну я слушаю
0
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 17:18  [ТС] #11
aLarman,
Что слушаете?)
0
aLarman
642 / 563 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 17:21 #12
Цитата Сообщение от Jer Посмотреть сообщение
Да вроде как раз математика и понятна.
расскажите, что Вам понятно)
0
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 17:24  [ТС] #13
если вы про математику, то:
1. берём макс. кол-во групп
2. сортируем по возрастанию
3. складываем макс. кол-во людей из каждой группы, пока кол-во групп не дойдёт до макс. кол-ва.
Да и у меня считает правильно... Почти.
Но интересно же найти ошибку...
0
aLarman
642 / 563 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
24.03.2014, 20:08 #14
1 берем группы
2) сортируем их в порядке возрастания
3) берем первую половину групп (а точнее на одну больше половины что бы "за" выиграло)
4) делаем что бы каждая из этих групп выиграла (в каждой из них, больше половину проголосовало "за")
5) суммируем это
0
Jer
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
24.03.2014, 20:37  [ТС] #15
aLarman, Да. Это и имею ввиду. Я просто мысли в слова плохо переделываю.
Да новый код написать это не сложно. ( тем более, уже 100 процентов зная как лучше)
Интересно, что не так в старом. Какой вариант входящих цифр ни придумаю - всё правильно решает, как надо. А видно, не всё.
Ещё есть вариант посмотреть на этот код через год или два, и понятно будет, что всё-таки там не так.
Пойду напишу новый что-ли
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2014, 20:37
Привет! Вот еще темы с ответами:

Программа считает бред какой-то - C++
#include &lt;stdio.h&gt; int main() { int t,y,v,x,n=0; scanf(&quot;%d %d&quot;, &amp;x, &amp;y); while (x&lt;y) {...

Как узнать в какой ОС запускается программа? - C++
Как узнать в какой ОС запускается программа? И уже дальше делать то или иное в зависимости от ОС.

В какой среде была написана программа - C++
Добрый вечер. Заранее прошу прощения,если вопрос будет задан некорректно. Я только начинаю погружаться в мир программирования)) А можно...

Программа проверяет, содержится ли какой-либо предлог из массива в данной строчке - C++
Дан массив с предлогами : in, and, is, a, an, or и дана пустая строчка char str, Пользователь вводит предложение, к примеру: Hello, my...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.03.2014, 20:37
Ответ Создать тему
Опции темы

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