Giúp hướng dẫn và giải bài chúc tết

[collagenadiva]

Giúp hướng dẫn và giải 2 bài khó

Bài 2. (6,0 điểm)Dãy số đặc biệt
Dãy số A1, A2,..., AN được gọi là dãy số đặc biệt nếu nó thoả mãn các điều kiện:
· Là dãy số giảm dần;
· Với mỗi Ai thì Ai hoặc là số nguyên tố hoặc là ước của một trong các số từ A1 đến Ai-1.
Em hãy tìm dãy số đặc biệt dài nhất bắt đầu từ N.
Dữ liệu vào: Từ file văn bản DAYSO.IN là một số nguyên dương N (N < 10000).
Kết quả: Ghi ra file văn bản DAYSO.OUT là dãy số tìm được, các số ghi cách nhau bởi dấu cách.
Ví dụ:

<div style="text-align: center">DAYSO.IN
DAYSO.OUT ​

</div>12
12 11 7 6 5 4 3 2 1


Bài 3. (5,0 điểm)Tham gia SEGAME bằng xe buýt
Để phục vụ cho SEGAME 25, nước bạn Lào của chúng ta đã chuẩn bị rất chu đáo về mọi mặt, đặc biệt là phương tiện giao thông cho các vận động viên cũng như khán giả. Đất nước Lào đã xây dựng hệ thống xe buýt đi lại giữa một số địa điểm, các tuyến xe buýt đều là đường đi hai chiều. Các hoạt động của SEGAME được tổ chức ở N địa điểm (1 £ N £100) các địa điểm được đánh số từ 1 đến N. Các trạm dừng xe buýt đều được đặt ở các địa điểm tổ chức SEGAME, tất nhiên vì điều kiện không cho phép nên có một số địa điểm không có trạm xe buýt và giữa một số địa điểm không thể đi lại bằng xe buýt được. Em hãy giúp các vận động viên cũng như khán giả đến cổ vũ SEGAME xác định được từ địa điểm A đến địa điểm B nào đó có thể đi được bằng xe buýt không? Nếu đi được thì nên đi theo tuyến như thế nào để số lần dừng lại ở các trạm xe buýt là ít nhất.
D÷ liÖu v µo: Đọc tõ file v¨n b¶n XEBUYT.INP gåm:
- Dßng ®Çu tiªn lµ sè N (1 £ N £ 100);
- Dòng thứ hai ghi hai sốnguyên dương thể hiện địa điểm A và B.
- C¸c dßng tiÕp theo mçi dßng ghi hai sè i vµ j cho biÕt cã tuyến xe buýt gi÷a 2 địa điểm i vµ j.
KÕt qu¶ : Ghi ra file v¨n b¶n XEBUYT.OUTnếu không đi được ghi số -1, nếu được ghi đường đi từ A đến B qua ít trạm xe buýt nhất.

V í dụ:

<div style="text-align: center"><div style="text-align: center">XEBUYT.INP
XEBUYT.OUT
XEBUYT.INP
XEBUYT.OUT​

</div>9
2 3
1 3
1 6
2 7
3 6
4 8
6 7
8 9
2 7 6 3
9
3 8
1 3
1 6
2 7
3 6
4 8
6 7
8 9
-1
​</div>
Bài 4. (3,0 điểm) Vườn trường
Vườn trường là một hình chữ nhật gồm một số khoảnh trồng các loại cây khác nhau. Nó được mô tả là một lưới ô vuông sao cho mỗi ô của lưới được xem như chỉ có 2 trạng thái: hoặc là diện tích trồng cây, hoặc không phải. Hưởng ứng cuộc vận động xây dựng trường "Xanh - Sạch - Đẹp" học sinh khối 12 muốn quét vôi xung quanh các bức tường rào của các khoảnh vườn này. Mỗi cạnh ô vuông của lưới được quét vôi nếu nó là cạnh chung của 2 ô khác trạng thái (các cạnh thuộc biên của lưới không được tính). Lập trình tính tổng chiều dài cần quét vôi của các khoảnh vườn (theo đơn vị cạnh ô lưới).
Dữ liệu vào: Đọc từ file văn bản VUON.INP gồm:
- Dòng đầu ghi hai số nguyên dương M, N (M, N £ 200 lần lượt là số dòng và cột của lưới);
- Dòng thứ i trong số M dòng tiếp mô tả trạng thái của N ô lưới tương ứng của dòng i gồm N số: 0 (là đất trống) hoặc 1 (là diện tích trồng cây) theo đúng thứ tự các ô trong lưới.
Kết quả: Ghi ra file văn bản VUON.OUT gồm một dòng ghi giá trị tổng chiều dài cần quét vôi.
Ví dụ:

<div style="text-align: center">VUON.INP
VUON.OUT​

</div>6 11
0 0 0 1 1 0 0 0 0 0 0
0 0 1 1 1 1 0 1 0 0 0
0 0 0 1 0 0 1 1 1 1 0
0 1 0 0 0 1 1 0 1 1 0
0 1 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 1 1 1

43

[vemaybayvietmy06]

Bài đầu tiên

Program AAAA;
Uses CRT;
Var P,i,n,a,s,m,k,e:Integer;
    MANG:ARRAY[0..10000] of Integer;
    F : Text;
    H : String;
BEGIN
        Clrscr;
        Assign(F,'DAYSO.IN');
        Reset(F);
        Read(F,H);
        Val(H,P,e);
        Writeln(H);
      {  Writeln('Nhap N vao day :');
        Readln(P);}
        MANG[0]:=P;
        s:=0;
        a:=0;
        for i:=(P-1) downto 2 do
        Begin
             for n:=(i-1) downto 2 do
                if i mod n=0 then
                Begin
                        a:=1;
                        break;
                End;
             if a<>1 then
             Begin
                s:=s+1;
                MANG[s]:=i;
             End
             else
                for m:=0 to s do
                  Begin
                  if MANG[m] mod i = 0 then
                       Begin
                        s:=s+1;
                        MANG[s]:=i;
                        break;
                       end;
                  a:=0;
                  End;
       End;
       s:=s+1;
       MANG[s]:=1;
       Close(F);
       Assign(F,'DAYSO.OUT');
       Rewrite(F);
        for k:=0 to s do
          Begin
                 Write(MANG[k],' ');
                write(F,MANG[k],' ');
          End;
        Close(F);
        Readln;
END.

Hjx mới tham gia làm Pascal để thi HSG Tin mong anh em giúp đỡ nha.

[lamgiaseo]

Bài đầu tiên

Program AAAA;
Uses CRT;
Var P,i,n,a,s,m,k:Integer;
    MANG:ARRAY[0..10000] of Integer;
    F:File of Integer;
BEGIN
        Clrscr;
        Assign(F,'DAYSO.IN');
        Reset(F);
        Read(F,P);
       { Writeln('Nhap N vao day :');
        Readln(P); }
        MANG[0]:=P;
        s:=0;
        a:=0;
        for i:=(P-1) downto 2 do
        Begin
             for n:=(i-1) downto 2 do
                if i mod n=0 then
                Begin
                        a:=1;
                        break;
                End;
             if a<>1 then
             Begin
                s:=s+1;
                MANG[s]:=i;
             End
             else
                for m:=0 to s do
                  Begin
                  if MANG[m] mod i = 0 then
                       Begin
                        s:=s+1;
                        MANG[s]:=i;
                        break;
                       end;
                  a:=0;
                  End;
       End;
       s:=s+1;
       MANG[s]:=1;
       Close(F);
       Assign(F,'DAYSO.OUT');
       Rewrite(F);
        for k:=0 to s do
          Begin
                 Write(MANG[k],' ');
               write(F,MANG[k]);
          End;
        Close(F);
       Readln;
END.

Hjx mới tham gia làm Pascal để thi HSG Tin mong anh em giúp đở ngar !!

cho thuật toán trước rồi hãy code bạn nha!
bạn đã test thử trước khi post lên chưa vậy?

[innguyengia]

Mình kiểm tra rồi mới post lên, mọi người xem giùm có lỗi gì không.

[songdonggun]

Sem cái tui mới sửa đó nhé đọc đề thiếu chữ "Văn bản" _ _! Thành ra làm lộn lun

