Участник:Andriygav/BAT3

Материал из DISCOPAL
Перейти к: навигация, поиск

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)