Имя входного файла: sum.dat
Имя выходного файла: sum.sol
Ограничение времени: 1 с
Ограничение памяти: 64 M
DOC-file
После того, как Урфин Джюс овладел Изумрудным городом, у него появилось любимое занятие — взвешивание изумрудов. Для этого у него есть чашечные весы и набор из N гирь. На одну чашу весов Урфин кладет изумруд, а на другую — некоторые гири из набора так, чтобы чаши уравновесились.
К сожалению, набор гирь у Урфина таков, что ему удается взвесить далеко не все изумруды, которые у него есть. Один из таких изумрудов он решил подарить мудрому филину Гуамоко. Естественно, Урфин хочет отдать Гуамоко самый легкий из тех изумрудов, вес которых он не может определить с помощью своего набора гирь.
Определите, какого веса изумруд получит мудрый филин Гуамоко.
Формат входного файла sum.dat
Текстовый файл sum.dat состоит из двух строк. В первой строке записано натуральное число N — количество гирь, которые есть у Урфина Джюса (1 ≤ N ≤ 50).
В следующей строке через пробел записаны N натуральных чисел - веса гирь. Веса лежат в диапазоне от 1 до 1 000 000 000.
Вес любого изумруда не меньше 1.
Формат выходного файла sum.sol
Текстовый файл sum.sol должен содержать единственное число — минимальный вес, который нельзя уравновесить с помощью гирь из заданного набора.
Программа выглядит так.
Код: Выделить всё
#include <iostream>
#include <stdio.h>
using namespace std;
#define maxn 100
int a[maxn];
int n;
int pr = 0;
void merge(int l, int r) {
if (r == l)
return;
if (r - l == 1) {
if (a[r] < a[l])
swap(a[r], a[l]);
return;
}
int m = (r + l) / 2;
merge(l, m);
merge(m + 1, r);
int buf[maxn];
int xl = l;
int xr = m + 1;
int cur = 0;
while (r - l + 1 != cur) {
if (xl > m) {
buf[cur++] = a[xr++];
pr++;
}
else if (xr > r) {
buf[cur++] = a[xl++];
pr++;
}
else if (a[xl] > a[xr]) {
buf[cur++] = a[xr++];
pr++;
}
else {
buf[cur++] = a[xl++];
pr++;
}
}
for (int i = 0; i < cur; i++)
a[i + l] = buf[i];
}
int main() {
int N, i, j, mn = 0, pr = 0, c = 0;
FILE *fp, *np;
fp = fopen("sum.dat", "r");
np = fopen("sum.sol", "w");
fscanf(fp, "%d", &N);
for(i = 0; i < N; i++) {
fscanf(fp, "%d", &a[i]);
}
merge(0, N - 1);
while(mn == 0) {
pr++;
mn = pr;
for(i = N - 1; i >= 0; i--) {
if(mn >= a[i]) {
mn = mn - a[i];
}
}
}
fprintf(np, "%d\n", pr);
fclose(fp);
fclose(np);
return 0;
}