Решение задачи Формирование поезда с Меньшиков

Без пояснения   Просмотров: 1158

Компания, занимающаяся железнодорожными перевозками, получила заказ сформировать поезд, состоящий из определённого числа вагонов. Проблема в том, что у компании есть вагоны, выпущенные в разное время, так что каждый из вагонов может иметь один из двух видов сцеплений на каждом конце. У компании также есть один локомотив.

Сцепления и для локомотива, и для вагонов обозначены буквой A или B. Повернуть вагон или локомотив противоположной стороной невозможно.

Дана информация о вагонах и локомотиве. Требуется найти число способов сформировать разные поезда заданной длины из имеющихся видов вагонов. Дополнительным требованием является то, что тип сцеплений на каждом конце состава должен соответствовать типу сцеплений локомотива.

Поезда считаются различными, если при их сравнении от одного конца к другому выявляется хотя бы одно отличие.

Пример 1. Пусть у компании есть вагоны AA, AA, AB, BA, BA и локомотив AB. В поезде должно быть 4 вагона. Из данных вагонов можно сформировать только два различных поезда: BAAAABBA и BAABBAAA. Локомотив можно присоединить к поезду как с левого (используя сцепление B), так и с правого конца (используя сцепление A).

Пример 2. Пусть у компании есть только по одному вагону каждого типа (AA, AB, BA, BB) и локомотив AA, а поезд должен состоять из трёх вагонов. Существует три способа сформировать поезд: AAABBA, ABBAAA и ABBBBA.

Код 

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64 > vvi64;
typedef vector<vvi64 > vvvi64;
int n,k;
char x,y;
int aa,ab,ba,bb;
vector<vector<vector<i64> > > prev,cur;
void input()
{
    cin>>n>>k;
    cur  = vvvi64(k+1,vvi64(k+1,vi64(3,0)));
    prev = vvvi64(k+1,vvi64(k+1,vi64(3,0)));
    scanf("\n%c%c\n",&y,&x);
    y-='A' - 1; x-='A' - 1;
    char cX,cY;
    for (int i=0;i<n;i++) {
        scanf("%c%c\n",&cX,&cY);
        if (cX == 'A' && cY == 'A') aa++;
        if (cX == 'A' && cY == 'B') ab++;
        if (cX == 'B' && cY == 'A') ba++;
        if (cX == 'B' && cY == 'B') bb++;
    }
}
void solve()
{
    if (x == 1) {
        if (aa>0) cur[1][0][1] = 1;
        if (ab>0) cur[0][1][2] = 1;
    }
    else {
        if (ba>0) cur[0][0][1] = 1;
        if (bb>0) cur[0][0][2] = 1;
    }
    prev.swap(cur);
 
    for (int len = 2; len<=k; len++) {
        for (int AA=0; AA<=len; AA++){
            for (int AB=0; AB<=len; AB++){
                if (aa>=AA && ab>=AB && AA+AB<=len) {
                    cur[AA][AB][1] = 0;
                    cur[AA][AB][2] = 0;
                    if (x==1) {
                        int BA = AB; // x = 'A'  E = 'A'
                        int BB = len - AA - AB - BA;
                        if (BB>=0 && BB<=bb && BA<=ba) {
                            if (AA >= 1) cur[AA][AB][1] += prev[AA-1][AB][1];
                            if (BA >= 1) cur[AA][AB][1] += prev[AA][AB][2];
                        }
 
                        BA = AB-1; // x = 'A'  E ='B'
                        BB = len - AA - AB - BA;
                        if (BB>=0 && BB<=bb && BA<=ba) {
                            if (AB >= 1) cur[AA][AB][2] += prev[AA][AB-1][1];
                            if (BB >= 1) cur[AA][AB][2] += prev[AA][AB][2];
                        }
                    }
                    else if (x==2) {
                        int BA = AB + 1; // x = 'B' E = 'A'
                        int BB = len - AA - AB - BA;
                        if (BB>=0 && BB<=bb && BA <= ba) {
                            if (AA >= 1)
                                cur[AA][AB][1] += prev[AA-1][AB][1];
                            if (BA >= 1)
                                cur[AA][AB][1] += prev[AA][AB][2];
                        }
 
                        BA = AB; // x = 'B' E = 'B'
                        BB = len - AA - AB - BA;
                        if (BB>=0 && BB<=bb && BA <= ba) {
                            if (AB >= 1)
                                cur[AA][AB][2] += prev[AA][AB-1][1];
                            if (BB >= 1)
                                cur[AA][AB][2] += prev[AA][AB][2];
                        }
                    }
                }
 
            }
        }
        cur.swap(prev);
    }
 
    i64 res = 0;
    for (int AA=0; AA<=k; AA++) {
        for (int AB=0; AB<=k; AB++) {
            res += prev[AA][AB][y];
        }
    }
    if (res == 0)
        cout<<"NO";
    else
        cout<<"YES"<<endl<<res;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp