Условие
Дадена е редица X от N цели числа. Да се намери най-дългата подредица, сумата от елементите на която се дели (без остатък) на зададено число K. Казваме, че Z е подредица на X, ако Z може да бъде получена чрез премахване на някои членове на X. Празното множество е подредица (с дължина 0) и цялата редица също е подредица (с дължина N).
Вход
Първият ред на входа съдържа две числа N и K. Следващите редове съдържат точно N цели числа - елементите на редицата. Входът съдържа повече от един пример и завършва с N = 0. Всички числа на входа са цели положителни числа, по-малки от 1000, с изключение на последното число, което е 0.
Изход
Всеки ред на изхода съдържа дължината на най-дългата намерена подредица за поредния пример от входа.
Solution by Chris Popoff (also known as Black & White)
Note: I have changed the input and the output format to show details on each operation.
The important thing is the algorithm, so I’ve skipped some nasty parts from the code, which verifies whether entered data refers to a possible situation.
Compile with MS Visual C++, Borland C++, Dev-C++ 4.9.9.2, or other compiler that supports the ISO Standard C++ with STL.
So... That’s all folks: */
CODE1
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
| #include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n,k,cd=-1,d;
cout << "Enter the number of the digits:";
cin >> n;
cout << "Enter the divisor:";
cin >> k;
vector<int> c(n);
for(int i = 0; i < n; i++) {
cout << "Enter N" << i+1 << " :";
cin >> c[i]; }
int excl = 1;
for(int i = 1; i < n; excl*=++i);
for(int i = 1; i < excl; i++)
{
next_permutation(c.begin(),c.end());
int sum = 0;
for(int b = 0; b < n; b++);
for(d = 0; d < n; d++)
{
sum += c[d];
if(!(sum % k))
if((cd < d) && (cd = d));
}
}
cout << cd+1 << endl;
system("PAUSE");
return EXIT_SUCCESS;
} |
