From 15b38076cc08d89024864252e99e10fe6f597196 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Wed, 4 Jan 2017 11:21:47 +0700 Subject: Add 9/TP-HN-2014 --- "12/TP-ThanhHo\303\241-2009/README.md" | 2 +- 9/TP-HN-2014/README.md | 159 +++++++++++++++++++++++++++++++++ 9/TP-HN-2014/cau1.pas | 46 ++++++++++ 9/TP-HN-2014/cau2.pas | 31 +++++++ 9/TP-HN-2014/cau3.pas | 59 ++++++++++++ 9/TP-HN-2014/cau4.pas | 89 ++++++++++++++++++ 6 files changed, 385 insertions(+), 1 deletion(-) create mode 100644 9/TP-HN-2014/README.md create mode 100644 9/TP-HN-2014/cau1.pas create mode 100644 9/TP-HN-2014/cau2.pas create mode 100644 9/TP-HN-2014/cau3.pas create mode 100644 9/TP-HN-2014/cau4.pas diff --git "a/12/TP-ThanhHo\303\241-2009/README.md" "b/12/TP-ThanhHo\303\241-2009/README.md" index b64db6b..f5d69a1 100644 --- "a/12/TP-ThanhHo\303\241-2009/README.md" +++ "b/12/TP-ThanhHo\303\241-2009/README.md" @@ -16,7 +16,7 @@ Thời gian: 180 phút | 2 | BAI2.PAS | BAI2.INP | BAI2.OUT | 5 | | 3 | BAI3.PAS | BAI3.INP | BAI3.OUT | 4 | | 4 | BAI4.PAS | BAI4.INP | BAI4.OUT | 3 | -| 4 | BAI5.PAS | BAI5.INP | BAI5.OUT | 3 | +| 5 | BAI5.PAS | BAI5.INP | BAI5.OUT | 3 | Giới hạn thời gian cho mỗi test là 3 giây. diff --git a/9/TP-HN-2014/README.md b/9/TP-HN-2014/README.md new file mode 100644 index 0000000..8a21e84 --- /dev/null +++ b/9/TP-HN-2014/README.md @@ -0,0 +1,159 @@ +# KỲ THI HỌC SINH GIỎI THÀNH PHỐ LỚP 9 NĂM HỌC 2013 - 2014 + +SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI + +Môn thi: TIN HỌC + +Ngày thi: 31/03/2014 + +Thời gian làm bài: 150 phút + +## Tổng quan bài thi + +| Câu | Tệp chương trình | Tệp dữ liệu | Tệp kết quả | Điểm | +| :---: | :--------------: | :---------: | :---------: | :---: | +| 1 | CAU1.PAS | CAU1.INP | CAU1.OUT | 6 | +| 2 | CAU2.PAS | CAU2.INP | CAU2.OUT | 6 | +| 3 | CAU3.PAS | CAU3.INP | CAU3.OUT | 4 | +| 4 | CAU4.PAS | CAU4.INP | CAU4.OUT | 4 | + +## Câu 1: Hiệu hai phân số + +Cho bốn số nguyên dương a, b, c, d, mỗi số có giá trị không vượt quá +105. + +### Yêu cầu + +Tìm hai số nguyên x, y để phân số tối giản x/y và bằng +hiệu của hai phân số a/b - c/d, +trong đó y > 0. + +### Dữ liệu + +* Dòng đầu chứ hai số a, b; +* Dòng thứ hai chứa hai số c, d. + +### Kết quả + +Hai số x và y trên cùng một dòng, cách nhau một dấu cách. + +### Ví dụ + +| CAU1.INP | CAU1.OUT | +| ----------- | :------: | +| 1 6
5 12 | -1 4 | + +#### Giải thích + +1/6 - 5/12 = +-1/4 + +## Câu 2: Đua Robot + +Trong cuộc đua tốc độc có n Robot tham gia được đánh số từ 1 đến n. Đường đua +có độ dài d (mét). Robot thứ i (1 ≤ i ≤ n) có vận tốc đua không đổi là +vi (mét/phút). Các Robot xuất phát theo thứ tự từ 1 đến n và cách +nhau 1 phút. Robot i gọi là vượt Robot j (1 ≤ j ≤ n) nếu i xuất phát sau j và +về đích trước j. + +### Yêu cầu + +Xác định số lần vượt nhau của tất cả các Robot trong cuộc đua. + +### Dữ liệu + +* Dòng đầu chứa hai số nguyên dương n và d, n ≤ 103, + d ≤ 109; +* Dòng tiếp theo chứa n số nguyên dương vi, 1 ≤ i ≤ n, mỗi số không + vượt quá 1000. + +### Kết quả + +Số lần vượt nhau của tất cả các Robot trong cuộc đua. + +### Ví dụ + +| CAU2.INP | CAU2.OUT | +| ----------------- | :------: | +| 5 10
1 2 4 3 8 | 7 | + +#### Giải thích + +* Robot 2 vượt Robot 1; +* Robot 3 vượt Robot 1, 2; +* Robot 4 vượt Robot 1; +* Robot 5 vượt Robot 1, 2, 4. + +Tổng số lần vượt là 7. + +## Câu 3: Tìm kiếm trong xâu + +Cho xâu s có độ dài tối đa 250 kí tự gồm chữ cái in hoa, in thường và chữ số. + +### Yêu cầu + +Đếm xem trong xâu s có bao nhiêu kí tự khác nhau và tìm độ dài đoạn kí tự liên +tiếp dài nhất trong xâu s tạo thành xâu x đối xứng. Xâu kí tự x được gọi là đối +xứng nếu đọc từ trái sang phải hoặc ngược lại ta đều thu được xâu như nhau. + +### Dữ liệu + +Một dòng duy nhất chứa xâu s. + +### Kết quả + +* Dòng thứ nhất ghi số lượng kí tự khác nhau trong s; +* Dòng thứ hai ghi độ dài xâu x tìm được. + +### Ví dụ + +| CAU3.INP | CAU3.OUT | +| :---------------: | :------: | +| AbcabA12321ABCcba | 9
7 | + +#### Giải thích + +Các kí tự khác nhau gồm: `1`, `2`, `3`, `A`, `B`, `C`, `a`, `b`, `c`. + +Xâu X tìm được là: `A12321A`. + +## Câu 4: Trồng cây + +Dọc theo một tuyến phố thẳng có n vị trí kế tiếp nhau để trồng cây đánh số từ 1 +đến n. Hiện tại chỉ có vị trí k (1 ≤ k ≤ n) đã trồng một cây có độ cao +ak, còn các vị trí khác để trống. Theo dự kiến, người ta sẽ trồng +cây có độ cao ai tại vị trí thứ i (1 ≤ i ≤ n, i ≠ k). Tuy nhiên, để +tăng vẻ đẹp cho hàng cây, người ta muốn tìm một phương án sắp xếp các cây cần +trồng vào các vị trí thích hợp (trừ vị trí k) sao cho tổng tất cả các độ chênh +lệch của hai cây trồng liền nhau là nhỏ nhất. Độ chênh lệch của hai cây là giá +trị tuyệt đối hiệu độ cao hai cây. + +### Yêu cầu + +Tìm giá trị nhỏ nhất t của tổng tất cả các độ chênh lệch của hai cây trồng liền +nhau. + +### Dữ liệu + +* Dòng đầu chứa hai số nguyên dương n và d, n ≤ 103, 1 ≤ k ≤ n; +* Dòng sau chứa n số nguyên dương ai, 1 ≤ i ≤ n, là độ cao của cây + thứ i theo dự kiến. Mỗi số đều không vượt quá 106. + +### Kết quả + +Số t tìm được. + +### Ví dụ + +| CAU4.INP | CAU4.OUT | +| ---------------- | :------: | +| 5 2
7 3 4 2 6 | 5 | + +#### Giải thích + +* Vị trí 1 trồng cây có độ cao 2; +* Vị trí 3 trồng cây có độ cao 4; +* Vị trí 4 trồng cây có độ cao 6; +* Vị trí 5 trồng cây có độ cao 7. + +Tổng độ chênh lệch nhỏ nhất là 5. diff --git a/9/TP-HN-2014/cau1.pas b/9/TP-HN-2014/cau1.pas new file mode 100644 index 0000000..466d4c4 --- /dev/null +++ b/9/TP-HN-2014/cau1.pas @@ -0,0 +1,46 @@ +var + f: text; + a, b, g: int64; + c, d: smallint; + + +function gcd(x, y: int64): int64; + var z: int64; + + begin + while y <> 0 do + begin + z := y; + y := x mod y; + x := z + end; + + gcd := a + end; + + +begin + assign(f, 'CAU1.INP'); + reset(f); + read(f, a, b, c, d); + close(f); + + a := a * d - c * b; + b := b * d; + + g := gcd(a, b); + + a := a div g; + b := b div g; + + if b < 0 then + begin + a := -a; + b := -b + end; + + assign(f, 'CAU1.OUT'); + rewrite(f); + writeln(f, a, ' ', b); + close(f) +end. diff --git a/9/TP-HN-2014/cau2.pas b/9/TP-HN-2014/cau2.pas new file mode 100644 index 0000000..aed61ed --- /dev/null +++ b/9/TP-HN-2014/cau2.pas @@ -0,0 +1,31 @@ +var + f: text; + n, i, j: smallint; + d: longint; + v: array of smallint; + t: array of real; + +begin + assign(f, 'CAU2.INP'); + reset(f); + readln(f, n, d); + setlength(v, n); + for i := 0 to n - 1 do + read(f, v[i]); + close(f); + + setlength(t, n); + for i := 0 to n - 1 do + t[i] := i + d / v[i]; + + d := 0; + for i := 1 to n - 1 do + for j := 0 to i - 1 do + if t[i] < t[j] then + inc(d); + + assign(f, 'CAU2.OUT'); + rewrite(f); + writeln(f, d); + close(f) +end. diff --git a/9/TP-HN-2014/cau3.pas b/9/TP-HN-2014/cau3.pas new file mode 100644 index 0000000..1785da9 --- /dev/null +++ b/9/TP-HN-2014/cau3.pas @@ -0,0 +1,59 @@ +var + f: text; + s: string; + c: char; + a: array of byte; + i, j: byte; + tmp: byte = 0; + + +function palin( + s: string; + l, h: byte +): boolean; + + begin + while l <= h do + begin + if s[l] <> s[h] then + exit(false); + + inc(l); + dec(h); + end; + + palin := true + end; + + + +begin + assign(f, 'CAU3.INP'); + reset(f); + readln(f, s); + close(f); + + setlength(a, 256); + for i := 0 to 255 do + a[i] := 0; + + for c in s do + inc(a[ord(c)]); + + for i in a do + if i > 0 then + inc(tmp); + + assign(f, 'CAU3.OUT'); + rewrite(f); + writeln(f, tmp); + + tmp := 0; + for i := 1 to length(s) - 1 do + for j := i + tmp to length(s) do + if palin(s, i, j) then + tmp := j - i + 1; + + writeln(f, tmp); + close(f) +end. diff --git a/9/TP-HN-2014/cau4.pas b/9/TP-HN-2014/cau4.pas new file mode 100644 index 0000000..1e79c04 --- /dev/null +++ b/9/TP-HN-2014/cau4.pas @@ -0,0 +1,89 @@ +var + f: text; + n, k, i: smallint; + a, c: array of longint; + b: array of boolean; + d: longint = 0; + + +procedure foo( + idx: smallint; + delta: longint +); + + var + i: smallint; + next: byte = 1; + + begin + if (idx = k + 1) and (k > 0) then + delta := delta + abs(c[k] - c[k - 1]); + + if delta >= d then + exit; + + if idx + 1 = k then + inc(next); + + if idx = n then + begin + d := delta; + exit + end; + + for i := 0 to n - 2 do + if b[i] then + begin + b[i] := false; + c[idx] := a[i]; + + if idx > 0 then + foo(idx + next, delta + abs(c[idx] - c[idx - 1])) + else + foo(idx + next, 0); + + b[i] := true; + c[idx] := 0 + end + end; + + +begin + assign(f, 'CAU4.INP'); + reset(f); + readln(f, n, k); + setlength(a, n); + for i := 0 to n - 1 do + read(f, a[i]); + close(f); + + setlength(c, n); + dec(k); + c[k] := a[k]; + + for i := 0 to k - 1 do + c[i] := 0; + for i := k + 1 to n - 1 do + c[i] := 0; + + for i := 1 to n - 1 do + d := d + abs(a[i] - a[i - 1]); + + for i := k to n - 2 do + a[i] := a[i + 1]; + setlength(a, n - 1); + + setlength(b, n - 1); + for i := 0 to n - 2 do + b[i] := true; + + if k = 0 then + foo(1, 0) + else + foo(0, 0); + + assign(f, 'CAU4.OUT'); + rewrite(f); + writeln(f, d); + close(f) +end. -- cgit 1.4.1