Đề thi HSG vòng 1 quốc gia

[Master_Baby]

Bài 1: Cho hai dãy số a, b độ dài bằng nhau. Gọi chi phí chọn cho một cặp số a[i], b[j] là |a[i] + b[j]|. Tìm các cặp số a[i], b[j] trong 2 dãy sao cho tổng chi phí chọn là nhỏ nhất.
Giới hạn: nhiều nhất có 1000 số mỗi dãy.

Bài 2: Cho một dãy các ô, mỗi ô ghi một số nguyên dương. (a[i] là số ghi ở ô thứ i). Giữa các ô có các đường nối độ dài 1 với quy tắc: nếu tồn tại 3 số i, j, k sao cho a[k] = a[i] + a[j] thì nối i đến k, j đến k (đường một chiều). Tìm đường đi dài nhất qua các ô này (đi qua các đường nối - tất nhiên).
Giới hạn: nhiều nhất có 10000 ô.

Bài 3: Cho một miếng sôcôla hình vuông, cạnh 2^k.
Ta bắt đầu cắt song song với các cạnh, đầu tiên cắt song song với cạnh ngang chia thành 2 phần bằng nhau, rồi gấp phần dưới chồng lên phần trên => thành 1 chồng.(kiểu gấp sách). Sau đó cắt song song với cạnh dọc chia thành 2 phần bằng nhau, rồi gấp phần bên phải lên chồng bên trái => thành 1 chồng.
Lặp lại cho đến khi chồng sôcôla có độ dài cạnh là 1 (các miếng hình vuông).
Vấn đề: cho trước hai ô (p, q), (u, v), hỏi sau khi cắt như trên thì 2 ô này nằm ở vị trí thứ mấy?
Giới hạn: k <= 40.

Anh em làm thử chơi :)

[m2mpro]

bài 1,2,3: Không dùng vét cạn được n<=1000 mà, còn quy hoạch động thì chưa học nên chịu thua.
- Ba bài này em chịu thua, giới hạn quá lớn mà chưa học quy hoạch động.

[phuclun]

bài 1 em chưa hiểu đề lắm nhỉ,nếu như chỉ có như vậy thì chọn kiểu nào chẳng đc vì 2 dãy bằng nhau mà.
Bài 2 + bài 3 em bó.

[mr_invincible]

Bài 1 chắc là chỉ chọn các cặp số có tổng nhỏ nhất đúng không (nếu có nhiều cặp có giá trị cùng cao nhất) đúng không nhỉ?

[proto]

pó toàn thân,đúng là cho học sinh giỏi

[bete]

Tui nghĩ bài thứ 3 như vầy:

- Mình chia 1 miếng sô-cô-la hình vuông thành 4 phần bằng nhau:


+---+---+
| A | B |
+---+---+
| C | D |
+---+---+


Khi mình gấp lần thứ nhứt thì C sẽ nằm chồng lên A, D nằm chồng lên B

Khi mình gấp lần thứ hai thì B sẽ nằm chồng lên D, D nằm chồng lên C, và C nằm chồng lên A

Như vậy, nếu mình đánh số 4 phần con là 1,2,3,4 như sau:


+---+---+
| 1 | 4 |
+---+---+
| 2 | 3 |
+---+---+


thì sau khi gấp 2 lần minh sẽ có thứ tự 4 phần con tính từ dưới lên trên sẽ 1,2,3,4

Bây giờ giả sử sau 1 số lần cắt & gấp mình có được 1 chồng gồm m mảnh hình vuông nằm chồng lên nhau . Mình chia chồng này ra làm 4 chồng con 1,2,3,4 đánh số như trên => sau khi gấp 2 lần mình sẽ có thứ tự 4 chồng con tính từ dưới lên trên là 1,2,3,4

Mình có 1 số nhận xét:

- các lớp của chồng con số 2 bị đảo ngược so với trước khi gấp (vì khi gấp thì mình lật úp chồng đó lại) => có thể tính được 1 lớp nào đó của chồng số 2 sau đợt gấp kế sẽ nằm ở lớp nào (xài đối xứng gương)

- 1 ô ứng với ô ở (cột c1, dòng d1) của chồng con số 2 sẽ trở thành ô ở (cột c2, dòng d2) của chồng con mới (sau khi gấp 2 lần) => có thể tính được 1 ô nào đó của chồng số 2 sau đợt gấp kế sẽ nằm ở ô nào (xài đối xứng gương)

- mình có thể lập luận tương tự (nhưng không giống y hệt) cho các chồng con còn lại (3 và 4)

Như vậy mình có thể tính được là 1 ô nào đó của 1 chồng con nào đó sau đợt gấp kế tiếp (2 lần) sẽ nằm ở lớp nào và ở ô nào

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[zmt264]

