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

Несоставляемое число - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
06.04.2009, 20:30     Несоставляемое число #1
Подскажите решение плииз....
Дано N натуральных чисел. Требуется найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза.

Входные данные
Входной файл INPUT.TXT в первой строке содержит натуральное число N, не превосходящее 104, далее следуют N строк, в каждой из которых записано по одному натуральному числу, каждое из которых не превосходит 109.

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры
№ INPUT.TXT OUTPUT.TXT
1 4
1
1
1
5 4

2 4
1
2
4
8 16

Добавлено через 2 часа 46 минут 10 секунд
Плиииз помогите мне... Мне к экзамену на этой неделе нужно....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2009, 20:30     Несоставляемое число
Посмотрите здесь:

Программа задумывает число от 1 до 10, и предлагает пользователю отгадать число за 5 попыток C++
Задача число и число записанное в обратном направлении сумма целого числа C++
C++ Разработать функцию f(x), которая нечётное число заменяет на 0, а чётное число уменьшает в 2 раза
C++ Ввести число с клавиатуры, потом записать это число в текстовой файл
Как из 4-х байт, составляющих число типа double, получить это число? C++
Вводится число от 1 до 15. Вывести данное число, записанное римскими цифрами C++
C++ Не получается исправить ошибку (Вводится диапазон, где 1-ое число-начало диапазона, 2-ое число приращени, 3-е число конец диапазона)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.04.2009, 21:21     Несоставляемое число #2
Работу с файлами думаю сам добавишь
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
 
int main()
{
    std::vector<int> vec(104);
    std::vector<int>::iterator veciter;
 
    srand( (unsigned)time( NULL ) );
 
    for(veciter=vec.begin();veciter!=vec.end();veciter++)
        std::cout<<(*veciter=rand()%109)<<' ';
    sort(vec.begin(),vec.end());
 
    int value=1;
    for(veciter=vec.begin();veciter!=vec.end();veciter++)
    {
        if(value>=*veciter)
            value+=*veciter;
        else
            break;
    }
 
    std::cout<<"\nResult: "<<value<<'\n';
    return 0;
}
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
06.04.2009, 21:36  [ТС]     Несоставляемое число #3
СПС.... Уже сделал!!!!
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 <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        int a[104],i=0,n,v=1;
        scanf ("%i",&n);
        for (i=0; i<n; i++){
            scanf ("%i",&a[i]);
            }
        sort(a,a+n-1);
        for(i=0; i<n; i++)
        {
                if(v>=a[i])
                        v+=a[i];
                else
                        break;
        }
        printf ("%i",v);
        return 0;
}
Добавлено через 3 минуты 39 секунд
Ну что же это такое ошибку выдает, на тестах....
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.04.2009, 21:48     Несоставляемое число #4
Какую именно?
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
06.04.2009, 21:59  [ТС]     Несоставляемое число #5
Цитата Сообщение от Humanitis Посмотреть сообщение
Какую именно?
Я тут твою переделал на си отправил учителю, говорит алгоритм не на 100%, проходит примерно 30-35% тестов...Вот так вот...
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.04.2009, 22:10     Несоставляемое число #6
Наверное wrong answer пишет
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
06.04.2009, 22:11  [ТС]     Несоставляемое число #7
Да
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.04.2009, 22:13     Несоставляемое число #8
Ну давай ссылку,на какой spoj отправляешь
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
06.04.2009, 22:14  [ТС]     Несоставляемое число #9
Цитата Сообщение от Humanitis Посмотреть сообщение
Ну давай ссылку,на какой spoj отправляешь
не понял...
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.04.2009, 22:17     Несоставляемое число #10
Ты задание тестишь на каком-то сайте?
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
06.04.2009, 22:18  [ТС]     Несоставляемое число #11
Цитата Сообщение от Humanitis Посмотреть сообщение
Ты задание тестишь на каком-то сайте?
http://********/index.asp?main=task&id_task=427
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.04.2009, 22:23     Несоставляемое число #12
Новенький, так ты задание правильно переписывай,там не 104 и 109,а 10**4 и 10**9.
Измени в задании тип int на unsigned long int и размер массива с 104 до 10000
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
06.04.2009, 22:38  [ТС]     Несоставляемое число #13
Цитата Сообщение от Humanitis Посмотреть сообщение
Новенький, так ты задание правильно переписывай,там не 104 и 109,а 10**4 и 10**9.
Измени в задании тип int на unsigned long int и размер массива с 104 до 10000
без разницы опять WA......

Добавлено через 12 минут 5 секунд
Humanitis, ты можешь мне свою почту скинуть... ну если те сложно... вдруг если у меня какие нибудь вопросы будут у тебя спрошу....
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
06.04.2009, 22:41     Несоставляемое число #14
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
 
 
int main()
{
    std::vector<unsigned long long int>::iterator veciter;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    unsigned int size;
    std::cin>>size;
    std::vector<unsigned long long int> vec(size);
 
    for(veciter=vec.begin();veciter!=vec.end();veciter++)
        std::cin>>*veciter;
    sort(vec.begin(),vec.end());
 
    unsigned long long int value=1;
    for(veciter=vec.begin();veciter!=vec.end();veciter++)
    {
        if(value>=*veciter)
            value+=*veciter;
        else
            break;
    }
 
    std::cout<<value;
    return 0;
}
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
07.04.2009, 16:30  [ТС]     Несоставляемое число #15
И все таки не проходит....
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
07.04.2009, 16:39     Несоставляемое число #16
У меня этот листинг на том сайте прошел тестирование прекрасно.
Ты что-то не так делаешь
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
07.04.2009, 16:40  [ТС]     Несоставляемое число #17
ну вот.... в чем проблема....
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 <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
        unsigned long long int a[10000],i=0,n,v=1;
        cin>>n;
        for (i=0; i<n; i++){
            cin>>a[i];
            }
        sort(a,a+n-1);
        for(i=0; i<n; i++)
        {
                if(v>=a[i])
                        v+=a[i];
                else
                        break;
        }
        cout<<v;
        return 0;
}
Humanitis
 Аватар для Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
07.04.2009, 16:48     Несоставляемое число #18
Видимо в том,что последний элемент тоже нужно сортировать
C++
1
sort(a,a+n);//вместо sort(a,a+n-1);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2009, 16:53     Несоставляемое число
Еще ссылки по теме:

Напечатать таблицу умножения на заданное число (число вводится с клавиатуры) C++
C++ Ввести число n, разбить число на цифры, и найти сумму этих цифр
Функция определяющая что общее число книг есть шестизначное число C++
C++ Дано натуральное число N. Получите новое число, перевернув его

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

Или воспользуйтесь поиском по форуму:
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
07.04.2009, 16:53  [ТС]     Несоставляемое число #19
Если время есть помоги эту задачу тоже .... http://www.cyberforum.ru/cpp-beginne...tml#post132975
Yandex
Объявления
07.04.2009, 16:53     Несоставляемое число
Ответ Создать тему
Опции темы

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