Dytechlab Algorithms Battle - N nhiệm vụ

View as PDF

Submit solution

Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem source:
Dytechlab Algorithms Battle 2021
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một máy tính cần chạy ~N~ tasks đánh số từ ~1-N~, mỗi task khi chạy sẽ có một số dữ liệu input và output. Mỗi dữ liệu được đặt tên là một chuỗi bao gồm chữ cái in thường, số và dấu "_". Dữ liệu input của một task sẽ là dữ liệu output của một task khác và được xác định bằng một số integer - biểu thị ID của task chứa dữ liệu output và một chuỗi là tên của dữ liệu output tương ứng.

Ví dụ:

Task 1:
Input:
Output: data_x data_y data_z
Task 2:
Input: (1, data_x)
Output: output_z
Task 3:
Input: (2, output_z)
Output:

Cho thông tin về input và output của các task, in ra thứ tự thực hiện các task, biết rằng nếu một task ~A~ sử dụng dữ liệu output của task ~B~ thì máy tính cần sắp xếp sao cho task ~A~ chạy sau task ~B~. In ra ~Impossible~ nếu không có thứ tự hợp lí, nếu có nhiều thứ tự thì in ra task có thứ tự từ điển lớn nhất.

Input:

  • Dòng đầu tiên là một số nguyên dương ~T~, số lượng test cần phải giải quyết.
  • Mỗi nhóm trong số ~T~ dòng sau là một test có dạng như sau:
    • Dòng đầu tiên là một số nguyên dương ~N~. Các dòng tiếp theo mô tả thông tin về các task.
  • Mỗi task sẽ được mô tả như sau:
    • Dòng thứ nhất chứa một số nguyên ~O~ và ~O~ chuỗi độ dài không quá 5 liệt kê output của task.
    • Dòng thứ hai chứa một số nguyên ~I~ là số lượng input của task, ~I~ dòng kế tiếp mỗi dòng chứa một số nguyên và một chuỗi, biểu thị ID và tên của dữ liệu input.

Output:

Với mỗi test in ra một dòng chứa N số nguyên biểu thị thứ tự cần tìm hoặc ~Impossible~ nếu không có thứ tự hợp lý.

Subtask:

  • ~1/3~ số test có ~1 \le T \le 10~, ~1 \le N \le 100~
  • ~2/3~ số test còn lại có ~1 \le T \le 10~, ~1 \le N \le 5000~
  • Tên dữ liệu là một chuỗi độ dài không quá 10 kí tự, bao gồm chữ cái in thường, số và dấu.

Sample Input 1:

1
3
3 data_x data_y data_z
0
1 output_z
1
1 data_x
0
1
2 output_z

Sample Output 1:

1 2 3

Sample Input 2:

1
2
1 data_xyz
1
2 data_abc
1 data_abc
1
1 data_xyz

Sample Output 2:

Impossible

Comments

Please read the guidelines before commenting.


There are no comments at the moment.