1 / 1 / 1
Регистрация: 12.01.2017
Сообщений: 19
1

Выведите максимальное число покемонов, которых Баш может взять

12.01.2017, 18:36. Показов 1539. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Баш отправился в путешествие, чтобы стать величайшим мастером Покемонов. Чтобы получить первого покемона, он отправился в лабораторию профессора Зулу. Поскольку Баш — любимый студент профессора, Зулу разрешил ему взять столько покемонов из лаборатории, сколько Баш захочет.

Однако, профессор предупрел Баша, что группа из k > 1 покемонов с силами {s1, s2, s3, ..., sk} склонна к драке между собой, если gcd(s1, s2, s3, ..., sk) = 1 (смотрите примечания для определения gcd).

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

Обратите внимание: Один покемон не может драться сам с собой.

Входные данные
Входные данные находятся в двух строках.

Первая строка содержит целое число n (1 ≤ n ≤ 105) — число покемонов в лаборатории профессора.

Следующая строка содержит n целых чисел, где i-е из них равно si (1 ≤ si ≤ 105) — силе i-го покемона.

Выходные данные
Выведите одно число — максимальное число покемонов, которых Баш может взять.

Примеры
входные данные
3
2 3 4
выходные данные
2
входные данные
5
2 3 4 6 7
выходные данные
3
Примечание
gcd (наибольший общий делитель) множества натуральных чисел {a1, a2, ..., an} равняется наибольшему натуральному числу, на которое делятся все числа {a1, a2, ..., an}.

В первом примере Баш может взять покемонов с силами {2, 4}, потому что gcd(2, 4) = 2.

Во втором примере Баш может взять покемонов с силами {2, 4, 6}, и не существует группы больше с gcd ≠ 1.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.01.2017, 18:36
Ответы с готовыми решениями:

Какое максимальное количество конфет он может взять
Степан очень любит конфеты. Сегодня он идет на свидание и хочет угостить девушку конфетами. Степан...

Выведите одно целое число — максимальное число, которое могло получиться в протоколе при игре на данном поле
У Пети имеется игровое поле размером 3×3 , заполненное числами от 1 до 9. В начале игры он может...

Выведите одно целое число — максимальное число, которое могло получиться в протоколе при игре на данном поле
У пети имеется игровое поле размером 3х3, заполненное числами от 1 до 9. В начале игры он может...

Найти максимальное количество монет, которые может взять вождь
Ребят, пожалуйста, помогите доработать код, а. Не проходит на 9 тесте (думаю, все поняли, на каком...

2
Эксперт С++
1624 / 954 / 782
Регистрация: 06.02.2016
Сообщений: 2,452
Записей в блоге: 31
12.01.2017, 20:34 2
Лучший ответ Сообщение было отмечено Tadeem как решение

Решение

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
#include <iostream>
#include <cmath>
#include <set>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
int gcd (int a, int b) {
    if (b == 0) {
        if (a == 0)
            return -1;
        else return a;
    } else abs(gcd(b, a % b));
}
int gcd(multiset<int>&s) {
    int k=*s.begin();
    set<int>::iterator it=++s.begin();
    for (set<int>::iterator iter=it; iter!=s.end(); iter++) {
        k = gcd(k, *iter);
    }
    return k;
}
int main() {
    vector<int>v {};
    multiset<int>s {0};
    vector<multiset<int>>vs {};
    int r,m;
    cin>>r;
    for(int i=0; i!=r && cin>>m; i++) {
        v.push_back(m);
    }
    int w = r;
    int n;
    n = pow(2, w);
    for ( int i = 0; i < n; i++ ) {
        for (int  j = 0; j < w; j++ ) {
            if ( i & (1 << j) ) {
                s.insert(v[j]);
            }
        }
        if(gcd(s)!=1 && s.size()>1) {
            vs.push_back(s);
        }
        s.clear();
    }
    cout<<endl;
    auto max=max_element(vs.begin(),vs.end(),[](multiset<int>&a,multiset<int>&b) {
        return a.size()<b.size();
    });
    cout<<max->size();
    return 0;
}
1
1 / 1 / 1
Регистрация: 12.01.2017
Сообщений: 19
12.01.2017, 21:06  [ТС] 3
Peoples, Спасибо огромное!!!
Только есть не большая проблема. Я работаю в Visual studio 2012 и при запуске выдает ошибку:
1>------ Построение начато: проект: B. Большой день для Баша, Конфигурация: Debug Win32 ------
1> main.cpp
1>c:\users\вадим\documents\visual studio 2012\projects\codeforce\b. большой день для баша\b. большой день для баша\main.cpp(34): warning C4244: =: преобразование "double" в "int", возможна потеря данных
1>c:\users\вадим\documents\visual studio 2012\projects\codeforce\b. большой день для баша\b. большой день для баша\main.cpp(14): warning C4715: gcd: значение возвращается не при всех путях выполнения
1> B. Большой день для Баша.vcxproj -> C:\Users\ВАДИМ\Documents\Visual Studio 2012\Projects\codeforce\B. Большой день для Баша\Debug\B. Большой день для Баша.exe
========== Построение: успешно: 1, с ошибками: 0, без изменений: 0, пропущено: 0 ==========

Добавлено через 12 минут
Peoples, То есть вот:
1>------ Построение начато: проект: B. Большой день для Баша, Конфигурация: Debug Win32 ------
1> main.cpp
1>c:\users\вадим\documents\visual studio 2012\projects\codeforce\b. большой день для баша\b. большой день для баша\main.cpp(24): error C2601: v: недопустимые локальные определения функций
1> c:\users\вадим\documents\visual studio 2012\projects\codeforce\b. большой день для баша\b. большой день для баша\main.cpp(23): эта строка содержит "{", которая пока не имеет парной
1>c:\users\вадим\documents\visual studio 2012\projects\codeforce\b. большой день для баша\b. большой день для баша\main.cpp(24): fatal error C1903: не удается восстановить после предыдущих ошибок; остановка компиляции
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========
0
12.01.2017, 21:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2017, 21:06
Помогаю со студенческими работами здесь

Выведите символы, у которых код нечетное число и чётное число
1)Выведите символы,у которых код нечетное число и чётное число. 2)Напечатайте в ряд символы с...

В каждой 4-ой строке взять максимальное нечетное число и найти их произведение
В каждой 4-ой строке взять максимальное нечетное число и найти их произведение(сделать это всё...

Выведите одно число - количество шоколадок, которые может купить Степан
Шоколадка Степан решил угостить одноклассников шоколадками. Шоколадка стоила N грн. С первого...

Выведите одно число-количество деталей, которое может получиться по заданной технологии
Имеется N кг металлического сплава.Из него изготавливают заготовки массой K кг каждая.Поле этого из...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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