Olympic tin học sinh viên lần thứ XV, 2006 Khối thi: Đồng đội chuyên

OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XV, 2006 Khối thi: Đồng đội chuyên Thời gian làm bài: 180 phút Ngày thi: 07-05-2006

Trong kỳ thi vấn đáp học sinh phải trả lời các câu hỏi của thầy giáo. Nếu trả lời đúng, thầy giáo đánh dấu bằng ký tự ‘C’ (Correct), nếu sai thì đánh dấu ‘N’ (No Correct). Khi học sinh trả lời đúng, thầy sẽ đưa ra câu hỏi tiếp theo khó hơn câu trước, còn khi trả lời sai thầy sẽ cho câu hỏi mới dễ hơn. Sau khi thi xong, kết quả của mỗi học sinh là một xâu các ký tự ‘C’ và ‘N’. Điểm số của học sinh sẽ được tính như sau: Với các câu trả lời sai học sinh không được điểm, với mỗi câu trả lời đúng học sinh nhận được điểm bằng số lần trả lời đúng liên tiếp từ câu trả lời này trở về trước. Ví dụ, nếu kết quả là ‘CCNNCNNCCC’, thì điểm số sẽ là 1+2+0+1+0+0+1+2+3 = 10.

• 
  Dòng đầu tiên chứa số nguyên T - số lượng Tests,
  
• 
  Mỗi dòng trong T dòng sau chứa một xâu kết quả thi.
  

SCORE.INP		Kết quả
5 CCNNCNNCCC CCNNCCNNCC CNCNCNCNCNCNCN CCCCCCCCCC CCCCNCCCCNCCCCN		10 9 7 55 30

Cho một lưới ô vuông gồm n dòng và n cột. Các dòng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i,j). Trên lưới đã cho, khoảng cách từ ô (i,j) tới ô (p,q) được tính bằng: i-p+j-q.Tại ô (i,j) của lưới ghi số nguyên không âm a_ij, i = 1, 2,..., n ; j = 1, 2,..., n. Với mỗi ô (i,j) gọi s_ij là khoảng cách ngắn nhất từ ô (i,j) đến một ô khác 0 . Một ô (i,j) chứa số 0 được gọi là ô thay thế nếu tồn tại duy nhất 1 ô (p,q) thoả:

• 
  a_pq > 0,
  
• 
  Khoảng cách từ ô (i, j) tới ô (p, q) bằng s_ij.
  

• 
  Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤ 10),
  
• 
  Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, trong mỗi nhóm:
  

• 
  Dòng đầu tiên ghi số nguyên dương n (n200).
  
• 
  Dòng thứ i trong số n dòng tiếp theo ghi n số nguyên dương a_i1, a_i2,..., a_in là các số trên dòng thứ i của lưới, i = 1, 2,..., n; a_ij1000000.
  

TABLE.INP		Kết quả
1 3 0 0 0 1 0 2 0 0 0		4

Cho một dãy A gồm N số nguyên. Dãy A có thể được biểu diễn dưới dạng một xâu S theo các quy tắc sau:

• 
  Loại bỏ các phần tử trùng nhau trong dãy chỉ giữ lại một phần tử đại diện,
  
• 
  Các số còn lại được sắp xếp theo thứ tự tăng dần,
  
• 
  Lần lượt liệt kê các số tách nhau bởi dấu phẩy và một dấu cách sau dấu phẩy.
  
• 
  Dãy các số nguyên liên tiếp từ a tới b (a

• 
  Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤ 10),
  

• 
  Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, với mỗi nhóm dòng:
  

• 
  Dòng đầu tiên chứa số nguyên n ( 1 ≤ n ≤ 1 000),
  
• 
  Dòng thứ 2 chứa n số nguyên, các số không nhất thiết phải khác nhau và có giá trị tuyệt đối không vượt quá 2*10⁹.
  

Để dựng lều cho các đội tuyển tham dự kỳ thi Đồng đội, Ban tổ chức Olimpic Sinh viên mua N cây tre được đánh số từ 1 tới N với độ dài tương ứng là: h₁, h₂,..., h_N. Qua việc đăng ký dự thi của các đội Ban tổ chức nhận thấy để làm đủ cho mỗi đội một lều cần phải có K cọc với độ dài bằng nhau và để tiện cho việc cưa độ dài của cọc là số nguyên. Mỗi chiếc cọc được cắt ra từ một cây nào đó và không được phép nối từ một số đoạn. Để các lều được thoáng mát Ban tổ chức mong muốn độ dài của cọc là lớn nhất.

• 
  Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤10),
  
• 
  Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, với mỗi nhóm:
  
  • 
    Dòng đầu chứa 2 số nguyên dương N và K (1N ≤10000, 1K ≤ 10000),
    
  • 
    Dòng thứ 2 ghi N số nguyên h₁, h₂,..., h_N (0<h_i1000000, 1iN).
    

STICKS.INP		Kết quả
1 2 4 130 270		90

Trên mặt phẳng toạ độ cho một đường gấp khúc khép kín không tự cắt gồm N đỉnh với toạ độ nguyên. Các đỉnh của đường gấp khúc được đánh số liên tiếp từ 1 tới N, trong đó đỉnh thứ i nối với đỉnh thứ i+1 (1iN-1) còn đỉnh thứ N nối với đỉnh 1. Đỉnh thứ i có toạ độ (x_i, y_i).

• 
  Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤ 10),
  
• 
  Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, với mỗi nhóm dòng:
  

• 
  Dòng đầu chứa số N (3N10 000),
  
• 
  Dòng thứ i trong N dòng tiếp theo chứa 2 số x_i và y_i (-1 000 000x_i, y_i1 000 000).
  

POINT.INP		Kết quả
1 6 -1 1 2 8 8 8 12 4 10 -2 7 -3		18

Trên hành tinh Delta có N quốc gia. Các quốc gia được đánh số từ 1 tới N. Mỗi quốc gia đều còn có một số vấn đề bất đồng với không quá 3 quốc gia khác. Để duy trì sự cân bằng, hoà bình trong hành tinh, người ta thành lập một tổ chức với tên gọi là Hội quốc liên. Sắp tới sẽ diễn ra một kỳ họp Đại hội đồng của tổ chức này. Vì số lượng Quốc gia quá nhiều nên Ban tổ chức Đại hội muốn phân các quốc gia này thành hai nhóm để họp vào hai thời điểm khác nhau sao cho trong mỗi nhóm mỗi quốc gia có không quá 1 quốc gia bất đồng với mình.

• 
  Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤ 10),
  
• 
  Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, với mỗi nhóm dòng:
  

• 
  Dòng đầu chứa số N là số lượng quốc gia trên hành tinh Delta (1N8000).
  
• 
  Dòng thứ i trong N dòng tiếp theo chứa các không quá 4 số: số đầu là số lượng các quốc gia có bất đồng với quốc gia thứ i, tiếp theo là chỉ số của các quốc gia đó. Nếu quốc gia thứ i không bất đồng với bất kỳ một quốc gia nào thì dòng thứ i chứa duy nhất một số 0.
  

Số -1 nếu không tồn tại phương án phân thành hai nhóm. Trong trường hợp có phương án phân nhóm hãy ghi ra hai dòng:

• 
  Dòng đầu chứa chỉ số các quốc gia trong nhóm thứ nhất.
  
• 
  Dòng thứ 2 chứa chỉ số các quốc gia thuộc nhóm thứ 2.