1 Тема от Lock Отредактировано Lock (2011-05-09 17:49:41)

  • Lock
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-05-09
  • Сообщений: 3

Тема: Счастливые билеты!

Я тока начал учить дин программирование,подскажите пожалуйста как решить эту задачку с тимуса
Необходимо посчитать количество «счастливых» билетов с заданной суммой цифр, среди тех, номер которых состоит из 2N разрядов. «Счастливым» является билет, у которого сумма первых N цифр равна сумме N последних цифр.
или здесь
http://acm.timus.ru/problem.aspx?space=1&num=1036roll

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Счастливые билеты!

Если сумма нечетна, ответ 0. Иначе считаем количество чисел с N цифрами с суммой S/2 и возводим в квадрат.

3 Ответ от Lock Отредактировано Lock (2011-05-10 10:02:25)

  • Lock
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-05-09
  • Сообщений: 3

Re: Счастливые билеты!

ваще не понял ваш алгоритм решения sad
формула выглядит так да ? result[N][S] = result[N-1][S-i] (где i от 0 до 9 включительно и S-i >=0)
или н знаю,в общем помогите с алгоритмом пожалуйста!

4 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Счастливые билеты!

Из простых соображений следует что количество счастливых билетов длины 2N с суммой цифр 2S равно квадрату количества чисел длины N с суммой S. Это позволяет свести исходную задачу к такой: есть N и S, нужно найти количество чисел из N цифр с суммой цифр S. Такая задача решается динамическим программированием. Кстати, формула правильная.

5 Ответ от Lock

  • Lock
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-05-09
  • Сообщений: 3

Re: Счастливые билеты!

Вот и код)

import java.util.*;
import java.math.BigInteger;
public class LuckyTickets {
    static int MAXN = 50;
    static int MAXS = 1000;
    static BigInteger[][] mem=new BigInteger[MAXN + 1][MAXS + 1];
    static BigInteger z=BigInteger.valueOf(0);
    static BigInteger calc(int n, int s) {
    if (mem[n][s].compareTo(z)>=0)
     return mem[n][s];
      if (n == 0) {
      if (s == 0) return BigInteger.ONE;
          return z;
     }
         mem[n][s] = z;
    for (int i = 0; i < 10; i++) {
       if (s - i >= 0)
       mem[n][s]=(mem[n][s].add(calc(n - 1, s - i)));
     }
     return mem[n][s];
    }
    
    public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      int s=sc.nextInt();
      if (s % 2 != 0) {
        System.out.println(0);
        return;
      }
      BigInteger one=BigInteger.valueOf(-3);
      s /= 2;
      for(int i=0;i<51;i++){
          for(int j=0;j<1001;j++){
              mem[i][j]=one;
          }
      }
      BigInteger ans=calc(n, s).multiply(calc(n, s));
      System.out.println(ans);
      }    
}