Tin học trẻ bảng C - Nghệ An

Nhằm duy trì phong trào Tin học trẻ trong đại dịch Covid-19, Tỉnh Đoàn Nghệ An đã quyết định tổ chức kỳ thi Tin học trẻ năm 2021 theo hình thức thi trực tuyến. Sau khi các đơn vị Huyện Đoàn gửi danh sách thí sinh tham gia, Tỉnh Đoàn đã xây dựng một chương trình quản lí thay vì dùng bảng tính Excel như mọi năm. Phần mềm đã nhập số liệu thí sinh tham gia của \(n\) Huyện Đoàn, Huyện Đoàn thứ \(i (1\le i \le n)\) có số lượng thí sinh tham gia các bảng \(A, B, C, E\) tương ứng là \(a_i, b_i, c_i, e_i\).

Ngoài ra, để đánh giá sơ bộ phong trào Tin học trẻ của từng Huyện cũng như của cả Tỉnh, phần mềm cũng đã tính toán, thống kê nhiều số liệu, ví dụ như các số liệu \(\overline{A}, \overline{B}, \overline{C}, \overline{E}\) tương ứng là trung bình số lượng thí sinh tham gia bảng từng bảng \(A, B, C, E\), hay số \(S\) là số lượng Huyện Đoàn mà với từng bảng đều có số lượng thí sinh tham gia lớn hơn trung bình số lượng thí sinh tham gia trong bảng đó.

Yêu cầu: Cho bộ số \(a_i, b_i, c_i, e_i\) , hãy tính số \(S\) giống như trong phần mềm được mô tả ở trên.

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu tiên chứa số nguyên dương \(n (n \le 100)\) là số Huyện Đoàn;
• Dòng thứ \(i (1 \le i \le n)\) trong \(n\) dòng tiếp theo chứa bốn số nguyên không âm \(a_i, b_i, c_i, e_i\) \((a_i, b_i, c_i, e_i \le 100)\).

Output

• Ghi ra thiết bị ra chuẩn gồm một số nguyên là số Huyện Đoàn mà với từng bảng đều có số lượng thí sinh tham gia lớn hơn trung bình số lượng thí sinh tham gia trong bảng đó.

Example

3
5 5 5 5
6 6 6 0
6 6 6 6

1

Công ty Alpha giới thiệu siêu máy tính có khả năng thực hiện được một lượng tính toán rất lớn. Để chứng minh sức mạnh của siêu máy tính, công ty đã cho máy tính thực hiện tính giá trị sau: \((a^m)^{b^n}\), trong đó các số \(a, m, b, n\) là các số nguyên dương. Để kiểm tra kết quả do máy tính thực hiện, Hồng muốn xây dựng chương trình tính phần dư trong phép chia \((a^m)^{b^n}\) cho \(K\).

Yêu cầu: Cho các bộ số nguyên dương \(a, m, b, n, K\), tính phần dư trong phép chia \((a^m)^{b^n}\) cho \(K\).

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu tiên chứa số nguyên dương \(T (1 \leq T \leq 1000)\) là số bộ dữ liệu;
• Dòng thứ \(i (1 \leq i \leq T)\) trong \(T\) dòng tiếp theo chứa năm số nguyên dương \(a, m, b, n, K\).

Output

• Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, dòng thứ \(i (1\leq i \leq T)\) là phần dư trong phép chia \((a^m)^{b^n}\) cho \(K\) tương ứng với bộ dữ liệu thứ trong dữ liệu vào.

Scoring

• Subtask #1 (\(20\%\) số điểm): \(a, m \leq 10; b = 1; n = 1; K \leq 10^5\);
• Subtask #2 (\(20\%\) số điểm): \(a, m \leq 10^6; b = 1; n = 1; K \leq 10^5\);
• Subtask #3 (\(20\%\) số điểm): \(a, m \leq 10^9; b = 1; n = 1; K \leq 10^5\);
• Subtask #4 (\(20\%\) số điểm): \(a, m \leq 10^9; b, n \leq 10^9; K \leq 10^5\);
• Subtask #5 (\(20\%\) số điểm): \(a, m \leq 10^9; b, n \leq 10^9; K \leq 10^7\);

Example

2
2 10 1 1 10
2 2 5 1 2000

4
1024

Công ty cung cấp dịch vụ mạng Alpha vừa thiết lập một mạng truyền thông bao gồm \(n\) nút và \(m\) kênh nối trực tiếp hai chiều giữa hai nút. Các nút được đánh số từ \(1\) đến \(n\), các kênh nối được đánh số từ \(1\) đến \(m\). Kênh nối thứ \(i\) cho phép truyền tin hai chiều từ nút \(u_i\) tới nút vi có độ trễ là \(c(u_i , v_i)\) và với chi phí duy trì là \(100 \times c(u_i, v_i)\). Có không quá một kênh truyền tin từ một nút đến một nút khác. Một đường truyền tin từ nút s đến nút t được biểu diễn dưới dạng một dãy liên tiếp các chỉ số của các nút, xuất phát từ s và kết thúc tại t, trong đó hai nút liên tiếp trong dãy có kênh nối trực tiếp giữa chúng. Độ trễ của đường truyền tin được định nghĩa là tổng độ trễ của các kênh nối trực tiếp trên đường truyền tin đó. Mạng của công ty là liên thông, nghĩa là luôn có đường truyền tin giữa hai máy bất kỳ.

Công ty lựa chọn ba nút \(x, y, z (1\le x < y < z \le n)\) làm ba nút nguồn chứa nguồn dữ liệu, các nút còn lại gọi là nút xử lý. Khi đó, mỗi nút xử lý i sẽ chọn đường truyền có độ trễ nhỏ nhất trong số ba đường truyền với độ trễ nhỏ nhất từ ba nguồn \(x, y\) hoặc \(z\) đến nó làm đường truyền mà theo đó nó sẽ nhận dữ liệu. Ta gọi độ trễ của đường truyền mà theo đó nút xử lý \(i\) nhận dữ liệu là độ trễ của nút này và ký hiệu là \(d_i\).

Sau một thời gian hoạt động, công ty nhận thấy có thể loại bỏ một số kênh truyền mà các giá trị độ trễ của các nút xử lý là không thay đổi. Vì vậy, công ty muốn tìm cách loại bỏ một số kênh nối sao cho tổng chi phí duy trì các kênh còn lại là nhỏ nhất mà vẫn đảm bảo các giá trị độ trễ của các nút xử lý là không thay đổi.

Yêu cầu: Cho biết thông tin về \(m\) kênh truyền tin và \(k\) giả định chọn ba nút nguồn. Với mỗi giả định chọn ba nút nguồn, hãy tìm phương án loại bỏ một số kênh truyền tin trong số \(m\) kênh truyền tin sao cho tổng chi phí duy trì các kênh còn lại là nhỏ nhất mà vẫn đảm bảo các giá trị độ trễ của các nút xử lý là không thay đổi.

Input

Vào từ thiết bị vào chuẩn:

• Dòng thứ nhất chứa ba số nguyên dương \(n, m, k\);
• Dòng thứ \(i\) trong số \(m\) dòng tiếp theo chứa ba số nguyên dương \(u_i , v_i , c_i\) cho biết thông tin về kênh truyền tin thứ \(i (i = 1, 2, ..., m)\). Giả thiết: \(u_i \ne v_i , c_i \le 10^9\).
• Dòng thứ j trong số k dòng tiếp theo chứa ba số nguyên \(x_j , y_j , z_j (1\le x_j < y_j < z_j \le n)\) mô tả giả định thứ \(j (j = 1, 2, ..., k)\).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra thiết bị ra chuẩn \(k\) dòng, dòng thứ \(j\) là tổng chi phí nhỏ nhất của phương án tìm
  được tương ứng với giả định thứ \(j\).

Scoring

• Subtask #1 (\(40\%\) số điểm): \(n \le 50, k \le 100\);
• Subtask #2 (\(60\%\) số điểm): \(n \le 500, m \le 10000, k \le 10000\).

Example

6 6 2
1 2 1
1 3 1
2 3 1
1 4 5
2 5 5
3 6 5
1 2 3
1 5 6

1500
700

Để khám phá đặc tính di chuyển của loài kiến, Hồng đã thiết kế một khay kích thước \(m \times n\) ô. Khay gồm \(m\) hàng ngang và \(n\) cột dọc, các hàng được đánh số từ \(1\) đến \(m\) từ trên xuống dưới, các cột dọc được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm ở hàng ngang \(i\) và cột dọc \(j\) được gọi là ô \((i, j)\).

Một lần thí nghiệm được thực hiện như sau: Cho một kiến đi vào khay là một trong các ô của cột dọc \(1\), sau đó kiến có thể chọn một trong các ô chung cạnh với ô hiện tại để di chuyển sang (có thể đi lại những ô đã đi). Thí nghiệm kết thúc nếu kiến đi ra khỏi khay từ một trong các ô nằm ở biên của khay. Khay có khả năng ghi nhận lại vị trí các ô mà kiến đã đi để phục vụ cho việc phân tích đặc tính di chuyển của loài kiến.

Hai lần thí nghiệm được gọi là cho kết quả khác nhau nếu tồn tại một ô trong thí nghiệm này mà kiến có đi tới nhưng trong thí nghiệm kia kiến không đi tới. Hồng muốn tính số \(S\) là số lượng kết quả thí nghiệm khác nhau có thể đạt được.

Yêu cầu: Cho \(m, n\) hãy tính phần dư \(S\) của chia cho \(10^9+7\).

Input

• Vào từ thiết bị nhập chuẩn gồm một dòng chứa hai số nguyên \(m, n\).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số là phần dư của \(S\) chia cho \(10^9 + 7\).

Scoring

• Subtask #1 (\(10\%\) số điểm): \(m = 1; n \leq 10^9\)
• Subtask #2 (\(20\%\) số điểm): \(m \leq 2; n \leq 10\)
• Subtask #3 (\(20\%\) số điểm): \(m = 2; n \leq 10^3\)
• Subtask #4 (\(20\%\) số điểm): \(m = 3; n \leq 10^3\)
• Subtask #5 (\(20\%\) số điểm): \(m \leq 5; n \leq 10^3\)
• Subtask #6 (\(10\%\) số điểm): \(m \leq 5; n \leq 10^9\)

Example

1 2

2

2 1

3

2 2

10