Tui nghĩ bài thứ 3 như vầy:

- Mình chia 1 miếng sô-cô-la hình vuông thành 4 phần bằng nhau:


+---+---+
| A | B |
+---+---+
| C | D |
+---+---+


Khi mình gấp lần thứ nhứt thì C sẽ nằm chồng lên A, D nằm chồng lên B

Khi mình gấp lần thứ hai thì B sẽ nằm chồng lên D, D nằm chồng lên C, và C nằm chồng lên A

Như vậy, nếu mình đánh số 4 phần con là 1,2,3,4 như sau:


+---+---+
| 1 | 4 |
+---+---+
| 2 | 3 |
+---+---+


thì sau khi gấp 2 lần minh sẽ có thứ tự 4 phần con tính từ dưới lên trên sẽ 1,2,3,4

Bây giờ giả sử sau 1 số lần cắt & gấp mình có được 1 chồng gồm m mảnh hình vuông nằm chồng lên nhau . Mình chia chồng này ra làm 4 chồng con 1,2,3,4 đánh số như trên => sau khi gấp 2 lần mình sẽ có thứ tự 4 chồng con tính từ dưới lên trên là 1,2,3,4

Mình có 1 số nhận xét:

- các lớp của chồng con số 2 bị đảo ngược so với trước khi gấp (vì khi gấp thì mình lật úp chồng đó lại) => có thể tính được 1 lớp nào đó của chồng số 2 sau đợt gấp kế sẽ nằm ở lớp nào (xài đối xứng gương)

- 1 ô ứng với ô ở (cột c1, dòng d1) của chồng con số 2 sẽ trở thành ô ở (cột c2, dòng d2) của chồng con mới (sau khi gấp 2 lần) => có thể tính được 1 ô nào đó của chồng số 2 sau đợt gấp kế sẽ nằm ở ô nào (xài đối xứng gương)

- mình có thể lập luận tương tự (nhưng không giống y hệt) cho các chồng con còn lại (3 và 4)

Như vậy mình có thể tính được là 1 ô nào đó của 1 chồng con nào đó sau đợt gấp kế tiếp (2 lần) sẽ nằm ở lớp nào và ở ô nào

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

Cách tiếp cận vấn đề rất đúng :D
đầu tiên tiếp cận số nhỏ, rồi quy nạp cho số lớn :D

[Master_Baby]

Bài 1:
phuclun, vd a[1] = -10; a[2] = 5; b[1] = 10; b[2] = -5 thì rõ ràng cặp tối ưu là (a[1]; b[1]) và (a[2]; b[2]) (tổng chi phí = 0) còn các cặp khác, ví dụ (a[1]; b[2]) chi phí 15 cộng với (a[2]; b[1]) chi phí 15, tổng chi phí là 30.
Cách của mr_invisible là một cách tham. Nhiều khi không đúng. Chú ý là chi phí luôn dương (trị tuyệt đối muh ^^)
Bài này mình cài đồ thị 2 phía + cặp ghép trọng số => chết đứ đừ

Bài 3 sếp bete giải vậy là ổn rồi. :)
Vấn đề duy nhất ở bài này là xử lý số lớn, vì nhiều nhất có 2^(k*2) ô = 1208925819614629174706176 >3<

[MMKC_IT]

toàn là bài không có giới hạn không ah, po'. Bác nào có bài nào làm mà giới hạn nó cao không

[meotrang7x]

Bài 1:
http://vn.spoj.pl/IOITRAIN/problems/NKSGAME/
Bài 2:
http://vn.spoj.pl/IOITRAIN/problems/NKJUMP/
Bài 3:
http://vn.spoj.pl/IOITRAIN/problems/NKGIFTS/

Các bạn đọc ở đó để có thông tin đầy đủ hơn (cũng như có thể viết chương trình để test xem mình đúng được bao nhiêu %). Chứ bạn gì đó mô tả quá ít không đủ điều kiện để làm bài.

[phuclun]

Trời ơi,hic hic,sao ko nghĩ ra trường hợp số âm vậy trời.

[mr_invincible]

Bài 1:
Cách của mr_invisible là một cách tham. Nhiều khi không đúng. Chú ý là chi phí luôn dương (trị tuyệt đối muh ^^)
Bài này mình cài đồ thị 2 phía + cặp ghép trọng số => chết đứ đừ

Bài 3 sếp bete giải vậy là ổn rồi. :)
Vấn đề duy nhất ở bài này là xử lý số lớn, vì nhiều nhất có 2^(k*2) ô = 1208925819614629174706176 >3<

mr_invisible là ai vậy nhỉ? Em là mr_invincible cơ mà?
Cho em hỏi luôn thi học sinh giỏi quốc gia bây giờ vẫn dùng trình biên dịch là Turbo Pascal hay Free Pascal? (Nếu Free Pascal thì bài 3 vẫn không cần xử lý số lớn)

[m2mpro]

Thi học sinh giỏi rồi có được gì đâu nhỉ ? Học để mà làm việc hay mở công ty mới hay...

[meotrang7x]

Thi học sinh giỏi rồi có được gì đâu nhỉ ? Học để mà làm việc hay mở công ty mới hay...

Không được gì thì em thi thử coi có giải được không? ;)
Những bài này là khó nhưng so với những bài toán thực tế mà Google, Microsoft giải còn dễ hơn nhiều đó em.

[m2mpro]

Em cũng đang thi học sinh giỏi mà anh, thăm dò ý kiến thôi mà !!! :D :D
- Mong mọi người bỏ qua.

[bete]

Tui nghĩ như vầy:

Bài 1: Cho hai dãy số a, b độ dài bằng nhau. Gọi chi phí chọn cho một cặp số a[i], b[j] là |a[i] + b[j]|. Tìm các cặp số a[i], b[j] trong 2 dãy sao cho tổng chi phí chọn là nhỏ nhất.
Giới hạn: nhiều nhất có 1000 số mỗi dãy.

Mình có 1 số nhận xét như sau:

1) Xét trường hợp mỗi dãy có đúng 2 số: [A,B] và [C,D]
=> mình có 2 lựa chọn: (|A+C|+|B+D|), và (|A+D|+|B+C|)
Không mất tính tổng quát, giả sử A>=B và C>=D

Số lớn nhứt của dãy số a bắt cặp với số nhỏ nhứt của dãy số b là lựa chọn tốt hơn:
(|A+D|+|B+C|) <= (|A+C|+|B+D|)

Lập luận:
A>=B và C>=D
=> (A+C)>=(A+D)>=(B+D)
và (A+C)>=(B+C)>=(B+D)

+ nếu A+C>=(A+D,B+C)>=B+D>=0
=> (A+C)+(B+D)=(A+D)+(B+C)
=> |A+C|+|B+D|>=|A+D|+|B+C| => điều phải chứng minh

+ nếu 0>A+C>=(A+D,B+C)>=B+D
=> -(A+C)-(B+D)=-(A+D)-(B+C)
=> |A+C|+|B+D|>=|A+D|+|B+C| => điều phải chứng minh

+ nếu A+C>=0>(A+D,B+C)>=B+D
=> (A+C)-(B+D) >= -(A+D)-(B+C)
=> |A+C|+|B+D|>=|A+D|+|B+C| => điều phải chứng minh

+ nếu A+C>=(A+D,B+C)>=0>B+D
=> (A+C)-(B+D) >= (A+D)+(B+C)
=> |A+C|+|B+D|>=|A+D|+|B+C| => điều phải chứng minh

+ nếu A+C>=B+C>=0>A+D>=B+D
=> (A+C)-(B+D) >= -(A+D)+(B+C)
=> |A+C|+|B+D|>=|A+D|+|B+C| => điều phải chứng minh

+ nếu A+C>=A+D>=0>B+C>=B+D
=> (A+C)-(B+D) >= (A+D)-(B+C)
=> |A+C|+|B+D|>=|A+D|+|B+C| => điều phải chứng minh

(tui không rành về bất đẳng thức với trị tuyệt đối nên phải làm dài dòng như trên; bạn nào có cách ngắn gọn hơn xin chỉ giùm, cám ơn)

2) Xét trường hợp mỗi dãy có n số với n>2
Số lớn nhứt của dãy số a bắt cặp với số nhỏ nhứt của dãy số b là lựa chọn tốt nhứt

Lập luận: gọi số lớn nhứt của dãy a là A, số nhỏ nhứt của dãy b là D
Xét 1 cách bắt cặp nào đó với: A bắt cặp với C (C thuộc dãy số b và C>=D) và D bắt cặp với B (B thuộc dãy số a và B<=A)
Khi đó chi phí của cách bắt cặp này sẽ là: |A+C|+|B+D|+S
(S là chi phí của các cặp còn lại)
Theo nhận xét 1 thì vì A là số lớn nhứt trong (A,B) và D là số nhỏ nhứt trong (C,D) cho nên |A+D|+|B+C|+S <= |A+C|+|B+D|+S. Tức là nếu mình cho A bắt cặp với D và B bắt cặp với C thì mình sẽ có 1 cách với chi phí "nhỏ hơn"

Với phần còn lại (sau khi loại bỏ đi A trong dãy số a và loại bỏ đi D trong dãy số B) thì mình cũng làm tương tự: cho số lớn nhứt của dãy số a bắt cặp với số nhỏ nhứt của dãy số b để được chi phí "nhỏ nhứt"

Tóm lại: sắp thứ tự a tăng và b giảm rồi bắt cặp theo thứ tự đó => sẽ được chi phí nhỏ nhứt

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[pvtao]

---->bài 1 hình như là n<=10000 thì phải.
Nếu thế theo em thì cứ đọc lại File nhiều lần, các bác cứ làm thử xem sao.
---->bài 2 theo em thì sắp xếp lại dãy A tăng dần rồi dùng quy hoạch động.
---->bài 3 nếu đặt miếng socola trong không gian ba chiều và dùng ba biến x,y,z để lưu lại vị trí sau mỗi lần gấp.
(em mới tham gia diễn đàn mong các bác góp ý).
(<<hiểu biết nông cạn xin giúp đỡ>>)

[mr_invincible]

Bài 1, bài 3 làm như anh bete đã là chuẩn và tối ưu lắm rồi.
Bài 2: giới hạn tương đối lớn, tất nhiên phải dùng quy hoạch động rồi, cái đó ai chả biết, vấn đề là dùng như thế nào để thời gian có thể chấp nhận được chứ quy hoạch động với độ phức tạp lớn thì ai chả làm được

[meotrang7x]

@bete: không biết đề thi gốc thế nào, nhưng theo link mà mình tìm được thì chỉ cần tìm 1 cặp số mà tổng là nhỏ nhất.

[meotrang7x]

Từ tập các bài có trên SPOJ
2401. VOI08 Trò chơi với dãy số
Mã bài: NKSGAME

Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:

b1, b2, ..., bn

còn dãy số mà bạn thứ hai chọn là

c1, c2, ..., cn

Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |bi+cj|.

Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2).
Yêu cầu

Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
Dữ liệu

* Dòng đầu tiên chứa số nguyên dương n (n ≤ 100000)
* Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi ≤ 109, i=1, 2, ..., n)
* Dòng thứ hai chứa dãy số nguyên c1, c2, ..., cn (|ci ≤ 109, i=1, 2, ..., n)

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả

Ghi ra giá nhỏ nhất tìm được.
Ràng buộc

* 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.

Ví dụ

Dữ liệu:
2
1 -2
2 3

Kết qủa
0

[meotrang7x]

Nếu làm theo cách thử tất cả các cặp có thể (ai,bj) thì sẽ được 60% điểm (vì 60% trường hợp n<=1000 nên chắc chắn là đủ thời gian chạy). Còn nếu muốn lấy 100% điểm thì.... ;)

[TIG_Messi]

Bài 1: Chặt nhị phân O(NlogN) bằng cách tìm số gần số đã cho nhất :)
Bài 2: Quy hoạch động trên DAG đã sort topo
Bài 3: Cơ bản rồi, xét trạng thái của 4 góc sau khi xoay :) O(N)

[mr_invincible]

Bài 2 nếu sắp xếp topo thì trước hết phải tìm mọi cạnh của đồ thị (mỗi đỉnh là 1 số). Sau đó lại phải tiếp tục sắp xếp lại. Em nghĩ làm xong 2 bước trên với n=10000 thì chương trình đã chạy lâu lắm rồi, làm sao đạt yêu cầu được

[quanglc]

bài 1 : sắp b
nhập c kiem tra luon co ton tai -c[i] trong b khong (tiềm kiếm nhị phân)
nếu không có thì chọn 2 số lân cận tìm min
bai 2 : sắp a tăng rồi quy hoạch động.
bải 3 : xử lí số lớn

[oOOo]

Thi HSG quá mạo hiểm và nặng về thành tích!!!!
học là quan trọng nhg kô nên đặt mục đích thi HSG lên hàng đầu
đây cũng là tiêu chí của HS nc' ngoài (khác VN )

[okmen910]

nãy giờ thấy mấy anh nói quy hoạch động, nhưng em chả biết nó là gì, có ai giải thích giúp em được không vì em đang cần, sắp thi rồi

[mr_invincible]

nãy giờ thấy mấy anh nói quy hoạch động, nhưng em chả biết nó là gì, có ai giải thích giúp em được không vì em đang cần, sắp thi rồi

Vấn đề là bạn thi cấp gì và bao giờ thi. Theo kinh nghiệm của tôi thì nếu thi đến cấp thành phố bậc THCS thì vẫn chưa cần đến quy hoạch động. Hơn nữa nếu bạn sắp thi thì chỉ nên tập trung ôn tập vào những cái gì bạn đã biết chứ nếu cố học thêm những cái mới thì cũng chẳng có tác dụng gì và sẽ làm bạn thêm rối trí.

[ConanKudo]

Đề thi năm nay phải nói là dễ hơn nhiều so với các năm trước .Chỉ có là phải cài đặt.
Bài 1 đoạn tìm kiếm chỉ cần tuyến tính trong O(N) thôi,làm gì phải chặt nhị phân
Bài 2 xây dựng đồ thị tuyến tính mất O(N^2),sau đó QHĐ trên DAG mất O(N^2) nữa.
Bài 3 thì chỉ cần xét xem miếng bánh thuộc miền nào trong 4 miền,độ phức tạp O(k*n).

Cả 3 bài này mình nghĩ chạy không quá 0.5s :)

[m2mpro]

Vấn đề là bạn thi cấp gì và bao giờ thi. Theo kinh nghiệm của tôi thì nếu thi đến cấp thành phố bậc THCS thì vẫn chưa cần đến quy hoạch động. Hơn nữa nếu bạn sắp thi thì chỉ nên tập trung ôn tập vào những cái gì bạn đã biết chứ nếu cố học thêm những cái mới thì cũng chẳng có tác dụng gì và sẽ làm bạn thêm rối trí.
mr_invincible nói chí phải, em cũng thi HSG năm nay ( lớp 9 ) rồi nghỉ luôn, focus vào Java ( đang ghiền thằng này ) :D

[phuclun]

uả,chứ m2mpro tính thi vài chuyên gì ma học Java,đâu có chuyên nào học Java đâu,họa chăng là chỉ học ở ngoài thôi.

[qvluom]

Đúng là kém may mắn thật. Đến giờ này mới tiếp xúc được với đề thi vòng quốc gia. Mấy đứa học trò của tui thi xong thì hỏi lại tụi nó nói là quên đề hết trơn. 5 đứa đi thi mà không có đứa nào nhớ được câu nào cả. Thật là hết nói. Đến lúc này thì chắc là các bạn đã có được lời giải rồi phải không. Nếu có thì hãy post lên cho tôi tham khảo. Còn bạn ConanKudo thì đúng là hay thật. Như vậy mà cũng nghĩ ra được. Chắc hẳn là một danh sư xuất thân từ danh môn. Theo đúng như đề bài phía trên thì câu 2 và 3 là không khó lắm. Nhưng câu 1 để có một giải thuật 0(n) thì tôi suy nghĩ hơn nữa tiếng đồng hồ rồi mà vẫn không ra. Mong được các bạn chỉ giáo (Tuy nhiên đối với bài 1, tôi đã nghĩ ra được một cách giải không vượt quá 2s đối với dữ liệu cực đại. Nhưng không phải là 0(n) nên ngại không đưa lên). Thanks!

[Ga mo]

Bài 1: Cho hai dãy số a, b độ dài bằng nhau. Gọi chi phí chọn cho một cặp số a[i], b[j] là |a[i] + b[j]|. Tìm các cặp số a[i], b[j] trong 2 dãy sao cho tổng chi phí chọn là nhỏ nhất.
Giới hạn: nhiều nhất có 1000 số mỗi dãy.

Bài 2: Cho một dãy các ô, mỗi ô ghi một số nguyên dương. (a[i] là số ghi ở ô thứ i). Giữa các ô có các đường nối độ dài 1 với quy tắc: nếu tồn tại 3 số i, j, k sao cho a[k] = a[i] + a[j] thì nối i đến k, j đến k (đường một chiều). Tìm đường đi dài nhất qua các ô này (đi qua các đường nối - tất nhiên).
Giới hạn: nhiều nhất có 10000 ô.

Bài 3: Cho một miếng sôcôla hình vuông, cạnh 2^k.
Ta bắt đầu cắt song song với các cạnh, đầu tiên cắt song song với cạnh ngang chia thành 2 phần bằng nhau, rồi gấp phần dưới chồng lên phần trên => thành 1 chồng.(kiểu gấp sách). Sau đó cắt song song với cạnh dọc chia thành 2 phần bằng nhau, rồi gấp phần bên phải lên chồng bên trái => thành 1 chồng.
Lặp lại cho đến khi chồng sôcôla có độ dài cạnh là 1 (các miếng hình vuông).
Vấn đề: cho trước hai ô (p, q), (u, v), hỏi sau khi cắt như trên thì 2 ô này nằm ở vị trí thứ mấy?
Giới hạn: k <= 40.

Anh em làm thử chơi :)

Đây là đề tin học quái gì chứ, đề toán thì đúng hơn:(.

[cashier]

Còn bạn ConanKudo thì đúng là hay thật. Như vậy mà cũng nghĩ ra được. Chắc hẳn là một danh sư xuất thân từ danh môn.
Đại ca này có con mắt tinh tường thật, mới nhìn qua đã khẳng định! mà có vẻ như đây là một thầy giáo ¿:whistling

Và cũng phải thừa nhận là đề năm nay không khó ( so với các năm khác :) ) < mình thấy đề năm nay dễ vì không cần phải sử dụng nhiều thuật toán kinh điển mà lại khó nhớ :( > Vậy mà vẫn có người đọc được nhầm đề mới giỏi :crying:


Tuy nhiên đối với bài 1, tôi đã nghĩ ra được một cách giải không vượt quá 2s đối với dữ liệu cực đại. Nhưng không phải là 0(n) nên ngại không đưa lên
Vậy là cũng hơn được nhiều người rồi :D, nên đưa lên cho mọi người cùng tham khảo chứ :)

