Участник:Andriygav/BAT3
https://www.spoj.com/problems/BAT3/
#include <iostream> using namespace std; int d[1005], arr[1005], t, n, m; int main(){ cin >> t; while(t--){ cin >> n >> m; for(int i = 0 ; i < n ; i++){ cin >> arr[i]; d[i] = 1; } for(int i = 1 ; i < n ; i++){ for(int j = 0 ; j < i ; j++){ if(arr[j] > arr[i] || j == m){ if(d[j] + 1 > d[i]){ d[i] = d[j] + 1; } } } } int maximum = 1; for(int i = 0 ; i < n ; i++){ if(d[i] > maximum){ maximum = d[i]; } } cout << maximum << endl; } }
К сожалению на питоне на заходит... ошибка runtime, но понять не могу почему, поэтому смотрите код на c++...
UPD: короче питон не для алгоритмов, еще несколько раз пытался запустить, просто не хочет заходить на питоне, причем у меня на той же версии питона работает и на сайте ideone.com тоже (это последняя задача где я дал шанс питону, больше Вы питона не увидите...)
def solver(n, m, arr): d = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[j] > arr[i] or j == m: d[i] = max(d[i], d[j] + 1) return max(max(d), 1) t = int(input()) answers = [] for i in range(t): n, m = list(map(int, input().split())) a = list(map(int, input().split())) answers.append(solver(n, m, a)) for ans in answers: print(ans)
StasFomin 02:32, 17 декабря 2020 (MSK): Жаль. Я засчитываю оба решения — питовые выглядит корректным, ну разве что можно было сэкономить на «answers» «return max(max(d), 1)» вроде можно же просто «max(d)», сам повозился с этой задачей, очень похоже, что как-то толи данные битые приходят (непонятно, как они этого добились), т.е. в определенный момент в строчку для «n, m» приходит пустая строка. В общем, в этом году лучше не пытаться решать питоном, инфа для тех, кто заглянул. Впрочем, 10 баллов тому, чей питон пройдет.
Ура, с Вашей подсказкой я смог решить) я не додумался, что проблема во входных данных
import sys import re def solver(n, m, arr): d = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[j] > arr[i] or j == m: d[i] = max(d[i], d[j] + 1) return max(max(d), 1) text = sys.stdin.read() text_splited = re.findall('\d+', text) all_input_numbers = list(map(int, text_splited)) all_input_numbers.reverse() t = all_input_numbers.pop() answers = [] for i in range(t): n = all_input_numbers.pop() m = all_input_numbers.pop() a = [] for _ in range(n): a.append(all_input_numbers.pop()) answers.append(solver(n, m, a)) for ans in answers: print(ans)