Easy102. ĐƯỜng đi thoát mê cung danh cho nguoi moi bat dau hoc Tin hoc 4

145. MY LAST INVENTION

IOI 3003 diễn ra trong n + 1 ngày, các bài toán của IOI được đánh số từ 1 tới n²+n và được phân bố vào các ngày thi theo lịch sau (mỗi ngày thi có n bài toán):

Ngày 1: Các bài toán từ 1 tới n

Ngày 2: Các bài toán từ n + 1 tới 2n

...

Ngày i: Các bài toán từ (i - 1).n + 1 tới i.n

Ngày n+1: Các bài toán từ n² + 1 tới n²+n

Các bài thi có một trong k dạng, bài thứ j có dạng là r_j (1  r_j  k)

Thể thức thi được thông báo cho mỗi đoàn như sau:

• 
  Mỗi đoàn sẽ có n + 1 học sinh tham gia
  
• 
  Hàng ngày, Ban tổ chức sẽ đưa một học sinh của đoàn đi tham quan thành phố, việc chọn học sinh nào cho đi tham quan là quyền của trưởng đoàn, nhưng phải đảm bảo điều kiện: Cho đến khi IOI kết thúc, học sinh nào của đoàn cũng đã được đi tham quan thành phố. Như vậy mỗi ngày đoàn sẽ còn lại n học sinh tham gia thi, việc giao cho học sinh nào làm bài nào là quyền của phó đoàn nhưng mỗi học sinh chỉ được giao một bài và hai học sinh khác nhau sẽ phải nhận hai bài khác nhau.
  
• 
  Kết thúc IOI, điểm đồng đội của mỗi đoàn sẽ được tính bằng tổng điểm của tất cả các lời giải các bài toán đã cho.
  

• 
  Dòng 1: Chứa hai số n, k (1  n  100; 1  k  1000)
  
• 
  Dòng 2: Chứa n²+n số, số thứ p là r_p.
  
• 
  Các dòng tiếp, mỗi dòng chứa ba số nguyên dương i, j, p cho biết một điều dự đoán của các thầy: học sinh thứ i có thể làm được bài toán dạng j và đạt được số điểm là p (=c[i, j]). (1  p  100)
  

• 
  Dòng 1: Ghi điểm đồng đội mà theo dự đoán đoàn Việt Nam có thể đạt
  
• 
  Tiếp theo là n² + n dòng, dòng thứ i ghi số hiệu học sinh Việt Nam được giao làm bài thứ i.
  

I hope and expect that you will have much success in IOI 2002

146. CÂY KHUNG NHỎ NHẤT

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G.
Dữ liệu: Vào từ file văn bản MST.INP

• 
  Dòng 1: Chứa hai số n, m (1  n  10000; 1  m  15000)
  
• 
  m dòng tiếp theo, dòng thứ i có dạng ba số nguyên u, v, c. Trong đó (u, v) là chỉ số hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó (1  u, v  n; 0  c  10000).
  

Kết quả: Ghi ra file văn bản MST.OUT

• 
  Dòng 1: Ghi trọng số cây khung nhỏ nhất
  
• 
  n - 1 dòng tiếp theo, mỗi dòng ghi chỉ số một cạnh được chọn vào cây khung nhỏ nhất
  

Ví dụ:

MST.INP		MST.OUT
6 9 1 2 1 1 3 1 2 4 1 2 3 2 2 5 1 3 5 1 3 6 1 4 5 2 5 6 2		5 3 7 5 2 1

Giới hạn thời gian: 1 giây

147. MẠNG MÁY TÍNH

Bản đồ mặt bằng của phòng máy tính là một hình chữ nhật nằm trong hệ trục toạ độ Decattes vuông góc có các đỉnh là A(0, 0), B(m, 0), C(m, n) và D(0, n). Tại các điểm toạ độ nguyên nằm trong hình chữ nhật ABCD có một máy tính (như vậy có tất cả (m + 1).(n+1) máy tính) . Một dây cáp mạng là một đoạn cáp nối độ dài 1 đơn vị, như vậy mỗi dây cáp mạng chỉ có thể nối được hai máy tính liền nhau trên cùng hàng hoặc cùng cột. Ban đầu đã có sẵn một số dây cáp mạng nối giữa một số cặp máy tính

Hai máy u và v có thể truyền tin cho nhau nếu giữa chúng có đường truyền tin

(u = x₁, x₂, x₃, ..., x_k = v) (Giữa máy x_i và máy x_i+1 có dây cáp mạng nối chúng)

Hãy nối thêm một số ít nhất các dây cáp mạng sao cho hai máy bất kỳ trong phòng máy có thể truyền tin được cho nhau.
Dữ liệu: Vào từ file văn bản NET.INP

• 
  Dòng 1: Chứa hai số m, n (1  m, n  100);
  
• 
  Các dòng tiếp theo, mỗi dòng chứa thông tin về một đoạn cáp đã có sẵn: gồm 4 số x­­₁, y₁, x₂, y₂ thể hiệu cho cáp mạng nối hai máy ở toạ độ (x₁, y₁) và (x₂, y₂). (|x₁ - x₂| + |y₁-y₂| = 1).
  

Kết quả: Ghi ra file văn bản NET.OUT

• 
  Dòng 1: Ghi số cáp mạng cần nối thêm (c)
  
• 
  c dòng tiếp theo, mỗi dòng ghi 4 số u₁, v₁, u₂, v₂ cho biết cần thêm cáp nối giữa hai máy ở toạ độ (u₁, v₁) và (u₂, v₂)
  

Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách.
Ví dụ:

NET.INP	NET.OUT
2 3 0 0 0 1 1 0 2 0 1 0 1 1 2 0 2 1 0 1 1 1 1 1 2 1 1 2 2 2 0 3 1 3	4 0 2 1 2 1 2 1 3 1 1 1 2 1 3 2 3

Giới hạn thời gian: 1 giây

Каталог: Portals
Portals -> Phan Chau Trinh High School one period test no 2 Name: English : 11- time : 45 minutes Class: 11/ Code: 211 Chọn từ hoặc cụm từ thích hợp A, B, C, d để điền vào chỗ trống trong đoạn văn sau
Portals -> PHẦn I: thông tin cơ BẢn về ĐẠi hàn dân quốc và quan hệ việt nam-hàn quốc I- các vấN ĐỀ chung
Portals -> Năng suất lao động trong nông nghiệp: Vấn đề và giải pháp Giới thiệu
Portals -> LẤy ngưỜi học làm trung tâM
Portals -> BÀi tậP Ôn lưu huỳnh hợp chất lưu huỳnh khí sunfurơ so
Portals -> TỜ trình về việc ban hành mức thu phí tham gia đấu giá quyền sử dụng đất
Portals -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập – Tự do – Hạnh phúc
Portals -> GIẤY Ủy quyền tham dự Đại hội đồng Cổ đông thường niên năm 2016

tải về 438.29 Kb.

Chia sẻ với bạn bè của bạn: