@Proshka17

Как понять условие задачи?

Добрый день!
Есть задача:
5f47bb7dc25bb142425683.png
5e5d31df60b3a289300908.png
5e5bb38e5b137113434962.png
5e5bb3cb49bbc461029238.png
5e5bb516b486f611807667.png

Я написал код для подсчета вероятности ничьи, но не понимаю что именно нужно вывести:
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>
#include <fstream>
#include <sstream>

using namespace std;


class Sol {
public:

  int num = 0;

  vector<int> starter;
  int otv = 0;
  int border = 0;
  int summer = 0;

  void rec(vector<int> vec, string posl, int counter, int mn) {

    if (counter == border) {
      int uniqleft = 0;
      int uniqright = 0;
      for (int i = 0; i < starter.size(); ++i) {
        if (starter[i] != vec[i]) uniqleft++;
        if (vec[i] > 0) uniqright++;
      }
      if (uniqleft == uniqright) otv += mn;
      summer += mn;
      cout << num << ": " << posl << " - " << mn << "| " << uniqleft << "-" << uniqright << "\n";
      num += mn;
      return;
    }



    for (int i = 0; i < vec.size(); ++i) {
      if (vec[i] > 0) {
        vec[i]--;
        rec(vec, posl + to_string(i + 1), counter + 1, mn * (vec[i] + 1));
        vec[i]++;
      }
    }

  }

};


int main() {

  ifstream f("input.txt");
  Sol s;

  int count;
  f >> count;
  vector<int> vec;
  int sch = 0;
  for (int i = 0; i < count; ++i) {
    int tmp;
    f >> tmp;
    s.starter.push_back(tmp);
    vec.push_back(tmp);
    sch += tmp;
  }

  s.border = sch / 2;
  s.rec(vec, "", 0, 1);
  cout << (double)s.otv / s.summer;


  //cout << s.bad;



  return 0;
}


Подскажите пожалуйста, как из полученной мной вероятности ничьи получить требуемый ответ?
  • Вопрос задан
  • 736 просмотров
Решения вопроса 1
wataru
@wataru
Про модули уже отвечено, я расскажу, как решать эту задачу быстрее, чем полным перебором.

Пусть общее количество карт - N.

Для простоты понимания, давайте забудем про колоду, просто карты раздаются как-то в 2 кучки по N/2 карт. Это пригодится попозже. Удобнее не вероятность считать, а количество способов раздать карты. Потом надо будет поделить количество хороших способов на все способы.

Сразу комбинаторно подсчитаем, сколько всего способов есть. Это просто количество всех различных колод. Гуглите "перестановки с повторениями". Формула будет такой:
N!/ a[1]! ... a[n]!
Раз мы на это число в конце будем делить, то сразу же считайте перевернутую формулу: подсчитайте факториал числа всех карт по модулю, обратите, умножьте на все маленькие факториалы.

Теперь самое главное, подсчитаем количество способов раздать карты так, что у всех поровну уникальных карт.
Динамическое программирование DP(k, t, i, j) - сколько способов раздать первые k типов карт так, что у первого игрока t карт всего, из них i уникальных, а у второго игрока j уникальных карт (при этом мы знаем, сколько у него всего карт - a[1]+...+a[k] - t).

База:
DP(0,0,0,0) = 1,
DP(0,*,*,*) = 0


Ответ:
sum {i=1..n} DP(n, N/2, i, i)

Пересчет:
DP(k,t,i,j) = sum{v=0..min(a[k],t)} DP(k-1, t-v, i - {v>0}, j-{v < a[k]}) * C(t, v) * C(a[1]+a[2]+...+a[k]-t, a[k]-v)


Тут надо объяснить: мы перебираем, сколько карт последнего типа досталось первому игроку: v. Это все разные колоды, поэтому их надо суммировать. Как бы убираем все карты этого последнего типа из рассмотрения. Что остается? То же самое ДП, но типов на 1 меньше, у первого игрока на v карт меньше и уникальные карты надо уменьшить на 1, если какому-то игроку хоть одна карта досталась. Но есть еще множители - это количество сочетаний. Эти самые v карт последнего типа могут быть на любом из t мест в колоде у первого игрока. Аналогично для второго игрока. Тут надо умножать, потому что любую колоду из предыдущего состояния ДП можно разбавить картами последнего типа в разных позициях и все эти способы дадут разные результирующие колоды. Надо домножить на оба сочетания, потому что мы независимо можем тасовать карты у первого и второго игрока.

Сочетания считаются факториалами С(n,k) = n!/ k! (n-k)!.
Я бы посоветовал предподсчитать все факториалы до 500 по модулю в массив, а так же обратные к ним.

Еще, если не будет влезать по памяти, обратите внимание, что в ДП достаточно хранить лишь 2 слоя по первому параметру. Т.е. надо места для 2*500*50*50 элементов, что для 4-х байтных значений будет занимать ~10mb памяти. Может даже long long можно хранить. Но тут надо переписать ДП снизу вверх, а не рекурсивно. Просто посмотрите, какие состояния куда плюсуются и с какими множителями. В этом случае вы будете не убирать карты последнего типа, а добавлять карты нового типа. Опять же, перебирайте сколько кому этих карт достанется. Надо только осторожно смотреть множители - С(сколько карт после добавления, сколько добавили).

Теперь прикинем на коленке сложность вычислений таким алгоритмом.
Само ДП имеет состояний 50*500*50*50 и пересчет 11 вариантов. Если все перемножить, получается что-то меньше 700 миллионов - в одну-две секунды должно влезать.

Полный перебор у вас, занимает что-то типа 11^50 - никогда не дождетесь на сколько нибудь не тривиальном тесте.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@Mercury13
Программист на «си с крестами» и не только
Подобный вывод используется, чтобы было понятно, что вы способны, если нужно, вычислить с точностью до обыкновенной дроби, но в длинную арифметику (а дроби бывают длинные) не лезть. Ибо реализации длинной арифметики различаются по эффективности от ЯП к ЯП, а в некоторых вообще нет штатной (внешние библиотеки в олимпиадном программировании запрещены).

Числа P и Q высчитываем с точностью до остатка от деления на Z := 109+ 7.

Авторы обещают, что Q mod Z ≠ 0. Z — простое. Тогда НОД(Q mod Z, Z) = 1. Так называемый расширенный алгоритм Евклида (гуглите!) позволяет подобрать такие числа, чтобы m(Q mod Z) + nZ = 1.

Ваша задача — вывести ((P mod Z) · m) mod Z. Специально указал дважды mod Z: первое у вас будет при работе с числом P, второе — при генерации вывода.

Почему так? Возьмём вместо здоровенного Z цифру поменьше, 17. Если у вас получился результат 100/400, при расчётах выйдет цифра 15/9, и 9·2+17·(−1) = 1, и ваша задача — вывести (15·2) mod 17 = 13.

Если же у вас получилось, например, 35/140, при расчётах получается 1/4, 1·(−4)+17·1 = 1, и вы должны вывести (1·(−4)) mod 17 = 13. То есть: независимо от того, насколько сократимая дробь у вас получилась, вы получите один и тот же результат. Тут надо уточнить: там, где возможен отрицательный числитель, нужен не обычный % из Си++, а (a % Z; если получилось отрицательное — добавь Z).

Ну а арифметических переполнений просто не допускайте, Z = 109 + 7 позволяет умножать в типе long long и не уходить в переполнение.

UPD. То, что Z — простое, даёт несколько выгод. Часто результат бывает круглый, и простота требует честно считать остаток, а не угадывать. Ну и побочек меньше.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы