BOI 2005 - Ngày 2

Các nhà khảo cổ Baltic vừa tìm thấy một bản thảo cổ, nhưng nhiều phần đã hư hỏng và một số chữ cái biến mất. Một nhà khoa học nhận xét rằng các từ trong bản thảo giống một ngôn ngữ có các quy tắc sau:

• trong một từ không có quá \(VC\) nguyên âm liên tiếp và không có quá \(CC\) phụ âm liên tiếp;
• không có quá \(VE\) nguyên âm giống nhau liên tiếp và không có quá \(CE\) phụ âm giống nhau liên tiếp.

Các nguyên âm là a, e, i, o, u; \(21\) chữ cái còn lại là phụ âm.

Hãy tính số cách thay mỗi ký tự bị mất bằng một chữ cái thường để thu được một từ hợp lệ theo các quy tắc trên.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên \(VE,VC,CE,CC\) với \(1 \le VE \le VC \le 4\) và \(1 \le CE \le CC \le 4\).

Dòng thứ hai chứa một từ dài không quá \(15\) ký tự gồm các chữ cái Latin thường; mỗi chữ cái bị mất được ký hiệu bằng *.

Dữ liệu ra

In số cách khôi phục từ hợp lệ. Đáp án vừa trong số nguyên có dấu \(64\) bit; nếu không có cách nào, in 0.

Ví dụ

1 1 1 1
a**

105

1 1 1 1
b*i

0

1 2 1 2
ancient

1

4 4 4 4
man****ipt

261870

2 2 2 2
*boi*

546

Có \(N\) thị trấn và \(M\) tuyến xe buýt một chiều chạy thẳng giữa các thị trấn. Các thị trấn được đánh số từ \(1\) đến \(N\). Một hành khách ở thị trấn \(1\) tại thời điểm \(0\) cần đến thị trấn \(P\). Người ấy sẽ được đón tại bến xe của thị trấn \(P\) đúng thời điểm \(T\); nếu đến sớm thì phải chờ.

Với tuyến \(i\), biết thị trấn xuất phát \(s_i\), thị trấn đến \(t_i\) và các khoảng thời gian gần đúng. Xe rời \(s_i\) tại một thời điểm thuộc \([a_i,b_i]\) và đến \(t_i\) tại một thời điểm thuộc \([c_i,d_i]\); hai đầu mút đều được tính.

Hành khách muốn chọn một hành trình làm nhỏ nhất tổng thời gian chờ lớn nhất có thể, đồng thời bảo đảm không lỡ bất kỳ chuyến nối tiếp nào. Vì vậy, khi đổi xe, thời điểm đến muộn nhất của chuyến trước không được sau thời điểm khởi hành sớm nhất của chuyến sau.

Khi tính thời gian chờ trong trường hợp xấu nhất, giả sử mỗi lần đến là sớm nhất có thể và mỗi lần khởi hành là muộn nhất có thể. Thời gian chờ trước chuyến đầu, giữa các chuyến và từ khi đến \(P\) đến \(T\) đều được tính.

Dữ liệu vào

Dòng đầu gồm \(N,M,P,T\) (\(1 \le N \le 50\,000\), \(1 \le M \le 100\,000\), \(1 \le P \le N\), \(0 \le T \le 10^9\)).

Mỗi dòng trong \(M\) dòng tiếp theo gồm \(s_i,t_i,a_i,b_i,c_i,d_i\), trong đó \(1 \le s_i,t_i \le N\) và

Dữ liệu ra

In tổng thời gian chờ lớn nhất của hành trình tối ưu. Nếu không thể bảo đảm đến thị trấn \(P\) không muộn hơn \(T\), in -1.

Ví dụ

3 6 2 100
1 3 10 20 30 40
3 2 32 35 95 95
1 1 1 1 7 8
1 3 8 8 9 9
2 2 98 98 99 99
1 2 0 0 99 101

32

3 2 2 100
1 3 0 0 49 51
3 2 50 51 100 100

-1

Hãy dựng một đa giác lồi có các độ dài cạnh cho trước. Trong bài này, một đa giác được coi là lồi khi mọi góc trong đều lớn hơn nghiêm ngặt \(0^\circ\) và nhỏ hơn nghiêm ngặt \(180^\circ\).

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\) (\(3 \le N \le 1000\)), số đỉnh của đa giác. Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên \(a_i\) (\(1 \le a_i \le 10\,000\)), là độ dài một cạnh.

Dữ liệu ra

Nếu dựng được đa giác, in đúng \(N\) dòng. Dòng thứ \(i\) chứa hai số thực \(x_i,y_i\) (\(|x_i|,|y_i| \le 10\,000\,000\)). Nối \((x_i,y_i)\) với \((x_{i+1},y_{i+1})\) cho \(1 \le i<N\), rồi nối \((x_N,y_N)\) với \((x_1,y_1)\), phải thu được một đa giác lồi. Độ dài các cạnh phải bằng các số trong dữ liệu vào, nhưng không nhất thiết theo cùng thứ tự. Có thể liệt kê các đỉnh theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Nếu không dựng được, in một dòng NO SOLUTION.

Hai độ dài được coi là bằng nhau nếu chênh lệch nhỏ hơn \(0.001\). Có thể dùng mọi định dạng số thực tiêu chuẩn.

Ví dụ

4
7
4
5
4

0.5 2.5
7.5 2.5
4.5 6.5
0.5 6.5