Untitled
unknown
plain_text
a year ago
7.5 kB
1
Indexable
Never
Ghé thăm bộ phận
Jang tiếp tục đến thăm và giúp đỡ một số bộ phận ngay sau khi anh đến làm việc.
Có một quy tắc trong phong trào của mình. Anh ấy ở lại một bộ phận chính xác trong 10 phút.
Bạn được cung cấp một biểu đồ xác suất của các chuyển động của họ. Hình 1 là một biểu đồ ví dụ.
Jang ở lại phòng 1 trong 10 phút; Sau đó, anh ta di chuyển đến Phòng 2 với xác suất 0, 3 (sau đó ở đó trong 10 phút) hoặc chuyển đến Phòng 3 với xác suất 0, 7 (sau đó ở đó trong 10 phút). Chúng tôi không xem xét thời gian di chuyển giữa các phòng ban.
Có thể có nhiều hơn một mũi tên đi từ một bộ phận; Tổng cơ hội của các mũi tên đi từ một bộ phận phải luôn là 1.
Bộ phận đầu tiên mà ông đến thăm luôn là khoa 1.
Cho một biểu đồ xác suất và thời gian T (tính bằng phút), tạo ra một chương trình tìm bộ phận mà Jang ở lại với cơ hội cao nhất tại thời điểm T.
Ngoài ra, bạn phải báo cáo xác suất tương ứng.
Trong Hình 1 ở trên, bộ phận có cơ hội cao nhất tại thời điểm 10 là khoa 3 và cơ hội là 0,7. Lúc 9 giờ, Jang không bắt đầu di chuyển; Vì vậy, anh ta ở Phòng 1 với xác suất là 1.
Nhìn vào tình hình tại thời điểm 20. Cơ hội ở phòng 1 hoặc phòng 2 là 0. Anh ta rời khỏi phòng 1 chính xác vào thời điểm 10, và nếu anh ta chuyển đến phòng 2 thì anh ta rời khỏi phòng 2 chính xác vào thời điểm 20.
Cơ hội có mặt tại phòng 4 tại thời điểm 20 là 0,3 * 1,0 + 0,7 * 0,8 = 0,86.
Khi anh ta đến một bộ phận mà không có bất kỳ mũi tên đi nào, bộ phận đó trở thành bộ phận cuối cùng mà cuối cùng anh ta đến thăm; Anh ấy ở lại bộ phận trong 10 phút và rời khỏi công việc.
Với đồ thị của Hình 2, Jang không làm việc tại thời điểm 50; trong trường hợp Hình 1, anh ta có thể ở lại làm việc mãi mãi nếu anh ta tiếp tục ở cùng một bộ phận với xác suất vòng lặp, ví dụ: các phòng ban 3, 4 hoặc 6
Ngoài ra, còn có một người khác, Kang, người di chuyển giống như Jang.
Jang luôn đến làm việc vào thời điểm 0, nhưng Kang đến vào một thời điểm khác muộn hơn thời gian 0. Bạn cũng phải báo cáo cùng một loại nội dung cho Kang.
Nếu thời gian đến của Kang là 4, các câu trả lời liên quan đến anh ta được tính chính xác theo nguyên tắc của Jang ngoại trừ anh ta bắt đầu làm việc muộn hơn Jang 4 phút; trong trường hợp này với Hình 2, Kang ở lại phòng 1 từ thời điểm 4 đến lần 13 trong khi Jang ở lại phòng 1 từ thời điểm 0 đến thời điểm 9.
[Đầu vào]
10 trường hợp kiểm thử được đưa ra. Mỗi trường hợp được đưa ra trong hai dòng. Như vậy đầu vào cần hoàn toàn 20 dòng.
Đối với mỗi trường hợp, dòng đầu tiên cung cấp N (số phòng ban), E (số mũi tên), K (thời gian đến của Kang) và T (thời gian tính bằng phút).
1<=N<=100. 1<=E<=200. 1<=K<=1000. 0<=T<=1000. K<=T.
Dòng tiếp theo liệt kê mũi tên E. Mỗi mũi tên được ký hiệu bằng "xác suất của bộ phận đích-nguồn". Chỉ mục cho bộ phận nguồn hoặc bộ phận đích là một số nguyên từ 1 đến 100, bao gồm.
Số nguyên thời gian K và T tính bằng phút. Ví dụ, nếu thời gian T là 8, bạn phải xác định các bộ phận mà Jang và Kang, tương ứng, ở lại với xác suất cao nhất tại thời điểm 8. Các phần tử trong cùng một dòng được phân tách bằng một khoảng trắng. Không có thứ tự đặc biệt trong đó các mũi tên được liệt kê.
[Đầu ra]
Bạn viết 10 câu trả lời trong 10 dòng.
Mỗi dòng bắt đầu bằng "#x" (Ở đây, x có nghĩa là chỉ số trường hợp.), đặt một khoảng trắng và viết câu trả lời.
Câu trả lời bao gồm chỉ số bộ phận có cơ hội cao nhất theo sau là xác suất tương ứng. Chỉ số dept. là một số nguyên và xác suất là một số thực, cách nhau bởi một khoảng trắng.
Nếu có nhiều hơn một bộ phận có cơ hội cao nhất, bạn viết bộ phận của chỉ số thấp nhất.
Nếu Jang không ở bất kỳ bộ phận nào vào thời gian quy định, bạn chỉ cần viết "0 0.000000". Xác suất là một số thực từ 0 đến 1, bao gồm; Nó phải chính xác đến sáu chữ số thập phân.
Một tập hợp khác của một bộ phận và xác suất tương ứng phải được cung cấp cho Kang. Do đó, câu trả lời bao gồm tổng cộng bốn số.
Nhập
6 7 100 100
1 2 0.3 1 3 0.7 2 4 1.0 3 4 0.7 3 6 0.3 4 5 1.0 5 6 1.0
6 7 1 23
1 2 0.3 1 3 0.7 2 4 1.0 3 4 0.7 3 6 0.3 4 5 1.0 5 6 1.0
6 10 8 40
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int n, m, k, j;
static double[][] a = new double[305][305];
static int[] vs = new int[305];
static int res1, res2;
public static void main(String[] args) throws FileNotFoundException {
//Scanner sc = new Scanner(System.in);
Scanner sc = new Scanner(new File("C:\\Users\\SVMC\\workspace\\adv\\Test\\src\\input.txt"));
int T = 1;
for(int t=1; t<=T; t++){
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
j = sc.nextInt();
k = j-k;
if(k%10==0){
k/=10;
}else{
k =k/10+1;
}
if(j%10==0){
j/=10;
}else{
j =j/10+1;
}
for(int i=0; i<m; i++){
int xx = sc.nextInt();
int yy = sc.nextInt();
double dept = sc.nextDouble();
a[xx][yy] = dept;
}
System.out.println(k+" "+j);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
System.out.print(a[i][j]+" ");
}
System.out.println();
}
BFS();
System.out.println(res2);
}
}
static void BFS(){
int[] q = new int[205];
int l=0, r=0;
q[r++]=1;
vs[1]=1;
int cnt=0;
while(l<r && cnt<j){
int top = q[l++];
cnt++;
System.out.println(cnt);
int max = 0, idx=-1;
for(int i=1; i<=n; i++){
if(a[top][i]>0){
vs[i]+=vs[top]*a[top][i];
if(vs[i]>max){
max=vs[i]; idx=i;
}
q[r++]=i;
}
}
printVS();
}
}
static void printVS(){
System.out.println();
for(int i=1; i<=n; i++){
System.out.print(vs[i]+" ");
}
System.out.println();
}
}
6 10 10 10
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
6 10 9 20
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
Ra
#1 0 0.000000 1 1.000000
#2 4 0.790000 4 0.790000
#3 6 0.774000 5 0.774000
#4 3 0.700000 1 1.000000
#5 4 0.860000 3 0.700000