Решение задачи Трубы с Codeforces

С пояснением   Просмотров: 76

Вам задана система труб. Она состоит из двух рядов, каждый из которых состоит из n труб. Верхняя левая труба имеет координаты (1,1), а нижняя правая — (2,n).

Всего существует шесть типов труб: два типа прямых труб и четыре типа изогнутых труб. Ниже приведены примеры всех шести типов:

Типы труб
Вы можете поворачивать каждую из заданных труб на 90 градусов по часовой или против часовой стрелки любое (возможно, нулевое) количество раз (таким образом, типы 1 и 2 могут переходить друг в друга, а также 3,4,5,6 могут переходить друг в друга).

Вы хотите повернуть некоторые трубы таким образом, чтобы поток воды мог начать свое движение в (1,0) (слева от верхней левой трубы), пойти по трубе в (1,1), как-то потечь по связным трубам до трубы (2,n) и потечь вправо в (2,n+1).

Трубы называются связными, если они являются соседними в системе и их концы соединены. Ниже несколько примеров связных труб:

Примеры связных труб
Попробуем описать задачу при помощи примера:

Входные данные первого примера
И его решение ниже:

Решение первого примера
Как вы можете заметить, поток воды — это плохо нарисованная синяя линия. Чтобы достичь ответа, нам необходимо повернуть трубу на позиции (1,2) на 90 градусов по часовой стрелке, трубу на позиции (2,3) на 90 градусов, трубу на позиции (1,6) на 90 градусов, трубу на позиции (1,7) на 180 градусов и трубу на позиции (2,7) на 180 градусов. Тогда поток воды сможет достичь (2,n+1) из (1,0).

Вам необходимо ответить на q независимых запросов.

Код 

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		string s[2];
		cin >> n >> s[0] >> s[1];
		int row = 0;
		int pos = 0;
		for (pos = 0; pos < n; ++pos) {
			if (s[row][pos] >= '3') {
				if (s[row ^ 1][pos] < '3') {
					break;
				} else {
					row ^= 1;
				}
			}
		}
		if (pos == n && row == 1) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	
	return 0;
}

         

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


Пояснение к задаче

Давайте посмотрим, как может течь вода, когда она встречает трубу типа 1 или 2 и в ином случае. Когда вода встречает трубу типа 1 или 2, мы не можем сделать ничего, кроме как позволить ей течь вправо от текущей клетки. Иначе (если текущая труба изогнута) существует два случая: если труба на той же позиции, но в другом ряду не является изогнутой, то ответ «NO», потому что вода должна изменить ряд, но мы не можем повернуть следующую трубу таким образом, чтобы позволить ей течь вправо или влево. Таким образом, текущая труба является изогнутой и труба на той же позиции, но в другом ряду тоже является изогнутой, так давайте изменим текущую строку и перейдем право (очевидно, что нам никогда не нужно поворачивать влево).

Таким образом, ответ (и последовательность труб) однозначно определяется типами труб. Если после прохода по всем n позициям мы не встретили случая «NO» и текущий ряд является вторым, ответ равен «YES».



Комментарии

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


© 2020 HSECODES [email protected] Карта сайта