Форум программистов, компьютерный форум, киберфорум
Наши страницы

Улучшение решения... - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Составить алгоритм к программе http://www.cyberforum.ru/cpp-beginners/thread29077.html
Нужно составить алгоритм, помогите пожалуйста :help: Эта программа: Определяет первый положительный максимальный элемент и его позицию в массиве, а также количество положительных элементов. ...
C++ Плавающие числа (Время: 1 сек. Память: 16 Мб ) Дано N целых чисел. Каждое из них можно один раз изменить не более чем на целую величину L как в сторону увеличения, так и в сторону уменьшения или оставить без... http://www.cyberforum.ru/cpp-beginners/thread29074.html
Определить расстояние от данной точки до ломаной C++
Есть задача. Вот ее краткий пересказ. На плосткости дана точка с координатами x и у. Дано n. На плоскости дано n точек, попарно соединенных прямыми, чтобы получилась замкнутая ломанная (первая со...
C++ Составить программу для нахожления точки пересечения этих функций
Кто нить кто понимает с++ помогите с задачкой :) Дана парабола y=ax2+bx+с и прямая y=kx+m. Составить программу для нахожления точки пересечения этих функций, если тковая существует. В случае если...
C++ Строки немогу найти решения или нехватает литературы чтоб самому разобраться http://www.cyberforum.ru/cpp-beginners/thread29059.html
подскажите пожалуйста как решить эти задачи методом для начинающего или где можно взять литературу по строкам пожалуйста заранее благодарен 1.Дана строка. Заменить в строке все большые буквы...
C++ Поиск экстремумов функции Вообще завал(( Была задана такая задача: Найти экстремумы функции y=2*sin(3*x) С чего вообще начать решать эту задачу? Есть ли какие-нибудь специальные функции(и если есть какие нужны... подробнее

Показать сообщение отдельно
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254

Улучшение решения... - C++

07.04.2009, 17:13. Просмотров 1309. Ответов 2
Метки (Все метки)

Я тут решил задачку... Решение не оптимальное... Помогите улучшить... Вот задача:
Несчастливые номера
(Время: 1 сек. Память: 16 Мб)
Обычно автобусный билет с номером, состоящим из 6 цифр, считается счастливым, если сумма первых трех цифр его номера была равна сумме трех последних. Школьник Вася очень любил получать счастливые билеты, однако это случалось не так часто. Поэтому для себя он изменил определение счастливого билета.
Счастливым он считал тот номер, сумма некоторых цифр которого равнялась сумме оставшихся цифр. В его представлении билет с номером 561743 счастливый, так как 5+1+4+3=6+7.
Вася вырос, но по привычке в номерах различных документов пытается найти признаки счастливого номера Смайлик - улыбка. Для этого он расширил свое определение счастливого номера на N значные номера лицевых счетов и других документов, состоящих из цифр от 0 до K. Номер документа он называет счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся. Остальные номера для него несчастливые. К сожалению, несмотря на расширенное понимание “счастья”, несчастливых номеров остается еще много...
Вам предлагается определить количество несчастливых N-значных номеров, которые можно составить, используя цифры от 0 до K. В номерах допускается любое количество ведущих нулей.
Входные данные
Входной файл INPUT.TXT содержит описание вида номеров в виде двух чисел N и K, разделенных пробелом. (1 <= N <= 100, 1 <= K <= 9, N*K <= 300)
Выходные данные

В выходной файл OUTPUT.TXT выведите количество несчастливых номеров для заданных N и K.
Примеры
INPUT.TXT OUTPUT.TXT
1 7 7

4 3 164

11 9 50184219171



Вот мое решение
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
53
54
55
56
57
58
59
#include <cmath>
#include <cstdio>
#include <cstring>
int N, K, a[103], num[10], is[1010];
long long sum, tmp, fact[103];
void cnt( int n, int mi, int ss ){
     if (n == N){
           if (ss & 1)
           return;
     for (int i=0; i<ss+1; i++)
         is[i] = 0;
         is[0] = 1;
     int s = 0;
     for (int i=0; i<N; i++){
         if (is[ss/2])
         break;
     for (int j = s; j >= 0; j--)
        if (is[j])
           is[j+a[i]]=1;
        s += a[i];
    }
    if (is[ss/2])
    {
      tmp = 1;
      int rest = N;
      for (int i=0; i<K+1; i++)
          for (int j=0; j<num[i]; j++){
              tmp*=rest--;
              tmp/=j+1;
              }
      sum += tmp;
    }
    return;
  }
  for (int i = mi; i <= K; i++)
  {
    a[n] = i;
    num[i]++;
    cnt(n + 1, i, ss + i);
    num[i]--;
  }  
}
 
int main()
{
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  while (scanf("%d%d", &N, &K) == 2 && (N || K))
  {
    memset(num, 0, sizeof(num));
    sum = 0;
    fact[0] = 1;
    for (int i = 1; i <103; i++)
    fact[i]=i*fact[i-1];
    cnt(0,0,0);
    printf("%I64d\n", (long long)(pow(K + 1, N) + 0.5) - sum);
  }
  return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru