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

@Tadeem · Регистрация: 12.01.2017

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.

@Peoples · 12.01.2017, 20:34

C++

#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;
}

@Tadeem · 12.01.2017, 21:06 **[ТС]**

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 ==========

@Tadeem 1 / 1 / 1 Регистрация: 12.01.2017 Сообщений: 19
		1
	Выведите максимальное число покемонов, которых Баш может взять 12.01.2017, 18:36. Показов 1524. Ответов 2 Метки нет (Все метки) Баш отправился в путешествие, чтобы стать величайшим мастером Покемонов. Чтобы получить первого покемона, он отправился в лабораторию профессора Зулу. Поскольку Баш — любимый студент профессора, Зулу разрешил ему взять столько покемонов из лаборатории, сколько Баш захочет. Однако, профессор предупрел Баша, что группа из 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

@Tadeem 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

Опции темы

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

Решение