Thuật toán đơn giản là đọc 1 file text chứ số N rồi chuyển sang Int sao đó kiểm tra từ N đến 1 các số thoả yêu cầu
Nếu nó ko là số nguyên tố thì sẽ kt nó có là ước của các số từ N đến nó không
Nếu nó là số cần tìm thì cho nó vào mảng để dễ kt

[viettopcare10]

test mẫu thì đúng rồi nhưng hình như xuất ra màn hình đó bạn . bỏ clrscr và readln ở cuối đi.

[simanhdung1]

Bạn sang làm thuật toán có độ phức tạp bao nhiêu? Mình nghĩ là O(N^2), để ý cái giới hạn nha, làm thuật toán tự nhiên (O(N^2)) là toi 1 số test đó.
[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] sang lớp mấy rùi? Thi hsg bao giờ thế?

[goalkinh]

Mình nghĩ sơ sơ thuật toán có thể ăn hết test bài 1 thế này, moị người tham khảo rồi cài thử nhé:
_Tạo 1 mảng chỉ chứa các số nguyên tố từ 2-> n (tự tạo)
_1 mảng chứa các giá trị cần tìm, các phần tử của màng này được xác định như sau:
+) nếu phần tử ở mảng nguyên tố > phần tử hiện ở cuối mảng kq / 2 thì cho nó vào mảng kq, không thì tìm ước các phần tử không phải nguyên tố (dùng 1 mảng đánh dấu để bớt bước kiểm tra) và tìm từ 1/2 của ptu đó về 1, tìm được ước nào thì cho nó vào mảng, dừng lặp.
+) thực hiện tới khi cho được số 1 vào mảng kq. Dừng chương trình.
Thuật toán hơi khó về độ phức tạp, nhưng chạy rất nhanh vì bước tạo mảng nguyên tố thì dùng sàng hoặc 1 số nhận xét về số nguyên tố nên tốc độ chạy rất nhanh, còn bước bổ sung phần tử vào mảng thì có dừng ngay khi tìm thấy, kết hợp việc chọn trong mảng nguyên tố nên thời gian tổng thể để chạy chương trình rất nhanh.
Còn nếu tăng giới hạn lên 10000 thì có lẽ mình chưa tìm được thuật toán hoàn hảo.
Bài 2 đọc đau cả mắt -> chán không đọc nữa =))

[aaronmax]

Bài 4:
Đầu tiên điền 0 vào các vị trí a[0,j], a[i,0], a[n+1,j], a[i,n+1]
Duyệt mảng từ vị trí a[1,1] đến a[n,n]
Nếu a[i,j] =0 thì bỏ qua.
Nếu a[i,j] =1 thì xét tiếp các vị trí a[i-1,j], a[i,j-1], a[i+1,j], a[i,j+1] nếu gặp gía trị 0 thì tăng biến đếm.
Kết thúc mảng in biến đếm ra.

[thomtomtit]

Bài 4:
Đầu tiên điền 0 vào các vị trí a[0,j], a[i,0], a[n+1,j], a[i,n+1]
Duyệt mảng từ vị trí a[1,1] đến a[n,n]
Nếu a[i,j] =0 thì bỏ qua.
Nếu a[i,j] =1 thì xét tiếp các vị trí a[i-1,j], a[i,j-1], a[i+1,j], a[i,j+1] nếu gặp gía trị 0 thì tăng biến đếm.
Kết thúc mảng in biến đếm ra.

Thuật toán nói chung là đúng nhưng em để ý đề bài nhé, các ô biên không được tính [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Haiz, đọc đề bài 2 mới thấy là nó hơi bị dễ, chỉ có cái là đề dài đọc đau cả mắt. :|
Bài 2 (SEAGAME) dùng BFS (loang) để giải quyết nhé, cả 2 câu dùng 1 lần BFS là ok rồi.
Giờ vấn đề còn lại mỗi bài 1 thôi, với giới hạn n=10000 như thế có lẽ giải quyết được vừa đủ thời gian cho phép, nhưng giờ thử nhé, tăng giới hạn lên n<=10^5 hoặc 10^6 thì làm thế nào?