From 318184dbda0658d8afae6dd3c13a0718382726a1 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Mon, 9 Jan 2017 10:47:37 +0700 Subject: Add NTU/{pali2,editpic}.c and update README.md --- "09/Q-Hu\341\272\277-2014/README.md" | 53 ++++++++++++ "09/Q-Hu\341\272\277-2014/bai1.pas" | 15 ++++ "09/Q-Hu\341\272\277-2014/bai2.pas" | 35 ++++++++ "09/Q-Hu\341\272\277-2014/bai3.pas" | 34 ++++++++ 09/TP-HN-2014/README.md | 159 +++++++++++++++++++++++++++++++++++ 09/TP-HN-2014/cau1.pas | 46 ++++++++++ 09/TP-HN-2014/cau2.pas | 31 +++++++ 09/TP-HN-2014/cau3.pas | 59 +++++++++++++ 09/TP-HN-2014/cau4.pas | 89 ++++++++++++++++++++ "9/Q-Hu\341\272\277-2014/README.md" | 53 ------------ "9/Q-Hu\341\272\277-2014/bai1.pas" | 15 ---- "9/Q-Hu\341\272\277-2014/bai2.pas" | 35 -------- "9/Q-Hu\341\272\277-2014/bai3.pas" | 34 -------- 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 -------------------- NTU/README.md | 4 +- NTU/editpic.c | 30 +++++++ NTU/pali2.c | 68 +++++++++++++++ README.md | 20 ++--- 22 files changed, 630 insertions(+), 534 deletions(-) create mode 100644 "09/Q-Hu\341\272\277-2014/README.md" create mode 100644 "09/Q-Hu\341\272\277-2014/bai1.pas" create mode 100644 "09/Q-Hu\341\272\277-2014/bai2.pas" create mode 100644 "09/Q-Hu\341\272\277-2014/bai3.pas" create mode 100644 09/TP-HN-2014/README.md create mode 100644 09/TP-HN-2014/cau1.pas create mode 100644 09/TP-HN-2014/cau2.pas create mode 100644 09/TP-HN-2014/cau3.pas create mode 100644 09/TP-HN-2014/cau4.pas delete mode 100644 "9/Q-Hu\341\272\277-2014/README.md" delete mode 100644 "9/Q-Hu\341\272\277-2014/bai1.pas" delete mode 100644 "9/Q-Hu\341\272\277-2014/bai2.pas" delete mode 100644 "9/Q-Hu\341\272\277-2014/bai3.pas" delete mode 100644 9/TP-HN-2014/README.md delete mode 100644 9/TP-HN-2014/cau1.pas delete mode 100644 9/TP-HN-2014/cau2.pas delete mode 100644 9/TP-HN-2014/cau3.pas delete mode 100644 9/TP-HN-2014/cau4.pas create mode 100644 NTU/editpic.c create mode 100644 NTU/pali2.c diff --git "a/09/Q-Hu\341\272\277-2014/README.md" "b/09/Q-Hu\341\272\277-2014/README.md" new file mode 100644 index 0000000..2da9e8e --- /dev/null +++ "b/09/Q-Hu\341\272\277-2014/README.md" @@ -0,0 +1,53 @@ +# THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ + +UBND THÀNH PHỐ HUẾ + +PHÒNG GIÁO DỤC VÀ ĐÀO TẠO + +MÔN TIN HỌC - NĂM HỌC: 2013-2014 + +Thời gian: 120 phút (Không kể thời gian giao đề) + +## Bài 1 (3 điểm) + +Hai số tự nhiên `n`, `m` được gọi là nguyên tố tương đương nếu chúng có chung +các ước số nguyên tố. + +Hãy viết chương trình nhập vào hai số `n`, `m` và kiểm +tra chúng có là nguyên tố tương đương với nhau hay không. + +**Ví dụ:** Số 75 và số 15 là nguyên tố tương đương vì chúng có cùng các ước số +nguyên tố là 3 và 5. + +## Bài 2 (3 điểm) + +Cho hệ phương trình bậc nhất hai ẩn: + + ax + by = c + a'x + b'y = c' + +Hãy viết chương trình giải hệ phương trình trên, đồng thời xác định vị trí +tương đối của hai đường thẳng `d: ax + by = c` và `d': a'x + b'y =c'` đã tạo +nên hệ phương trình. + +## Bài 3 (4 điểm) + +Cho hai xâu `X`, `Y` chứa các kí tự số từ 0 đến 9 và không dài quá 250 kí tự. + +Hãy viết chương trình tạo ra xâu `ST` thoả mãn các điều kiện sau: + +* Gồm các kí tự số vừa có mặt ở xâu `X`, vừa có mặt ở xâu `Y` +* Các kí tự số trong xâu `ST` chỉ xuất hiện duy nhất một lần +* Giá trị xâu `ST` nhận được là một số đạt giá trị lớn nhất + +Dữ liệu vào cho bởi file `INPUT.INP` chứa giá trị xâu `X` và xâu `Y`, mỗi xâu +nằm trên một dòng. + +Dữ liệu ra chứa ở file `OUTPUT.OUT` là số lớn nhất nhận được. + +**Ví dụ:** + +| INPUT.INP | OUTPUT.OUT | +| --------- | ---------- | +| 19012304 | 43210 | +| 034012 | | diff --git "a/09/Q-Hu\341\272\277-2014/bai1.pas" "b/09/Q-Hu\341\272\277-2014/bai1.pas" new file mode 100644 index 0000000..7bd0d92 --- /dev/null +++ "b/09/Q-Hu\341\272\277-2014/bai1.pas" @@ -0,0 +1,15 @@ +var + n, m, p: qword; + +begin + read(n, m); + + while m <> 0 do + begin + p := n mod m; + n := m; + m := p + end; + + writeln(n <> 1) +end. diff --git "a/09/Q-Hu\341\272\277-2014/bai2.pas" "b/09/Q-Hu\341\272\277-2014/bai2.pas" new file mode 100644 index 0000000..172137d --- /dev/null +++ "b/09/Q-Hu\341\272\277-2014/bai2.pas" @@ -0,0 +1,35 @@ +var + a, b, c, e, p, k, tmp: real; + +function det(a, b, c, d: real): real; + begin + exit(a * d - b * c) + end; + +begin + read(a, b, c, e, p, k); + + tmp := det(a, b, e, p); + + if tmp <> 0 then + begin + writeln('x = ', (det(c, b, k, p) / tmp):0:6); + writeln('y = ', (det(a, c, e, k) / tmp):0:6); + writeln('Hai đường thẳng cắt nhau.') + end + else if c <> k then + begin + writeln('Phương trình vô nghiệm.'); + writeln('Hai đường thẳng song song.') + end + else + begin + if a = 0 then + writeln('y = ', (c / b):0:6) + else if b = 0 then + writeln('x = ', (c / a):0:6) + else + writeln('x = ', (-b / a):0:6, 'y + ', (c / a):0:6); + writeln('Hai đường thẳng trùng nhau.') + end; +end. diff --git "a/09/Q-Hu\341\272\277-2014/bai3.pas" "b/09/Q-Hu\341\272\277-2014/bai3.pas" new file mode 100644 index 0000000..91fc05f --- /dev/null +++ "b/09/Q-Hu\341\272\277-2014/bai3.pas" @@ -0,0 +1,34 @@ +var + x, y: string; + f: text; + a: array[0 .. 9] of shortint; + b: shortint; + c: char; + +begin + assign(f, 'INPUT.INP'); + reset(f); + readln(f, x); + readln(f, y); + close(f); + + fillchar(a, 0, sizeof(a)); + + for c in x do + a[ord(c) - 48] := 1; + + for c in y do + begin + b := ord(c) - 48; + if a[b] = 1 then + a[b] := 2 + end; + + assign(f, 'OUTPUT.OUT'); + rewrite(f); + for b := 9 downto 0 do + if a[b] = 2 then + write(f, b); + writeln(f); + close(f) +end. diff --git a/09/TP-HN-2014/README.md b/09/TP-HN-2014/README.md new file mode 100644 index 0000000..8a21e84 --- /dev/null +++ b/09/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/09/TP-HN-2014/cau1.pas b/09/TP-HN-2014/cau1.pas new file mode 100644 index 0000000..466d4c4 --- /dev/null +++ b/09/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/09/TP-HN-2014/cau2.pas b/09/TP-HN-2014/cau2.pas new file mode 100644 index 0000000..aed61ed --- /dev/null +++ b/09/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/09/TP-HN-2014/cau3.pas b/09/TP-HN-2014/cau3.pas new file mode 100644 index 0000000..1785da9 --- /dev/null +++ b/09/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/09/TP-HN-2014/cau4.pas b/09/TP-HN-2014/cau4.pas new file mode 100644 index 0000000..1e79c04 --- /dev/null +++ b/09/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. diff --git "a/9/Q-Hu\341\272\277-2014/README.md" "b/9/Q-Hu\341\272\277-2014/README.md" deleted file mode 100644 index 2da9e8e..0000000 --- "a/9/Q-Hu\341\272\277-2014/README.md" +++ /dev/null @@ -1,53 +0,0 @@ -# THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ - -UBND THÀNH PHỐ HUẾ - -PHÒNG GIÁO DỤC VÀ ĐÀO TẠO - -MÔN TIN HỌC - NĂM HỌC: 2013-2014 - -Thời gian: 120 phút (Không kể thời gian giao đề) - -## Bài 1 (3 điểm) - -Hai số tự nhiên `n`, `m` được gọi là nguyên tố tương đương nếu chúng có chung -các ước số nguyên tố. - -Hãy viết chương trình nhập vào hai số `n`, `m` và kiểm -tra chúng có là nguyên tố tương đương với nhau hay không. - -**Ví dụ:** Số 75 và số 15 là nguyên tố tương đương vì chúng có cùng các ước số -nguyên tố là 3 và 5. - -## Bài 2 (3 điểm) - -Cho hệ phương trình bậc nhất hai ẩn: - - ax + by = c - a'x + b'y = c' - -Hãy viết chương trình giải hệ phương trình trên, đồng thời xác định vị trí -tương đối của hai đường thẳng `d: ax + by = c` và `d': a'x + b'y =c'` đã tạo -nên hệ phương trình. - -## Bài 3 (4 điểm) - -Cho hai xâu `X`, `Y` chứa các kí tự số từ 0 đến 9 và không dài quá 250 kí tự. - -Hãy viết chương trình tạo ra xâu `ST` thoả mãn các điều kiện sau: - -* Gồm các kí tự số vừa có mặt ở xâu `X`, vừa có mặt ở xâu `Y` -* Các kí tự số trong xâu `ST` chỉ xuất hiện duy nhất một lần -* Giá trị xâu `ST` nhận được là một số đạt giá trị lớn nhất - -Dữ liệu vào cho bởi file `INPUT.INP` chứa giá trị xâu `X` và xâu `Y`, mỗi xâu -nằm trên một dòng. - -Dữ liệu ra chứa ở file `OUTPUT.OUT` là số lớn nhất nhận được. - -**Ví dụ:** - -| INPUT.INP | OUTPUT.OUT | -| --------- | ---------- | -| 19012304 | 43210 | -| 034012 | | diff --git "a/9/Q-Hu\341\272\277-2014/bai1.pas" "b/9/Q-Hu\341\272\277-2014/bai1.pas" deleted file mode 100644 index 7bd0d92..0000000 --- "a/9/Q-Hu\341\272\277-2014/bai1.pas" +++ /dev/null @@ -1,15 +0,0 @@ -var - n, m, p: qword; - -begin - read(n, m); - - while m <> 0 do - begin - p := n mod m; - n := m; - m := p - end; - - writeln(n <> 1) -end. diff --git "a/9/Q-Hu\341\272\277-2014/bai2.pas" "b/9/Q-Hu\341\272\277-2014/bai2.pas" deleted file mode 100644 index 172137d..0000000 --- "a/9/Q-Hu\341\272\277-2014/bai2.pas" +++ /dev/null @@ -1,35 +0,0 @@ -var - a, b, c, e, p, k, tmp: real; - -function det(a, b, c, d: real): real; - begin - exit(a * d - b * c) - end; - -begin - read(a, b, c, e, p, k); - - tmp := det(a, b, e, p); - - if tmp <> 0 then - begin - writeln('x = ', (det(c, b, k, p) / tmp):0:6); - writeln('y = ', (det(a, c, e, k) / tmp):0:6); - writeln('Hai đường thẳng cắt nhau.') - end - else if c <> k then - begin - writeln('Phương trình vô nghiệm.'); - writeln('Hai đường thẳng song song.') - end - else - begin - if a = 0 then - writeln('y = ', (c / b):0:6) - else if b = 0 then - writeln('x = ', (c / a):0:6) - else - writeln('x = ', (-b / a):0:6, 'y + ', (c / a):0:6); - writeln('Hai đường thẳng trùng nhau.') - end; -end. diff --git "a/9/Q-Hu\341\272\277-2014/bai3.pas" "b/9/Q-Hu\341\272\277-2014/bai3.pas" deleted file mode 100644 index 91fc05f..0000000 --- "a/9/Q-Hu\341\272\277-2014/bai3.pas" +++ /dev/null @@ -1,34 +0,0 @@ -var - x, y: string; - f: text; - a: array[0 .. 9] of shortint; - b: shortint; - c: char; - -begin - assign(f, 'INPUT.INP'); - reset(f); - readln(f, x); - readln(f, y); - close(f); - - fillchar(a, 0, sizeof(a)); - - for c in x do - a[ord(c) - 48] := 1; - - for c in y do - begin - b := ord(c) - 48; - if a[b] = 1 then - a[b] := 2 - end; - - assign(f, 'OUTPUT.OUT'); - rewrite(f); - for b := 9 downto 0 do - if a[b] = 2 then - write(f, b); - writeln(f); - close(f) -end. diff --git a/9/TP-HN-2014/README.md b/9/TP-HN-2014/README.md deleted file mode 100644 index 8a21e84..0000000 --- a/9/TP-HN-2014/README.md +++ /dev/null @@ -1,159 +0,0 @@ -# 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 deleted file mode 100644 index 466d4c4..0000000 --- a/9/TP-HN-2014/cau1.pas +++ /dev/null @@ -1,46 +0,0 @@ -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 deleted file mode 100644 index aed61ed..0000000 --- a/9/TP-HN-2014/cau2.pas +++ /dev/null @@ -1,31 +0,0 @@ -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 deleted file mode 100644 index 1785da9..0000000 --- a/9/TP-HN-2014/cau3.pas +++ /dev/null @@ -1,59 +0,0 @@ -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 deleted file mode 100644 index 1e79c04..0000000 --- a/9/TP-HN-2014/cau4.pas +++ /dev/null @@ -1,89 +0,0 @@ -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. diff --git a/NTU/README.md b/NTU/README.md index 8261d6c..1caccf3 100644 --- a/NTU/README.md +++ b/NTU/README.md @@ -7,7 +7,7 @@ - [x] writer: [Robot đánh chữ](http://laptrinh.ntu.edu.vn/Problem/Details/3255) - [x] ngto4: [Tổng nguyên tố](http://laptrinh.ntu.edu.vn/Problem/Details/3256) - [x] demso0: [Đếm số không bên phải](http://laptrinh.ntu.edu.vn/Problem/Details/3330) -- [ ] pali2: [Tách chuỗi đối xứng](http://laptrinh.ntu.edu.vn/Problem/Details/3332) +- [x] pali2: [Tách chuỗi đối xứng](http://laptrinh.ntu.edu.vn/Problem/Details/3332) - [x] moco: [Khu mộ cổ](http://laptrinh.ntu.edu.vn/Problem/Details/3343) - [x] dayso6: [Dãy số](http://laptrinh.ntu.edu.vn/Problem/Details/3344) - [x] keba2: [Kết bạn](http://laptrinh.ntu.edu.vn/Problem/Details/3345) @@ -25,6 +25,6 @@ - [ ] hamar: [Hàm số](http://laptrinh.ntu.edu.vn/Problem/Details/5557) - [x] xauduynhat: [Xâu duy nhất](http://laptrinh.ntu.edu.vn/Problem/Details/5573) - [x] chenhlech: [Chênh lệch](http://laptrinh.ntu.edu.vn/Problem/Details/5574) -- [ ] editpic: [Chỉnh sửa ảnh](http://laptrinh.ntu.edu.vn/Problem/Details/5588) +- [x] editpic: [Chỉnh sửa ảnh](http://laptrinh.ntu.edu.vn/Problem/Details/5588) - [ ] cntpalin: [Đếm số Palindrome](http://laptrinh.ntu.edu.vn/Problem/Details/5600) - [x] TutOnEqua: [Tutoring on equations](http://laptrinh.ntu.edu.vn/Problem/Details/5606) diff --git a/NTU/editpic.c b/NTU/editpic.c new file mode 100644 index 0000000..5e34d74 --- /dev/null +++ b/NTU/editpic.c @@ -0,0 +1,30 @@ +#include + +const long long POW2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, + 4096, 8192, 16384, 32768, 65536, 131072, 262144, + 524288, 1048576, 2097152, 4194304, 8388608, 16777216, + 33554432, 67108864, 134217728, 268435456, 536870912}; + +int main() +{ + long long l, w, l0, w0, l1, w1; + char i; + + scanf("%lld %lld", &l, &w); + + for (i = 29; POW2[i] > l || POW2[i] * 4 > w * 5; i--); + l0 = POW2[i]; + w0 = (l0 * 5 >= w * 4) ? w : l0 * 5 / 4; + + for (i = 29; POW2[i] > w || POW2[i] * 4 > l * 5; i--); + w1 = POW2[i]; + l1 = (w1 * 5 >= l * 4) ? l : w1 * 5 / 4; + + l = l0 * w0 - l1 * w1; + if (l > 0 || !l && l0 > l1) + printf("%lld %lld\n", l0, w0); + else + printf("%lld %lld\n", l1, w1); + + return 0; +} diff --git a/NTU/pali2.c b/NTU/pali2.c new file mode 100644 index 0000000..72c9105 --- /dev/null +++ b/NTU/pali2.c @@ -0,0 +1,68 @@ +#include +#include +#include + +short MIN_K, *P; + +void putnc(char *s, short len) +{ + short i; + + for (i = 0; i < len; i++) + putchar(s[i]); + putchar(10); +} + +char palin(char *s, short len) +{ + short i; + + for (i = 0; i < (len + 1) / 2; i++) + if (s[i] != s[len - i - 1]) + return 0; + + return 1; +} + +void foo(char *s, short len, short k, short *p) +{ + short i, j; + + if (palin(s, len)) { + MIN_K = k; + memcpy(P, p, k * sizeof(short)); + return; + } + + if (k >= MIN_K) + return; + + for (i = len - 1; i; i--) + if (palin(s, i)) { + p[k] = p[k - 1] + i; + foo(s + i, len - i, k + 1, p); + } +} + +int main() +{ + short n, i, *p; + char *s; + + scanf("%hd\n", &n); + s = malloc(n + 1); + fgets(s, n + 1, stdin); + + MIN_K = n; + P = malloc(n); + p = malloc(n); + p[0] = 0; + foo(s, n, 1, p); + + printf("%hd\n", MIN_K); + for (i = 1; i < MIN_K; i++) + putnc(s + P[i - 1], P[i] - P[i - 1]); + puts(s + P[MIN_K - 1]); + + return 0; +} diff --git a/README.md b/README.md index 6fcb262..03a3bae 100644 --- a/README.md +++ b/README.md @@ -2,15 +2,15 @@ Bài tập luyện tập thi Olympic, học sinh giỏi Tin học, trong đó: -| Thư mục | Nguồn đề bài | -| --------------------- | --------------------------------- | -| `9`, `10`, `11`, `12` | Đề thi, kiểm tra phân theo lớp | -| `COCI` | [Giải Tin học Croatia mở rộng][0] | -| `NTU` | [Đại học Nha Trang][1] | -| `THT` | Hội thi Tin học trẻ | -| `codeforces` | [Codeforces][2] | -| `daily` | [/r/dailyprogrammer][3] | -| `others` | Các đề bài không rõ nguồn | +| Thư mục | Nguồn đề bài | +| ---------------------- | --------------------------------- | +| `09`, `10`, `11`, `12` | Đề thi, kiểm tra phân theo lớp | +| `COCI` | [Giải Tin học Croatia mở rộng][0] | +| `NTU` | [Đại học Nha Trang][1] | +| `THT` | Hội thi Tin học trẻ | +| `codeforces` | [Codeforces][2] | +| `daily` | [/r/dailyprogrammer][3] | +| `others` | Các đề bài không rõ nguồn | [0]: http://www.hsin.hr/coci/ [1]: http://laptrinh.ntu.edu.vn/ @@ -24,8 +24,6 @@ nhật dần. Bài làm trên Pascal được được dịch thử trên FPC 2.6 trở lên, bài viết trên C được dịch trên GCC 6 trở lên, bài làm trên Python chạy thử trên Python 3.5. -Các commit message có dạng: `<đường dẫn>: `. - Tất cả các bài làm được phát hành theo giấy phép [GPLv3](LICENSE), cho phép người dùng chạy, nghiên cứu, chia sẻ và chỉnh sửa tự do. Các đề bài hầu như không rõ điều khoản sử dụng. -- cgit 1.4.1