[zmt264]

Bài 1: Cho hai dãy số a, b độ dài bằng nhau. Gọi chi phí chọn cho một cặp số a[i], b[j] là |a[i] + b[j]|. Tìm các cặp số a[i], b[j] trong 2 dãy sao cho tổng chi phí chọn là nhỏ nhất.
Giới hạn: nhiều nhất có 1000 số mỗi dãy.



Phải ra đề thía nè mới dễ hiểu nhé :D
Cho n người nam, và n người nữ.
Giả sử mỗi người nam hoặc nữ khi đám cưới sẽ bị mất (hoặc được - tức là khi cưới có thể lãi hoặc lỗ :D ) 1 số tiền là a[i] và b[j]
Như vậy, chi phí hoặc số tiền nhận được của một đám cưới là a[i]+b[j]

Tìm cách gặp các cặp với nhau sao cho tổng số tiền nhận được hoặc mất đi là ít nhất.

[ConanKudo]

Xui quá,kết quả thi mình được có 19.25/20.Giải nhì.Nhầm một tẹo thôi là giải nhất rồi.
@qvluom : anh/thầy/bạn ,mình nói là O(N) đoạn searching ,chứ không phải cả bài là O(N).Đương nhiên vẫn phải mất O(NLogN) đoạn sort.
Cái đề này mình thấy bài 2 nhiều người làm O(N^2LogN).Trong khi thực tế chỉ cần O(N^2).
3 bài này thì theo mình cài mà gặp rắc rối nhất là bài 3.Bài này mình cài số lớn mà xử lý hơi "thô" nên khá dài :).Nhưng cũng ăn full điểm.
Đề vòng 2 năm nay thì lại khó hơn năm ngoái,ngày 1 mình làm vớ vẩn quá,ngày 2 làm còn tốt.Cũng chả hi vọng gì nhiều :)

p/s:Xin lỗi mình cũng không xuất thân từ danh môn nào,mình đến từ lớp 11 Toán 1 khối phổ thông chuyên ĐHSP Hà Nội.Nick trên các trang online judge cũng như forum nào đều là ConanKudo

[bete]

Thân gửi bạn ConanKudo,


Cái đề này mình thấy bài 2 nhiều người làm O(N^2LogN).Trong khi thực tế chỉ cần O(N^2).

=> tui nghĩ bài này có thể đẩy xuống O(NlogN) đó chớ !? (với giả thiết của bạn meotrang7x: không biết đề thi gốc thế nào, nhưng theo link mà mình tìm được thì chỉ cần tìm 1 cặp số mà tổng là nhỏ nhất).

-thân

[attilathehun]

@bete: bạn conankudo đang nói bài 2. Bài tìm cặp số có trị tuyệt đối bé nhất là bài 1. Bài 1 có thể làm trong O(n).
Về đề thi vòng 2 quốc gia, các bạn có thể xem tại địa chỉ:
http://vnoi.info/vn/forum/voi/vong_2_2008/view.pas

[ConanKudo]

Thân gửi bạn ConanKudo,



=> tui nghĩ bài này có thể đẩy xuống O(NlogN) đó chớ !? (với giả thiết của bạn meotrang7x: không biết đề thi gốc thế nào, nhưng theo link mà mình tìm được thì chỉ cần tìm 1 cặp số mà tổng là nhỏ nhất).

-thân

Nếu là bài 1 thì cách trâu bò là for 2 vòng cho nhanh chứ mình nói O(N^2logN) làm gì =)),bài 1 có 2 cách làm là sort rồi tìm kiếm nhị phân,hoặc sort xong rồi tuyến tính O(N),cả 2 đều có độ phức tạp trung bình là O(NLogN).

Còn O(N^2) mình nói là bài 2,bài 2 mà bạn làm được O(NLogN) thì mình cũng phục :).Vì hầu hết mọi người đều làm O(N^2logN) do tìm kiếm nhị phân đoạn khởi tạo đồ thị :)

[vdmedragon]

Những bài này là khó nhưng so với những bài toán thực tế mà Google, Microsoft giải còn dễ hơn nhiều đó em.

Nghe câu này thấy chuối vãi và giọng điệu tinh tướng ghê luôn, những bài toán thực tế mà ABC, XYZ giải còn dễ hơn nhiều. Thằng này đúng là ếch ngồi đáy giếng, coi trời bằng vung. Giải được dăm ba cái bài tin học mà đã lên giọng cứ tưởng mình là siêu nhân, vô đối.

