Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
1

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

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

Author24 — интернет-сервис помощи студентам
Здравствуйте.

Задача - 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.03.2014, 14:53
Ответы с готовыми решениями:

В какой момент уничтожится объект?
есть функция function Tdm.GetTypeList: TStringList; var AdoSet : TADOQuery; begin AdoSet...

В какой момент вывести лог
Всем привет. Начинаю изучать js и практически сразу встрял на одном моменте. server.js var http =...

В какой момент вода вытечет полностью?
У дна бака расположен кран. Когда кран открыли, вода начала вытекать, высота столба меняется по...

В какой момент лучше заняться SEO?
уважаемые ALL! Я задумываю интернет проект. Работы, связанные с этим буду раздавать подрядчикам, в...

16
654 / 575 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
24.03.2014, 15:54 2
Лучший ответ Сообщение было отмечено Jer как решение

Решение

может просто при каких то исходных данных программа Вычисляет слишком долго? или вообще зависает

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

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

Не по теме:

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

0
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 28
25.03.2014, 12:49  [ТС] 17
aLarman, Да не. Не надо ничего разбирать.
Я же просто говорю что мне было бы интересно потом узнать может быть.
Вы то мне и так здорово помогли, спасибо Вам!
0
25.03.2014, 12:49
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.03.2014, 12:49
Помогаю со студенческими работами здесь

В какой момент Проведение запоминает данные?
Добрый день Подскажите в какой момент (Процедуре) проведение запоминает данные ? у меня есть...

В какой момент срабатывает ограничение CHECK?
Есть функция CheckValue(Num,Name), которая возвращает 1 в случае наличия совокупности Номера и...

В какой момент вызывается сигнал readyRead()
в какой момент вызывается сигнал readyRead() ?? Добавлено через 48 секунд если пришел новый...

В какой момент времени лучше всего подключаться к БД?
Добрый день! Пишу небольшую прикладную программку для одного пользователя, которая в том числе...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru