Bai on luyen 2

Câu 1: (6 điểm) Serpent - “Số rắn hai đầu”  “Số rắn hai đầu” là một số nguyên dương N sao cho: khi thêm hai chữ số a, b vào hai đầu số N ấy (theo dạng 
) sẽ được số mới có giá trị nâng lên 99 lần. Tức là:                         
            Cho trước hai chữ số nguyên a, b (0 ≤ a, b ≤ 9). Tìm “Số rắn hai đầu” N?             Tổ chức dữ liệu:
Dữ liệu vào: từ tập tin Serpent.inp gồm 2 số a, b cách nhau một dấu cách.
Dữ liệu ra: là tập tin Serpent.out chứa số N cần tìm. Trong trường hợp có nhiều hơn một số N thỏa mãn, hãy đưa ra số bé nhất.
Cho biết với dữ liệu vào, luôn tồn tại kết quả. Ví dụ:
Serpent.inp
Serpent.out

8 1
9

1 4
11236

8 5
8988764045

& Giải thích:
9 × 99 = 891                  11236 × 99 = 1112364                8988764045 × 99 = 889887640455
Câu 2: (7 điểm) Factory - "Nhà máy"            Nhà máy Intel cần sản xuất dây chuyền mainboard máy tính. Có N công việc; Công việc i cần ai ngày công. Mỗi công đoạn sản phẩm là kết hợp 2 công việc liên tiếp lại với nhau thành một công việc với chi phí bằng tổng ngày công 2 công việc đó. Bạn hãy giúp nhà máy ghép N công việc đó lại thành từng công đoạn sao cho tổng chi phí công đoạn là nhỏ nhất. Tổ chức dữ liệu: Dữ liệu vào: Trong file FACTORY.INP có dạng: + Dòng đầu ghi số N (N<101) là số công việc. + Dòng thứ 2 gồm N số nguyên là số ngày công của N công việc. (
); Dữ liệu ra: ghi vào file FACTORY.OUT có dạng: + Dòng đầu ghi tổng chi phí nhỏ nhất tìm được. + Các dòng tiếp theo, mỗi dòng là một công đoạn kết hợp 2 công việc liên tiếp có số ngày công tương ứng của 2 công việc đó. Ví dụ:
FACTORY.INP
FACTORY.OUT

5 4 1 2 7 5
41 1    2 4    3 7    5 7    12

Giải thích: Vì 41 = 3 + 7 + 12 + 19 Câu 3: (7 điểm) Max-polygon - "Đa giác lồi cực đại" Cho N điểm trên mặt phẳng tọa độ, các điểm có tọa độ là những số tự nhiên. Ta định nghĩa sau: + Một đa giác lồi “cực đại” là đa giác lồi có các đỉnh là một số điểm trong các điểm đã cho và gốc tọa độ mà số lượng đỉnh nhiều nhất. Gốc tọa độ (0,0), phải là một đỉnh của đa giác lồi này. + Một đa giác là lồi nếu mỗi đọan thẳng có 2 đầu nằm trong đa giác thì đọan thẳng ấy nằm hoàn toàn trong đa giác. Các cạnh liên tiếp của đa giác lồi không được cùng phương. Viết chương trình xác định đa giác lồi “cực đại”. Tổ chức dữ liệu: Dữ liệu vào: từ file văn bản polygon.inp gồm Dòng thứ nhất chứa số tự nhiên N, 2 <= N <= 100, là số điểm cho trước. Mỗi một dòng trong N dòng tiếp theo chứa hai số tự nhiên X và Y, 1<=X<=100, 1<=Y<=100, cách nhau dấu cách, là tọa độ của một điểm đã cho. Kết quả ra: ghi file văn bản polygon.out gồm Dòng đầu tiên là số đỉnh của đa giác lồi “cực đại”. Các dòng tiếp theo, mỗi dòng 2 số thể hiện tọa độ của một đỉnh đa giác lồi “cực đại”. Các đỉnh ghi theo thứ tự chiều quay của kim đồng hồ hoặc ngược lại. (Chú ý: kết quả luôn luôn lớn hơn hoặc bằng 3) ví dụ:
polygon.in1 5 4 2 2 2 2 3 3 2 3 1
polygon.in2 8 10 8 3  9 2 8 2 3 9 2 9 10 10 3 8 10
polygon.in3 10 9 6 1 7 2 2 3 9 8 7 3 2 9 4 3 1 9 7 6 9
 

polygon.ou1 4 3 2 4 2 3 1 0 0
polygon.ou2 8 2 8 3 9 8 10 9 10 10 8 10 3 9 2 0 0
polygon.ou3 7 1 7 3 9 8 7 9 6 9 4 3 1 0 0  
 




 

  Câu 1: (