[=========> Bổ sung bài viết <=========]

Đây, bài này xem meotrang7x giải thế nào mà tinh tướng : bài thật sự chứ không phải là mấy bài thi tin học đâu nhé.

Một công ty về hoạt hình cần tô màu các đối tượng hoạt hình trong phim, ví dụ mèo tôm màu xanh, chuột jerry màu đen ... Đã có sẵn các lớp mẫu ví dụ mèo tôm màu xanh, chuột jerry màu đen, cái mũ bà chủ màu đỏ ... Để tiết kiệm công vẽ mầu (chắc là vì lúc đầu vẽ bằng mầu chì lên khung các đối tượng sau đó tô màu các đối tượng này để lên hình) thì họ muốn có một chương trình tự động dò tìm các đối tượng và tô màu các đối tượng đó theo mẫu có sẵn. Vấn đề là các đối tượng này nó có thể không giống ban đầu, mèo tôm có thể chạy, ngã ... nhưng vẫn là mèo tôm (ví dụ phân biệt thông qua khuông mặt chẳng hạn).

Công ty cần bạn viết chương trình tô màu giúp họ, lương trả theo tháng chẳng hạn 2000E/tháng, làm trong 3 năm (kết quả dùng làm luận án tiến sĩ mà).

[meotrang7x]

Nghe câu này thấy chuối vãi và giọng điệu tinh tướng ghê luôn, những bài toán thực tế mà ABC, XYZ giải còn dễ hơn nhiều. Thằng này đúng là ếch ngồi đáy giếng, coi trời bằng vung. Giải được dăm ba cái bài tin học mà đã lên giọng cứ tưởng mình là siêu nhân, vô đối.

[=========> Bổ sung bài viết <=========]

Đây, bài này xem meotrang7x giải thế nào mà tinh tướng : bài thật sự chứ không phải là mấy bài thi tin học đâu nhé.

Một công ty về hoạt hình cần tô màu các đối tượng hoạt hình trong phim, ví dụ mèo tôm màu xanh, chuột jerry màu đen ... Đã có sẵn các lớp mẫu ví dụ mèo tôm màu xanh, chuột jerry màu đen, cái mũ bà chủ màu đỏ ... Để tiết kiệm công vẽ mầu (chắc là vì lúc đầu vẽ bằng mầu chì lên khung các đối tượng sau đó tô màu các đối tượng này để lên hình) thì họ muốn có một chương trình tự động dò tìm các đối tượng và tô màu các đối tượng đó theo mẫu có sẵn. Vấn đề là các đối tượng này nó có thể không giống ban đầu, mèo tôm có thể chạy, ngã ... nhưng vẫn là mèo tôm (ví dụ phân biệt thông qua khuông mặt chẳng hạn).

Công ty cần bạn viết chương trình tô màu giúp họ, lương trả theo tháng chẳng hạn 2000E/tháng, làm trong 3 năm (kết quả dùng làm luận án tiến sĩ mà).

Lâu ngày mới trở lại forum.
Đọc đi đọc lại mới hiểu là bé này chửi mình vì bé ấy... không hiểu tiếng Việt! :lick:
Đọc câu trích dẫn của mình có ai nghĩ mình nói các bài toán thực tế là dễ không ta? :D:D:D

[^^nhox_nhox^^]

hì,sao có nhiều giỏi lập trình wá,phải chi mình giỏi bằng họ 1 chút :P hihi

[ConanKudo]

Hi
Mọi người làm gì mà căng thẳng thế.
Những gì bàn luận ở đây chỉ là những bài toán tin học rất là "nhãi nhép" so với nhu cầu cuộc sống thôi mà.Cái thi QG này cũng chỉ là một trò chơi của những năm cấp 3 thôi,nó đâu thể hiện gì nhiều khi vào đại học.Về sau khi học đại học toàn học nhiều ngôn ngữ lập trình khác như PERL,RUBY,C++,C#,JAVA...Chứ ai xài pascal nữa đâu.
Nói chung những bài toán tin ở đây bàn luận chỉ là một trò chơi về tư duy thôi.Còn so với những bài toán thực tế thì đúng chỉ là những bài "trẻ con"

[chuotbac08]

bai thu nhat nha
const fi='seqgame.inp';
fo='seqgame.out';
maxn=1000;

var b:array[0..maxn] of longint;
f,g:text;
n,gtmin:longint;

procedure nhapdl;
var i:longint;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do read(f,b[i]);
readln(f);
end;

procedure ghikq;
begin
assign(g,fo);
rewrite(g);
writeln(g,gtmin);
close(g);
end;

