2г

Задача по программированию. Решить на Python или C++

В некоторых случаях проверить корректность работы программы гораздо сложнее, чем написать ее. Сейчас у вас будет шанс в этом убедиться. От вас требуется написать программу для проверки корректности ответа второй задачи этой попытки. Напомним ее условие. Имеется парк в виде шестиугольника с 12 аллеями, которые обозначены заглавными символами латиницы. В парке есть только один вход у перекрестка аллей "A", "F", "G". Схема парка приведена ниже. Требуется проверить корректность составленного маршрута движения по этому парку. Маршрут представляется, как последовательность символов, представляющих аллеи в том порядке, в котором они были пройдены. Маршрут движения считается корректным если выполняются следующие требования.

Описание маршрута содержит только символы от "A" до "L".
Маршрут начинается и заканчивается у входа в парк.
Запрещено разворачиваться на 180 градусов. В частности, это означает, что начав движение с одного конца аллеи, вы обязательно дойдете до другого ее конца, причем на перекрестке вы должны будете перейти на другую аллею.
На вход вашей программе будет подано несколько описаний маршрутов. Ваша программа должна будет определить, какие из них удовлетворяют указанным требованиям.

Формат входных данных
На вход в первой строке подается одно натуральное число nn — количество проверяемых маршрутов, 1\le n \le 401≤n≤40. Далее в nn строках записаны сами маршруты. Описание каждого маршрута состоит из последовательности заглавных символов латиницы. Каждое описание не пустое и содержит не более 100 символов.

Формат выходных данных
Программа должна вывести строку из nn нулей и единиц. Единица на ii-той позиции означает, что маршрут с номером ii является корректным. В противном случае в этой позиции должен быть записан ноль.

Методика проверки
Программа проверяется на 8 тестах. Прохождение каждого теста оценивается в 4 балла. Тест из условия задачи при проверке не используется.

Sample Input 1:
6
ABCDKHA
FMG
ABBA
ABCEF
BCDEF
ABCDK

Sample Output 1:
100000

Пояснение к примеру
Первый маршрут является корректным.

Второй маршрут содержит недопустимое обозначение аллеи.

В третьем маршруте происходит разворот на 180 градусов.

Четвертый маршрут не является связным. После третьего шага он приходит к перекрестку "C", "D", "J" и с него нельзя попасть на аллею "E".

Пятый маршрут начинается не у входа.

Шестой м

аршрут заканчивается не у входа.

Дополнен

По дате

По рейтингу

n_veselukha

Новичок

2г

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273

 #include <bitset> 
#include <iostream> 
#include <string> 
#include <vector> 
using namespace std; 
class Route { 
protected: 
    bool static exist(const string& route) { 
        const size_t length = route.length(); 
        if (length < 3) return false;
        if (input.find(route.front()) == string::npos) return false;
        if (input.find(route.back()) == string::npos) return false;
        for (size_t i = 0, j = 1; j < length; ++i, ++j) { 
            auto a = pattern.find(route[i]); 
            if (a == string::npos) return false; 
            auto b = pattern.find(route[j]); 
            if (b == string::npos) return false; 
            if (matrix[a][b] == 0) return false;
            if (j > 1 && route[j] == route[j - 2]) return false;
        } 
        return true; 
    } 
private:
    inline static const string input{ "AFG" };
    inline static const string pattern{ "ABCDEFGHIJKL" }; 
    inline static const int matrix[12][12]{ 
        { 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0 }, 
        { 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0 }, 
        { 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0 }, 
        { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0 }, 
        { 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1 }, 
        { 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 }, 
        { 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1 }, 
        { 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1 }, 
        { 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1 }, 
        { 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1 }, 
        { 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1 }, 
        { 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0 } 
    }; 
}; 
template<size_t Size> 
class Routes : public Route { 
public: 
    void add(const string& route) { 
        routes.push_back(route); 
    } 
    string get()const { 
        bitset<Size> box; 
        size_t pos = routes.size() - 1; 
        for (const auto& route : routes) { 
            if (exist(route)) { 
                box.set(pos); 
            } 
        } 
        const auto s = box.to_string(); 
        const auto n = Size - routes.size(); 
        return string{ s.begin() + n, s.end() }; 
    } 
private: 
    vector<string> routes; 
}; 
int main() { 
    size_t quantity; 
    cin >> quantity; 
    string route; 
    Routes<40> routes; 
    for (size_t i = 0; i < quantity; ++i) { 
        cin >> route; 
        routes.add(route); 
    } 
    auto box = routes.get(); 
    cout << box << '\n'; 
}

P.S. Требуется поддержка стандарта C++17 и выше.

sergei_12322

Гений

2г

1234567891011121314151617181920212223242526272829303132333435363738

 #include <iostream>
#include <vector>
using namespace std;

int find_next(int skip , char Ch, vector<string>& paths)
{
	for (int i = 0; i < paths.size(); i++)
	{
		if (i == skip) continue;
		if (paths[i].find(Ch) != string::npos) return i;
	}
	return -1;
}
 
char searcher(string str)
{
	static vector <string> paths{ "FGA","AHB","BIC","CJD","DKE","ELF","GHIJKL" };
	for (int i = 1; i < str.size(); i++) if (str[i] == str[i - 1]) return '0';
	int tmp = 0;
	for (auto& i : str)
	{
		if (paths[tmp].find(i) != string::npos) { tmp = find_next(tmp, i, paths); if (tmp == -1) return '0'; }
	}
	return tmp==0?'1':'0';
}
 
int main()
{
	int n;
	string str, result;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> str;
		result.push_back(searcher(str));
	}
	cout << result;
}