Доброго времени суток, уважаемые форумчане, несколько дней мучался над программой, сейчас она работает на на 0,015 секунды дольше чем должна, голова уже не варит от слова совсем, так что нужна помощь знающих людей, пожалуйста, прооптимизируйте мой горе код на сколько это возможно, я буду крайне Вам признателен
за ранее ОГРОМНОЕ СПАСИБО!
Задача с Timus 1287 “Каналы на марсе” (СМ прикрепленный файл)
Один из районов поверхности Марса покрыт идеальной сеткой каналов. Они делят поверхность на одинаковые квадратные клетки (кривизной поверхности мы здесь пренебрегаем). Сам район представляет собой идеальный квадрат, каждая сторона которого разбита на N клеток.
Как показали исследования археологической экспедиции, покрытый каналами район Марса занимала древняя страна под названием Йатик. Жители Йатика выращивали специальный злак — сир — который составлял основу их метаболизма. Сир бывает двух сортов — крупно- и мелкозернистый. Собственно, закат империи Йатика начался после гражданской войны между любителями этих сортов. До последнего времени, однако, не было установлено, какая из партий победила в этой кровопролитной войне. Результаты последней экспедиции на Марс позволяют надеяться на разгадку этой исторической тайны. Ученым удалось установить, сир какого сорта был последним высеян в той или иной клетке Йатика. Поскольку, по стародавней традиции, сир высевали в последовательности клеток (параллельные сторонам света, или идущие под углом 45° к ним), можно предположить, что сторонники победившей партии делали наиболее длинные посевы.
Исходные данные
В первой строке входа содержится единственное число N — размер квадрата (1 ≤ N ≤ 1400). Затем следуют N строк, каждая из которых состоит ровно из N символов. Буква “s” в i-й строке и j-м столбце означает, что в соответствующей клетке квадрата последним был высеян мелкозернистый сир, буква “S” означает, что последним был высеян крупнозернистый сир. Можно считать, что жители данного района не выращивали ничего кроме сира, и в каждой клетке района был засеян сир одного из этих двух сортов.
Результат
В первую строку нужно записать символ “s”, если в кровопролитной войне победила партия любитетей мелкозернистого сира, и символ “S”, если крупнозернистого. Если победителя определить невозможно, то первая строка должна содержать единственный символ “?”. Во второй строке должно быть записано целое число — максимальная длина посева сира одного сорта.
КОД:
def tra(mat): # ФУНКЦИЯ, которая транспонирует исходную матрицу
tm = list()
for i in range(len(mat)):
tm.append(list(len(mat) * ‘0’))
for i in range(len(mat)):
for j in range(len(mat)):
tm = mat # Поворот матрицы на бок, при помощи замены x и y местами
return tm
def scm(mat,lt): # ФУНКЦИЯ, которая находит самые длинные неприрывные цепочки (среди строк передаваемой в качестве матрицы) из букв, возвращет букву, из которой состоит саммая длинная цепочка и колличесвто этой буквы в цепочке или знак “?” если в строчке равное колличесвто букв S и s (второй аргумент всегда 0, углубляться почему это так не буду)
fug = list()
for i in range(len(mat)):
fg = list()
arg = 1
a = mat # начальный элемент строки
for i1 in range(1, len(mat)):
if mat == a:
arg += 1 # добавляем +1 если совпал проверяемый элемент
else:
fg.append() # конец подстрочки из однаковых элементов
arg = 1
a = mat
fg.append() # запись последнего элемента
fg.sort() # сортировка по возрастанию
if len(fg) > 1:
gh = fg
for i in range(len(fg) - 2, -1, -1):
if fg == gh:
if fg == gh:
pass
else:
fug.append([fg, “?”]) # две максимально длинных подстроки совпадают длиной
break
else:
fug.append(fg) # максимальная подстрока самая большая и не имеет аналогов
break
else:
fug.append(fg) # что-то пошло не по плану
if lt == 1:
return fug # если lt=1, то просто выводим максимумы строк
elif lt == 0:
fug.sort()
gh = fug
fg = list()
f = False
for i in range(len(fug) - 2, -1, -1):
if fug == gh:
if fug == gh:
pass
else:
return [fug, “?”] # два максимума под строк совпадают
f = True
break
else:
return fug # максимум строки всего 1
f = True
break
if not f:
return fug # если ничего не нашло
N = int(input())
POLE =
ALL_0 =
ALL_1 =
ALL_2 =
OTVET =
for i in range(N):
POLE.append(list(input()))
if N == 1: # частный случай, когда размер поля 1 на 1 то сразу можем сказать ответ
print(POLE)
print(1)
else:
l = len(POLE) # находим все диагонали
b = l * 2 - 1 # находим все диагонали
ALL_DIAG = [ for _ in range(b * 2)]
м
for i in range(l): # находим все диагонали
for j in range(l): # находим все диагонали
ALL_DIAG.append(POLE) # находим все диагонали
ALL_DIAG.append(POLE) # находим все диагонали
ALL_0.append(
ALL_DIAG) # (МАТРИЦА ДЛЯ ВСЕГО) запихиваем все диагонали # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО это матрица где хранятся все диагонали столбцы и строчки)
ALL_1 = [c for d in ALL_0 for c in
d] # очищаем матрицу со всеми строками столбцами диагоналями от лишних скобок т.е.[[,]] = [,]
for i in range(N): # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
ALL_1.append(POLE) # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
ALL_2 = (tra(POLE)) # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
for i in range(N): # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
ALL_1.append(ALL_2) # запихиваем все строчки в (МАТРИЦА ДЛЯ ВСЕГО)
OTVET.append(scm(ALL_1, 0)) # вызываем функцию scm, которая сама находит ответ на задачу(МАТРИЦА ДЛЯ ВСЕГО)
print(OTVET)
print(OTVET)
fug = list()
for i in range(len(mat)):
fg = list()
arg = 1
a = mat # начальный элемент строки
for i1 in range(1, len(mat)):
if mat == a:
arg += 1 # добавляем +1 если совпал проверяемый элемент
else:
fg.append() # конец подстрочки из однаковых элементов
arg = 1
a = mat
fg.append() # запись последнего элемента
fg.sort() # сортировка по возрастанию
if len(fg) > 1:
gh = fg
for i in range(len(fg) - 2, -1, -1):
if fg == gh:
if fg == gh:
pass
else:
fug.append([fg, “?”]) # две максимально длинных подстроки совпадают длиной
break
else:
fug.append(fg) # максимальная подстрока самая большая и не имеет аналогов
break
else:
fug.append(fg) # что-то пошло не по плану
if lt == 1:
return fug # если lt=1, то просто выводим максимумы строк
elif lt == 0:
fug.sort()
gh = fug
fg = list()
f = False
for i in range(len(fug) - 2, -1, -1):
if fug == gh:
if fug == gh:
pass
else:
return [fug, “?”] # два максимума под строк совпадают
f = True
break
else:
return fug # максимум строки всего 1
f = True
break
if not f:
return fug # если ничего не нашло
N = int(input())
POLE =
ALL_0 =
ALL_1 =
ALL_2 =
OTVET =
for i in range(N):
POLE.append(list(input()))
if N == 1: # частный случай, когда размер поля 1 на 1 то сразу можем сказать ответ
print(POLE)
print(1)
else:
l = len(POLE) # находим все диагонали
b = l * 2 - 1 # находим все диагонали
ALL_DIAG = [ for _ in range(b * 2)]
м
for i in range(l): # находим все диагонали
for j in range(l): # находим все диагонали
ALL_DIAG.append(POLE) # находим все диагонали
ALL_DIAG.append(POLE) # находим все диагонали
ALL_0.append(
ALL_DIAG) # (МАТРИЦА ДЛЯ ВСЕГО) запихиваем все диагонали # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО это матрица где хранятся все диагонали столбцы и строчки)
ALL_1 = [c for d in ALL_0 for c in
d] # очищаем матрицу со всеми строками столбцами диагоналями от лишних скобок т.е.[[,]] = [,]
for i in range(N): # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
ALL_1.append(POLE) # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
ALL_2 = (tra(POLE)) # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
for i in range(N): # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО)
ALL_1.append(ALL_2) # запихиваем все строчки в (МАТРИЦА ДЛЯ ВСЕГО)
OTVET.append(scm(ALL_1, 0)) # вызываем функцию scm, которая сама находит ответ на задачу(МАТРИЦА ДЛЯ ВСЕГО)
print(OTVET)
print(OTVET)
Полная версия: СРОЧНО помогите с оптимизацией кода
Используй тег code
Это первая проверка на мышление 
Для начала надо словесно (только словами, без кода) описать алгоритм решения. Это, знаешь, как дом строить: если ты взялся класть кирпичи, да побольше, побольше, то это совершенно не значит, что у тебя дом получится в результате этого; сначала обязательно надо сделать план строительства, а он к кирпичам никак не относится. С программами всё точно так же происходит. Программы - это такие дома, и никакие строчки (кирпичи) их не делают, хоть они из них и состоят.
[code python]
Тут пиши код
[/code]
Для начала надо словесно (только словами, без кода) описать алгоритм решения. Это, знаешь, как дом строить: если ты взялся класть кирпичи, да побольше, побольше, то это совершенно не значит, что у тебя дом получится в результате этого; сначала обязательно надо сделать план строительства, а он к кирпичам никак не относится. С программами всё точно так же происходит. Программы - это такие дома, и никакие строчки (кирпичи) их не делают, хоть они из них и состоят.
СПАСИБО ЗА ОТВЕТ!
Весь код занимается тем, что отыскивает среди всех диагоналей, столбцов и строк самую длинную НЕПРЕРЫВНУЮ последовательность, состоящую либо из символов “s” ЛИБО из символов “S”, т.е. по сути самую длинную непрерывную последовательность в двумерном массиве(матрице) в коде нельзя использовать библиотек, которые не идут по умолчанию с питоном, более подробно я описал логику алгоритма в комментариях к ключевым строкам, а так же в условии самой задачи единственное что нужно это либо заставить код работать лучше, либо ак то переделать его под динамическое программирование (т.е. применить метод динамического программирования, если это возможно сделать с данным кодом)
УСЛОВИЕ ЗАДАЧИ:
Один из районов поверхности Марса покрыт идеальной сеткой каналов. Они делят поверхность на одинаковые квадратные клетки (кривизной поверхности мы здесь пренебрегаем). Сам район представляет собой идеальный квадрат, каждая сторона которого разбита на N клеток.
Как показали исследования археологической экспедиции, покрытый каналами район Марса занимала древняя страна под названием Йатик. Жители Йатика выращивали специальный злак — сир — который составлял основу их метаболизма. Сир бывает двух сортов — крупно- и мелкозернистый. Собственно, закат империи Йатика начался после гражданской войны между любителями этих сортов. До последнего времени, однако, не было установлено, какая из партий победила в этой кровопролитной войне. Результаты последней экспедиции на Марс позволяют надеяться на разгадку этой исторической тайны. Ученым удалось установить, сир какого сорта был последним высеян в той или иной клетке Йатика. Поскольку, по стародавней традиции, сир высевали в последовательности клеток (параллельные сторонам света, или идущие под углом 45° к ним), можно предположить, что сторонники победившей партии делали наиболее длинные посевы.
Исходные данные
В первой строке входа содержится единственное число N — размер квадрата (1 ≤ N ≤ 1400). Затем следуют N строк, каждая из которых состоит ровно из N символов. Буква “s” в i-й строке и j-м столбце означает, что в соответствующей клетке квадрата последним был высеян мелкозернистый сир, буква “S” означает, что последним был высеян крупнозернистый сир. Можно считать, что жители данного района не выращивали ничего кроме сира, и в каждой клетке района был засеян сир одного из этих двух сортов.
Результат
В первую строку нужно записать символ “s”, если в кровопролитной войне победила партия любитетей мелкозернистого сира, и символ “S”, если крупнозернистого. Если победителя определить невозможно, то первая строка должна содержать единственный символ “?”. Во второй строке должно быть записано целое число — максимальная длина посева сира одного сорта.
Весь код занимается тем, что отыскивает среди всех диагоналей, столбцов и строк самую длинную НЕПРЕРЫВНУЮ последовательность, состоящую либо из символов “s” ЛИБО из символов “S”, т.е. по сути самую длинную непрерывную последовательность в двумерном массиве(матрице) в коде нельзя использовать библиотек, которые не идут по умолчанию с питоном, более подробно я описал логику алгоритма в комментариях к ключевым строкам, а так же в условии самой задачи единственное что нужно это либо заставить код работать лучше, либо ак то переделать его под динамическое программирование (т.е. применить метод динамического программирования, если это возможно сделать с данным кодом)
УСЛОВИЕ ЗАДАЧИ:
Один из районов поверхности Марса покрыт идеальной сеткой каналов. Они делят поверхность на одинаковые квадратные клетки (кривизной поверхности мы здесь пренебрегаем). Сам район представляет собой идеальный квадрат, каждая сторона которого разбита на N клеток.
Как показали исследования археологической экспедиции, покрытый каналами район Марса занимала древняя страна под названием Йатик. Жители Йатика выращивали специальный злак — сир — который составлял основу их метаболизма. Сир бывает двух сортов — крупно- и мелкозернистый. Собственно, закат империи Йатика начался после гражданской войны между любителями этих сортов. До последнего времени, однако, не было установлено, какая из партий победила в этой кровопролитной войне. Результаты последней экспедиции на Марс позволяют надеяться на разгадку этой исторической тайны. Ученым удалось установить, сир какого сорта был последним высеян в той или иной клетке Йатика. Поскольку, по стародавней традиции, сир высевали в последовательности клеток (параллельные сторонам света, или идущие под углом 45° к ним), можно предположить, что сторонники победившей партии делали наиболее длинные посевы.
Исходные данные
В первой строке входа содержится единственное число N — размер квадрата (1 ≤ N ≤ 1400). Затем следуют N строк, каждая из которых состоит ровно из N символов. Буква “s” в i-й строке и j-м столбце означает, что в соответствующей клетке квадрата последним был высеян мелкозернистый сир, буква “S” означает, что последним был высеян крупнозернистый сир. Можно считать, что жители данного района не выращивали ничего кроме сира, и в каждой клетке района был засеян сир одного из этих двух сортов.
Результат
В первую строку нужно записать символ “s”, если в кровопролитной войне победила партия любитетей мелкозернистого сира, и символ “S”, если крупнозернистого. Если победителя определить невозможно, то первая строка должна содержать единственный символ “?”. Во второй строке должно быть записано целое число — максимальная длина посева сира одного сорта.
def tra(mat): # ФУНКЦИЯ, которая транспонирует исходную матрицу tm = list() for i in range(len(mat)): tm.append(list(len(mat[i]) * '0')) for i in range(len(mat)): for j in range(len(mat)): tm[j][i] = mat[i][j] # Поворот матрицы на бок, при помощи замены x и y местами return tm def scm(mat,lt): # ФУНКЦИЯ, которая находит самые длинные неприрывные цепочки (среди строк передаваемой в качестве матрицы) из букв, возвращет букву, из которой состоит саммая длинная цепочка и колличесвто этой буквы в цепочке или знак "?" если в строчке равное колличесвто букв S и s (второй аргумент всегда 0, углубляться почему это так не буду) fug = list() for i in range(len(mat)): fg = list() arg = 1 a = mat[i][0] # начальный элемент строки for i1 in range(1, len(mat[i])): if mat[i][i1] == a: arg += 1 # добавляем +1 если совпал проверяемый элемент else: fg.append([arg, a]) # конец подстрочки из однаковых элементов arg = 1 a = mat[i][i1] fg.append([arg, a]) # запись последнего элемента fg.sort() # сортировка по возрастанию if len(fg) > 1: gh = fg[-1] for i in range(len(fg) - 2, -1, -1): if fg[i][0] == gh[0]: if fg[i][1] == gh[1]: pass else: fug.append([fg[i][0], "?"]) # две максимально длинных подстроки совпадают длиной break else: fug.append(fg[-1]) # максимальная подстрока самая большая и не имеет аналогов break else: fug.append(fg[0]) # что-то пошло не по плану if lt == 1: return fug # если lt=1, то просто выводим максимумы строк elif lt == 0: fug.sort() gh = fug[-1] fg = list() f = False for i in range(len(fug) - 2, -1, -1): if fug[i][0] == gh[0]: if fug[i][1] == gh[1]: pass else: return [fug[i][0], "?"] # два максимума под строк совпадают f = True break else: return fug[-1] # максимум строки всего 1 f = True break if not f: return fug[-1] # если ничего не нашло N = int(input()) POLE = [] ALL_0 = [] ALL_1 = [] ALL_2 = [] OTVET = [] for i in range(N): POLE.append(list(input())) if N == 1: # частный случай, когда размер поля 1 на 1 то сразу можем сказать ответ print(POLE[0][0]) print(1) else: l = len(POLE) # находим все диагонали b = l * 2 - 1 # находим все диагонали ALL_DIAG = [[] for _ in range(b * 2)] for i in range(l): # находим все диагонали for j in range(l): # находим все диагонали ALL_DIAG[i + j].append(POLE[j][i]) # находим все диагонали ALL_DIAG[i + j + b].append(POLE[~j][i]) # находим все диагонали ALL_0.append(ALL_DIAG) # (МАТРИЦА ДЛЯ ВСЕГО) запихиваем все диагонали # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО это матрица где хранятся все диагонали столбцы и строчки) ALL_1 = [c for d in ALL_0 for c in d] # очищаем матрицу со всеми строками столбцами диагоналями от лишних скобок т.е.[[[a],[b]]] = [[a],[b]] for i in range(N): # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО) ALL_1.append(POLE[i]) # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО) ALL_2 = (tra(POLE)) # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО) for i in range(N): # запихиваем все столбцы в (МАТРИЦА ДЛЯ ВСЕГО) ALL_1.append(ALL_2[i]) # запихиваем все строчки в (МАТРИЦА ДЛЯ ВСЕГО) OTVET.append(scm(ALL_1, 0)) # вызываем функцию scm, которая сама находит ответ на задачу(МАТРИЦА ДЛЯ ВСЕГО) print(OTVET[0][1]) print(OTVET[0][0])
RjugoНужно описывать не то, чем занимается код, который ты уже написал. Нужно описывать то, чем будет заниматься код, который ты ещё не написал. То есть нужно полное описание на словах решения задачи.
Весь код занимается тем, что отыскивает среди всех диагоналей, столбцов и строк самую длинную НЕПРЕРЫВНУЮ последовательность, состоящую либо из символов “s” ЛИБО из символов “S”, т.е. по сути самую длинную непрерывную последовательность в двумерном массиве(матрице)
А описывать в стиле “я построил треугольник из кирпичей, вот этот треугольник!” не надо, потому что я и так вижу, что это треугольник из кирпичей. А дом где? Плана-то нет. Сомневаюсь, что из треугольника из кирпичей получится дом. Ещё не факт, что этот дом будет кирпичный. Может, там бетон нужно будет делать и плиты краном устанавливать.
Так что переосмысливай подход к разработке программы.
Вот, допустим, ты получил эту матрицу на 1400 строк и столбцов. Дальше что? Каким образом ты ищешь непрерывные цепочки? Я тебя не про твой код спрашиваю, а вот про то, как ты ищешь эти цепочки руками, глазами, без кода. Откуда ты начинаешь, как это продолжается при достижении той же границы матрицы и как это заканчивается? Что ты будешь делать, если две цепочки, которые ты обыскиваешь в разное время, пересекутся на каких-то элементах? Как ты поймёшь, что эти пересечения уже учтены и их повторно считать не надо? Заметь, эти все вопросы нужно сначала разрешить, а только потом начинать какой-то там код писать.
Понял, исправляюсь)
На вход мой код получает матрицу ЗАТЕМ:
1. Проверяю частный случай, если матрица 1 на 1 то СРАЗУ печатаю ответ
2. Задействую алгоритм перебора всех диагоналей(главных и побочных) запихиваю каждую диагональ в список, а потом все диагонали введенной матрицы запихиваю в один список ALL_1
3.Беру все строки исходной матрицы и запихиваю каждую из них в список, далее, кладу все эти строки в список ALL_1
4. Транспонирую исходную матрицу и строки транспонированной матрицы так же как и в пункте 3 распихиваю каждую строку по спискам, а затем все списки так же пихаю в ALL_1
5. Наконец у меня есть список ALL_1 со всеми диагоналями(главными и побочными), всеми строками, всеми столбцами и потом просто применяю к списку ALL_1 свою функцию scm, которая и находит символ-лидер(который повторяется чаще всего среди всех вложенных списков списка ALL_1), печатаю его самого(или знак “?” если в списке максимальное количество “S” и “s” одинаково) и в следующей строке печатаю сколько раз он встретился
На вход мой код получает матрицу ЗАТЕМ:
1. Проверяю частный случай, если матрица 1 на 1 то СРАЗУ печатаю ответ
2. Задействую алгоритм перебора всех диагоналей(главных и побочных) запихиваю каждую диагональ в список, а потом все диагонали введенной матрицы запихиваю в один список ALL_1
3.Беру все строки исходной матрицы и запихиваю каждую из них в список, далее, кладу все эти строки в список ALL_1
4. Транспонирую исходную матрицу и строки транспонированной матрицы так же как и в пункте 3 распихиваю каждую строку по спискам, а затем все списки так же пихаю в ALL_1
5. Наконец у меня есть список ALL_1 со всеми диагоналями(главными и побочными), всеми строками, всеми столбцами и потом просто применяю к списку ALL_1 свою функцию scm, которая и находит символ-лидер(который повторяется чаще всего среди всех вложенных списков списка ALL_1), печатаю его самого(или знак “?” если в списке максимальное количество “S” и “s” одинаково) и в следующей строке печатаю сколько раз он встретился
Вот у тебя на входе матрица 3x3
Вариант 1
Вариант 2
Чему равны максимальные длины цепочек в ней для s и для S?
Во втором варианте получается вообще кольцо из S.
Вот у тебя на входе матрица 4x4
Чему равна максимальная длина цепочки S в ней? Обнаружь цепочку саму.
Вот тут условие есть
Вот пример цепочки из букв S, где под углом 45° к разным сторонам света цепочка поворачивает
Так что разберись сначала с понятием цепочки.
Вариант 1
sSs
SSS
sSs
Вариант 2
sSs
SsS
sSs
Чему равны максимальные длины цепочек в ней для s и для S?
Во втором варианте получается вообще кольцо из S.
Вот у тебя на входе матрица 4x4
sSss
Ssss
sSss
ssSS
Вот тут условие есть
RjugoОно не означает, что цепочка - это диагональ.
Поскольку, по стародавней традиции, сир высевали в последовательности клеток (параллельные сторонам света, или идущие под углом 45° к ним), можно предположить, что сторонники победившей партии делали наиболее длинные посевы.
Вот пример цепочки из букв S, где под углом 45° к разным сторонам света цепочка поворачивает
SsSs
sSsS
ssss
ssss
Так что разберись сначала с понятием цепочки.
Я тоже об этом думал, но я считаю, что такие варианты не учитываются, они резко усложняют задачу и эти случаи с “кольцом” и другие точно бы указали в примерах, к тому же мой код проходит 16 проверок, так что он точно бы прошел бы меньше, если бы эти кольца считались бы возможными, давайте отталкиваться от той логики, которой я придерживался изначально при написании кода и не будем учитывать кольца
RjugoТак что ты считаешь цепочкой? Дай точное определение цепочки.
Я тоже об этом думал, но я считаю, что такие варианты не учитываются, они резко усложняют задачу и эти случаи с “кольцом” и другие точно бы указали в примерах, к тому же мой код проходит 16 проверок
Вот в этой матрице 4x4
ssss
ssss
ssss
sssS
Они же не могли их засаживать повторно. Сначала засадили так, а потом пересадили вот так.
Ты вот говоришь про оптимизацию кода, сократить время там и так далее. А ты уверен, что у тебя вот эти повторные перезасевы исключены? Если ты тупо берёшь сначала ряды, а потом диагонали, то не происходит ли именно вот это?
RjugoА ты думаешь, что в реальном программировании все задачки будут простыми и удобными? Вот этот класс задач, как эта, направлен на работу с изображениями. Возьми капчу и попытайся распознать с неё цифры и буквы. Там ничего удобного не будет, а тест там - не какие-то проверки, которые сделали добрые дяденьки для маленьких школьников, чтобы те случайно мозги себе не сломали, а результат в текстовом файле, который либо совпадает, либо нет. И вот ты хоть в лепёшку разбейся, если ты не продумал всё до, то ничего и не будет в результате. Программа - это такая вещь… её нельзя уговорить, чтобы она стала попроще.
они резко усложняют задачу
цепочкой могут являться:
1. вся строка(или часть / части строки)
2. весь столбец(или часть / части столбца)
3. вся диагональ (или часть / части диагонали) (главные и побочные диагонали)
И это ВСЕ
ниже предоставлю схему, на которой попробую визуально представить непрерывные цепочки (непрерывные посевы)
цветными прямоугольниками я указал непрерывные посевы, если смотреть по строкам, аналогично со столбцами
цветными линиями я так же указал непрерывные посевы, если смотреть по диагоналям(отдельно сомтрим главные и побочные)
P.S. Я прекрасно понимаю, что сложные задачи более чем часто встречаются в реальном программировании, но это задача и я делаю логичные выводы, и да, на сайте Timus пишется лишь номер теста на котором программа не правильно работает, но не дает самой причины или примера входных данных, так что я точно так же мучаюсь в процессе поиска багов как и все другие программисты
1. вся строка(или часть / части строки)
2. весь столбец(или часть / части столбца)
3. вся диагональ (или часть / части диагонали) (главные и побочные диагонали)
И это ВСЕ
ниже предоставлю схему, на которой попробую визуально представить непрерывные цепочки (непрерывные посевы)
цветными прямоугольниками я указал непрерывные посевы, если смотреть по строкам, аналогично со столбцами
цветными линиями я так же указал непрерывные посевы, если смотреть по диагоналям(отдельно сомтрим главные и побочные)
P.S. Я прекрасно понимаю, что сложные задачи более чем часто встречаются в реальном программировании, но это задача и я делаю логичные выводы, и да, на сайте Timus пишется лишь номер теста на котором программа не правильно работает, но не дает самой причины или примера входных данных, так что я точно так же мучаюсь в процессе поиска багов как и все другие программисты
Сама задача и тесты
https://acm.timus.ru/problem.aspx?num=1287
https://acm.timus.ru/submit.aspx?space=1&num=1287
О, видал
https://acm.timus.ru/forum/thread.aspx?id=29731&upd=635074897412446678
Эту фигню с кольцом уже обсуждали.
То есть мудак тут - автор задачи самой. Придумал задачу неопределённую и решай как хочешь. Думаю, тестировщики с Timus'а поднапряглись, чтобы понять, что имел в виду автор задачи, и нагенерили своих тестов, которые приблизительно что-то проверяют, что-то похожее на правду.
Так что будем считать, что там просто тупо надо посчитать непрерывные цепочки от длины 1 до длины 1400, которые идут непрерывно либо по горизонтали, либо по вертикали, либо по главной диагонали, либо по побочной диагонали.
Будем считать цепочкой непрерывную последовательность от единицы, которая либо горизонтальная, либо вертикальная, либо наискосок направо, либо наискосок налево. Вот это и будет определением цепочки. Видимо, пересекающиеся цепочки не учитываются и ими можно пренебречь.
Пример матрицы 3x3
Тут определить, в какой последовательности засевались цепочки из S, просто невозможно именно из-за автора задачи. То ли засевалась вторая колонка, а потом отдельно засевались одинарные цепочки второго ряда, то ли засевался второй ряд, а потом засевались одинарные цепочки второй колонки.
Видимо, тут тупо надо их считать засеваемыми повторно. И тут тогда получается есть две цепочки из S тройной длины: одна цепочка - второй ряд; вторая цепочка - вторая колонка. А для s тут четыре цепочки одинарной длины. И также есть цепочки из S двойной длины. А если их засевать можно повторно, то их можно засевать сначала сверху вниз, а потом и снизу вверх. Спасибо автору за “вумную” задачу.
Будем считать, что если цепочка посчитана уже, то перезасевать элементы из неё нельзя.
https://acm.timus.ru/problem.aspx?num=1287
https://acm.timus.ru/submit.aspx?space=1&num=1287
О, видал
https://acm.timus.ru/forum/thread.aspx?id=29731&upd=635074897412446678
Эту фигню с кольцом уже обсуждали.
То есть мудак тут - автор задачи самой. Придумал задачу неопределённую и решай как хочешь. Думаю, тестировщики с Timus'а поднапряглись, чтобы понять, что имел в виду автор задачи, и нагенерили своих тестов, которые приблизительно что-то проверяют, что-то похожее на правду.
Так что будем считать, что там просто тупо надо посчитать непрерывные цепочки от длины 1 до длины 1400, которые идут непрерывно либо по горизонтали, либо по вертикали, либо по главной диагонали, либо по побочной диагонали.
Будем считать цепочкой непрерывную последовательность от единицы, которая либо горизонтальная, либо вертикальная, либо наискосок направо, либо наискосок налево. Вот это и будет определением цепочки. Видимо, пересекающиеся цепочки не учитываются и ими можно пренебречь.
Пример матрицы 3x3
sSs
SSS
sSs
Видимо, тут тупо надо их считать засеваемыми повторно. И тут тогда получается есть две цепочки из S тройной длины: одна цепочка - второй ряд; вторая цепочка - вторая колонка. А для s тут четыре цепочки одинарной длины. И также есть цепочки из S двойной длины. А если их засевать можно повторно, то их можно засевать сначала сверху вниз, а потом и снизу вверх. Спасибо автору за “вумную” задачу.
Будем считать, что если цепочка посчитана уже, то перезасевать элементы из неё нельзя.