# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Đề thi HSG Tin học tỉnh Nam Đinh 2009-2010

## nguyendangvan

đây là đề thi học sinh giỏi minh sưu tập được nhưng chưa biết cách giải mong các thành viên giúp đỡ và chỉ rõ thuật toán áp dụng để giải mỗi bài, thanhk[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

*Bài 1: (6 điểm) Mua hàng*
Có n người xếp thành hàng theo thứ tự để mua hàng. Thòi gian người bán hàng phục vụ cho người thứ i là ti đơn vị thời gian. Hãy tìm thời gian mà người thứ k phải chờ để mua hàng.
*Dữ liệu:* Vào từ tệp văn bản MH.INP
- Dòng 1: chứa 2 số n, j nguyên dương (1≤k≤n≤100);
- Dòng 2: chứa n số t1, t2,...tn ( Các giá trị ti đều nguyên dương va nhỏ hơn 1000).
*Kết qủa :* Đưa ra tệp văn bản MH.OUT chứa duy nhất số C thở mãn yêu cầu của dữ liệu vào.
*Ví dụ:* 
<div style="text-align: center">MH.INP​</div> <div style="text-align: center">MH.OUT​</div> 5 3
1 3 2 4 1
4




*Bài 2: (7 điểm) Giả thuyết của GÔN – BẮC*
Giả thuyết của GÔN – BẮC ( Cho đến nay vẫn chưa bị bác bỏ, nhưng cũng chưa chứng minh được đầy đủ) nói rằng mỗi số chẵn n lớn hơn 2 là tổng của hai số nguyên tố.
*Yêu cầu:* Cho số n chẵn lớn hơn 2, hãy xác định số lượng các cặp số nguyên tố có tổng bằng số n.
*Kết quả :* Đưa ra tệp văn bản GONBAC.OUT chứa duy nhất một số theo yêu cầu của bài.
*Ví dụ :* 
<div style="text-align: center">GONBAC.INP​</div> <div style="text-align: center">GONBAC.OUT​</div> 16
2


*Bài 3: (7 điểm) Bố trí xe*
Vưa qua kì thi máy tính cầm tay cấp quốc gia được tổ chức tại nam Định, Ban tổ chức đã bố trí xe ô tô để đưa mỗi đoàn học sinh cảu mỗi tỉnh đi tham quan các địa điểm khác nhau. Có tất cả n đoàn hoạc sinh đánh số từ 1 đên n, đoàn thứ I cần đi tới địa điểm cách nơi ở là di đơn vị( coi như di là khoảng cách tình theo chiều cả đi lẫn về). có m chiếc xe ô tô sử dụng được đánh số từ 1 đến m (m≥n), có thể dùng để phục vụ đưa các đoàn đi tham quan. Được biết xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích xăng trên một đơn vị độ dài. Hãy lựa chọn và bố trí n xe, mỗi xe chi phục vụ một đoàn theo yêu cầu sao cho tổng thể tích xăng cần thiết là ít nhất.
*Dữ liệu:* Vào từ tệp văn bản XE.INP có cấu trúc:
- Dòng 1: Chứa 2 số nguyên dương n, m (1≤n≤m≤200);
- Dòng 2 chứa n số d1, d2,…dn;
- Dòng 3: Chứa m số v1, v2,…vm.( Các giá trị di, vj đều nguyên dương và không qúa 32000).
*Kết quả:* Đưa ra tệp văn bản XE.OUP, chứa 2 dòng
- Dòng 1: Chứa số lượng xăng cần ít nhất theo yêu cầu;
- Dòng 2: chứa n số x1, x2,…xn thể hiện đoàn thứ I được bố trí đi xe xi;
*Ví dụ:* 
<div style="text-align: center">XE.INP​</div> <div style="text-align: center">XE.OUT​</div> 3 5
3 8 5
3 2 4 1 5
27
1 4 2



*Chú ý:* 
- Tệp chương trình Bài 1 đặt tên là: MH.PAS
- Tệp chương trình Bài 2 đặt tên là: GONBAC.PAS
- Tệp chương trình Bài 3 đặt tên là: XE.PAS
- Trong các tệp dữ liệu vào hoạc ra, các số trên cùng một dòng cách nhau ít nhất một dấu cách.

----------


## vietkanpy

Bạn ở trường nào của Nam Định thế? Mình cũng ở Nam Định nhưng chưa từng gặp loại đề nào thế này, chắc của lớp 8 mới học Pascal hả?
Bài 1: tính tổng T_ từ 1-> k là ra kết quả.
Bài 2: lập mảng chứa tất cả các số nguyên tố < n. Dựa vào mảng đã lập được, với mỗi vị trí thứ i, tìm vị trí j>i sao cho tổng = n. Nếu tìm được thì tăng biến đếm.
Bài 3: xếp tăng V, xếp giảm D. Xe thứ i thì đi đoàn D tiêu thụ V. -> Xong
Bài 3 vẽ ra giấy là thấy ngay cách làm thôi mà._

----------


## thanhtungbooking

bạn có thể giải cụ thể các bài được không?

----------


## linhti0209

Vì có chút việc bận nên có lẽ mình chưa có code ngay cho bạn. Mình sẽ sớm code và post cho bạn. Chắc bạn học ở TDN hả? Vì mình thấy có 1 bài mình đã được thày cho làm rồi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## ledinh121189

Bài 1 của bạn đây, mình làm theo đúng yêu cầu đề bài, bạn đọc code sẽ hiểu[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]



> const inp='mh.inp';
> out='mh.out';
> var fi,fo:text;
> i,n,k,tong,so:longint;
> begin
> assign(fi,inp);reset(fi);
> assign(fo,out);rewrite(fo);
> readln(fi,n,k);
> tong:=0;so:=0;
> ...


Bài 2: Mình làm vội bài này với thuật toán cơ bản, chưa tối ưu, nếu bạn có thể tối ưu hơn ở bước kiểm tra tính nguyên tố thì tối ưu lại code nhé.



> const inp='gonbac.inp';
> out='gonbac.out';
> var fi,fo:text;
> i,n,kq:longint;
> procedure nhap;
> begin
> assign(fi,inp);reset(fi);
> readln(fi,n);
> close(fi);
> ...


Bài 3:



> const inp='xe.inp';
> out='xe.out';
> var fi,fo:text;
> sttd,sttv,d,v:array[1..200]of integer;
> i,j,tg,vt,tong,n,m:integer;
> procedure nhap;
> begin
> assign(fi,inp);reset(fi);
> readln(fi,n,m);
> ...

----------


## khuvucmuabannhadat

Bài 2: giới hạn bn vậy bạn ? 

Ý tưởng của mình ( chắc nhanh hơn bạn Long)
- Tạo mạng hằng NT
- Cho vòng for chạy từ i -> k (k là vị trí mà tại đó a[k]<=n) ùi tìm kiếm nhị phân phần tử n-a_
+ Nếu tìm đc : thì k:= vị trí tìm thấy - 1 , tăng biến đếm
+ Không tìm thấy thì vòng for tự động tăng i
- In biến đếm_

----------


## kitelag

Nhanh hơn sao được chị Hằng, riêng cái khoản tạo mảng NT đã kém em rồi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

----------


## dungmxh

Mình đâu nói là tạo trong bài [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]. Vik hẳn 1 ct tạo, lấy mảng hằng đưa vào bài thôi !

----------


## zinzin8x

Cách này mà cho giới hạn mã nguồn là chết chắc. Nếu n chỉ tầm 100 đã có rất nhiều số nguyên tố trong khoảng 1->100 rồi. Làm cách này nghe chừng không ổn lắm

----------


## Tuanvuong

k bik bạn có nhầm, số nguyên tố < 100 có 26 số àhh [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## TruongTamPhong

1000? Chắc chắn bài này giới hạn n sẽ không nhỏ hơn 10000 vì chạy với cách cổ nhất (cách của mình) thì với n=10000 chạy mất 1s. Có cải tiến phải giới hạn to nữa.

----------


## 36hoangcau

Bài hai mình nghĩ là bạn nên đưa ra giới hạn cho số N chứ. Để mọi người có thuật toán hoàn chỉnh [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## muabuon

> Bài hai mình nghĩ là bạn nên đưa ra giới hạn cho số N chứ. Để mọi người có thuật toán hoàn chỉnh [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]


xin lỗi, mình quên nêu giới hạn của n: 2<n<20000

----------


## thieuk55

Nếu vậy thì mình nghĩ dùng sàng Eratosthene là đủ rồi. Đơn giản, dễ cài đặt. Sau đó thì for một vòng trong tập sô nguyên tố vừa sinh được để kiểm tra xem có bao nhiêu trường hợp thôi.

@TieuLong: Đoạn kiểm tra số nguyên tố của em không được gọn lắm, anh nghĩ là em nên sinh mảng số nguyên tố trước luôn rồi mới kiểm tra. Đoạn code khởi tạo các số nguyên tố từ 1 -> MaxN có thể viết như sau:



```
const
  maxN = 20004;
var
  Prime : array [1..maxN] of longint; // lưu các số nguyên tố
  PrimeSqr : array [1..maxN] of longint; // lưu bình phương của các số nguyên tố.
  Count : longint;  

procedure InitPrime;
var 
  T, i, j, check : longint;
begin
  Count := 2;
  check := 0;
  Prime[1] := 2;
  Prime[2] := 3;
  PrimeSqr[1] := 4;
  PrimeSqr[2] := 9;
  T := 3;
  while true do
  begin
  // Một số nguyên tố bất kì lớn hơn 3 chỉ có thể có dạng (6k+1) hoặc (6k+5) -> Có thể áp
  //dụng "bước nhảy 2" và "bước nhảy 4" trọng thuật toán sinh các số nguyên tố
    T := T + 2;
    If T > MaxN then 
      exit;

    for i := 1 to Count do
      if (PrimeSqr[i] > T) then
        break
      else
      if (T mod Prime[i] = 0) then
      begin
        check := T;
        break;
      end;
    
    if (check <> T) then
    begin
      inc(Count);
      Prime[Count] := T;
    end;
    // 
    T := T + 4;
    If T > MaxN then 
    exit;

    {Đoạn này copy y nguyên đoạn ở trên, 
     đoạn giữa hai dòng "T := T+2" và "T := T+4" xuống}
  end;

end;
```

Đoạn code trên được viết trực tiếp trên diễn đàn, chưa Compile thử, nên có gì sai sót anh em sửa hộ với nhé [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Cái trên không thể nhanh bằng sàng, nhưng được cái "thân thuộc" hơn với các bạn mới học đến xử lí số nguyên tố [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Tốc độ thì cũng tạm chấp nhận được [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## kingkonghn

Em thấy cách của em tuy chưa gọn nhưng vẫn là nhanh hơn chứ. Trong khi anh sinh hết các số nguyên tố rồi mới tiến hành xử lí thì em kiểm tra các số i=1-> n/2 nếu số nào là nguyên tố thì tiếp kiểm tra số n-i là nguyên tố thì tăng đếm. Như thế được cái là không phải tạo mảng số nguyên tố, thời gian tạo mảng số nguyên tố cũng bằng thời gian em chạy xong test rồi.
Hang_vt: giới hạn 20000 [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](!

----------


## balothuhn

@ Giang: Trên kia chỉ là đoạn code mẫu thôi, còn ứng dụng thì phải linh hoạt chứ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Thế để anh post thuật toán của anh lên nhá:

Đầu tiên là sinh các số nguyên tố từ 1->410 theo cách trên 
Sau đó thì thực hiện các dòng lệnh:


```
function Check(T:longint):boolean;
var
     i, j, k  : longint;
begin
     for i := 1 to maxN do
               if PrimeSqr[i] > T then
                      exit(true)
               else
                if T mod Prime[i] = 0 then
                      exit(false);
end;

Function Answer : longint;
var
     dem,t,k : longint;
begin
      dem := 0;
      t := 2;
   while (t <= N div 2) do
   begin
            if Check(t) and Check(N-t) then
                  inc(dem);
      t := t+2;
   end;
   exit(dem);
end;
```

Cách này đã đủ thuyết phục em chưa Giang [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## wapa

Cách của anh áp dụng 2 định lí trong topic kiểm tra tính nguyên tố em đưa ra đúng không? Cách này ổn hơn cách cơ bản vì bước nhảy không còn là 1 mà là 2 4 2 4, khi kiểm tra cũng không từ 1->sqrt mà các snt trong 1->sqrt(N). Cách này ngon rồi, không biết có cách nào tốt hơn nữa không nhỉ?

----------


## admin

Cách tốt hơn nữa thì em dùng sàng, sàng Eratosthenes hay Atkin thì tuỳ em chọn. Thuật toán sàng có lẽ đủ nhanh cho em xử lí bài toán này. Em lên Wikipedia search là có thông tin về hai thuật toán này, nếu đọc được Wiki tiếng Anh thì càng tốt [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## trungvu

*theo minh thi nen tao 1 tap hop de chua so nguyen to nho hon so n roi xet tong nhu ban da noi!!*

----------


## letien1993

Nếu mệnh đề của Gôn-Bắc được chứng minh thì khỏe quá! Cứ output 2!
---------------------------------Bài viết đã được trộn ---------------------------------
Đây, mình xin cung cấp code sàng Eratosthenes 




> Procedure Eratosthenes(n: longint; var prime: array of boolean);
> Var
> i, j: longint;
> Begin
> Fillchar(prime, sizeof(prime), true);
> prime[0]:=false; prime[1]:=false;
> i:=2;
> While (i*i<=n) do begin
> if (prime_) then begin
> ...

----------