procedure quicksort(L,R:longint);
var i,j,tg,chot:longint;
begin
if L>=R then exit;
chot:=b[(L+R) div 2];
i:=L;j:=R;
repeat
while b[i]<chot do inc(i);
while b[j]>chot do dec(j);
if i<=j then
begin
tg:=b[i];
b[i]:=b[j];
b[j]:=tg;
inc(i); dec(j);
end;
until i>j;
quicksort(L,j);
quickSort(i,R);
end;


function min(x,y:longint):longint;
begin
if x>y then min:=y else min:=x;
end;

procedure tinhtiep;
var i,d,c,g,x:longint;
begin
for i:=1 to n do
begin
read(f,x);
d:=1; c:=n;
while c-d>1 do
begin
g:=(d+c) div 2;
if b[g]>-x then c:=g else d:=g;
end;
gtmin:=min(gtmin,min(abs(x+b[d]),abs(x+b[c])));
if gtmin=0 then
begin
ghikq;
halt;
end;
end;
end;

procedure xuli;
begin
quicksort(1,n);
tinhtiep;
end;

begin
nhapdl;
xuli;
ghikq;
end.

[=========> Bổ sung bài viết <=========]

bai thu hai nha

const fi='jump.inp';
fo='jump.out';
maxn=1000;

var a:array[1..maxn] of longint;
f:text;
b:array[1..maxn] of integer;
omax,n:longint;

procedure nhapdl;
var i:integer;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do read(f,a[i]);
close(f);
end;

procedure chuanbi;
begin
end;

procedure sapxep;
var i,j,g,tg:longint;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then
begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
end;
end;

function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;

procedure tinh;
var i,j,k:longint;
begin
for i:=1 to n do b[i]:=1;
for i:=1 to n do
for j:=i+1 to n do
for k:=j+1 to n do
if a[i]+a[j]=a[k] then
b[k]:=max(b[k],max(b[i],b[j])+1);
end;

procedure timmax;
var i:integer;
begin
omax:=0;
for i:=1 to n do
if b[i]>omax then omax:=b[i];
end;

procedure xuli;
begin
sapxep;
tinh;
timmax;
end;

procedure ghikq;
begin
assign(f,fo);
rewrite(f);
writeln(f,omax);
close(f);
end;

begin
nhapdl;
chuanbi;
xuli;
ghikq;
end.

[=========> Bổ sung bài viết <=========]

bai thu ba ne

const finp='gifts.inp';
fout='gifts.out';

var fi,fo:text;
dem,x,y,k,i,cot,dong,j:longint;
somu:array[-1..20] of longint;

procedure chuanbi;
begin
somu[-1]:=0;
somu[0]:=1;
for i:=1 to 20 do
somu[i]:=somu[i-1]*2;
end;

procedure cat_ngang;
begin
if x<=dong then
dem:= dem+somu[j] else
begin
x:=2*dong-x+1; {x:=dong-(x-dong)+1}
dem:=somu[j]-dem-1;
end;
end;

procedure cat_doc;
begin
if y>cot then
dem:= dem+somu[j] else
begin
dem:=somu[j]-dem-1;
y:=2*cot-y+1; {y:=cot+(cot-y)+1}
end;
end;

procedure xuli;
begin
dem:=0;
dong:=somu[k-1] -1;
cot :=somu[k-1] -1;
j:=0;
for i:=1 to k do
begin
cat_ngang;
inc(j);
cat_doc;
inc(j);
dong:=dong div 2;
cot:=cot+(somu[k]-cot-1) div 2;
end;
end;

begin
assign(fi,finp); reset(fi);
assign(fo,fout); rewrite(fo);
chuanbi;
read(fi,k,x,y);
xuli;
write(fo,dem+1,#32);
read(fi,x,y);
xuli;
write(fo,dem+1);
close(fi);
close(fo);
end.

[bld]

chào mấy anh chị
em vào đây chỉ đọc sơ qua cái đề thôi-biết chắc là không giải được rồi . chỉ mong được chat với mấy anh chị 1 chút :
cho em hỏi anh conankudo bắt đầu với pascal từ khi nào ? anh đã có những thành tích gì , em năm nay lên lớp 8 , rất thích pascal ,không biết năm lên lớp 11 có bằng được mấy anh chị hiện giờ không ... mấy anh chị đọc những sách gì và luyện tập , học hành , làm việc ở đâu ?
- hỏi hơi nhiều nhưng em thật sự cần biết -
cảm ơn :)

[thuonghcm]

bai thu nhat nha
procedure ghikq;
begin
assign(g,fo);
rewrite(g);
writeln(g,gtmin);
close(g);
end;
..........................................
if gtmin=0 then
begin
ghikq;
halt;
end;
end;
end;




XIn lỗi nhé, chưa đọc hết mà thấy chỗ này vậy và nó sẽ hgi số 0 vào file KQ mãi à?
hong biet tui có nhầm o đuâu hôn!? thankxs