Участник:Easik/PFDEP — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «* https://www.spoj.com/problems/PFDEP/ Через input spoj не принимал решение. Воспользовался хаком отсюда (Andriy…»)
 
 
Строка 1: Строка 1:
 
* https://www.spoj.com/problems/PFDEP/
 
* https://www.spoj.com/problems/PFDEP/
  
Через input spoj не принимал решение. Воспользовался хаком отсюда ([[Andriygav/BAT3]]) и всё заработало.
+
Через input spoj не принимал решение. Воспользовался хаком отсюда ([[Участник:Andriygav/BAT3]]) и всё заработало.
  
 
'''Python 3 (python 3.7.3)'''
 
'''Python 3 (python 3.7.3)'''

Текущая версия на 21:49, 17 декабря 2020

Через input spoj не принимал решение. Воспользовался хаком отсюда (Участник:Andriygav/BAT3) и всё заработало.

Python 3 (python 3.7.3)

import re
import sys
import numpy as np
 
def main(v, v_size):
 
	vis = np.zeros(101).astype(int)  # Array of visited tasks
 
	for k in range(n):
		for i in range(1, n + 1):
 
			ct = 0
			if vis[i] == 1:
				continue
 
			# Count unvisited dependencies
			for j in range(v_size[i]):
				if vis[v[i][j]] == 0:
					ct += 1
 
			# If no dependencies or no unvisited dependencies - push task in queue
			if ct == 0:
				vis[i] = 1
				print(str(i) + ' ', end='')
				break
 
	print('')
 
 
v = np.zeros((101, 101)).astype(int)
v_size = np.zeros(101).astype(int)
 
text = sys.stdin.read()
text_splited = re.findall('\d+', text)
all_input_numbers = list(map(int, text_splited))
 
n = all_input_numbers[0]
m = all_input_numbers[1]
i = 2
 
# Read lines with dependencies
for h in range(m):
 
	idx = all_input_numbers[i]
	i += 1
 
	k = all_input_numbers[i]
	i += 1
 
	for j in range(k):
		v[idx][j] = all_input_numbers[i]
		v_size[idx] += 1
		i += 1
	assert k == v_size[idx]
 
main(v, v_size)