Đội ôn thi tin học trẻ không chuyên năm 2012

Status
Không mở trả lời sau này.
M

mikelhpdatke

Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314..... (1)
Hỏi số ở vị trí thứ N trong dãy trên là số nạo Với N lấy từ File với N<=10^9.

Bài này của cuơng276 làm ko ổn đâu, giới hạn N<=10^9 đó. Không thể chạy đc, chờ chán ko ra
 
C

cuong276

mikelhpdatke said:
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314..... (1)
Hỏi số ở vị trí thứ N trong dãy trên là số nạo Với N lấy từ File với N<=10^9.

Bài này của cuơng276 làm ko ổn đâu, giới hạn N<=10^9 đó. Không thể chạy đc, chờ chán ko ra
Bấm để xem đầy đủ nội dung ...

Chờ không ra thì cũng phải chờ. Chờ đến khi nào ra mới thôi. Có kiên trì nhất định sẽ thành công. haha:p . Đùa đó. Để mình xem lại thuật toán đã. Còn bài 3 thì dễ.
 
C

cuong276

Có 2 bài này mọi người cùng giải quyết luôn nha:
Cho dãy N số tự nhiên tuỳ ý [TEX](1\leq N \leq128)[/TEX], hãy chia dãy số đó thành nhiều đoạn nhất có tổng bằng nhau.
Dữ liệu vào từ tệp BAI1.INP có nội dung:
- Dòng đầu tiên ghi số N
- Dòng tiếp theo ghi N số tự nhiên đã cho
Dữ liệu ra là tệp BAI1.out có nội dung:
- Dòng đầu tiên ghi 2 số cách nhau ký tự trống, số thứ nhất là số đoạn chia,số thứ 2 là tổng của các đoạn đã chia.
- Các dòng tiếp theo, mỗi dòng ghi các sô của mỗi đoạn vừa tìm được, các số cách nhau 1 kí tự trống.

------------------------------------------------------

Trên 1 đường thẳng ở đồng quê là 1 đường khép kín, do đó là nơi bắt đầu cũng là nơi kết thúc. Độ cao của con đường (Tính theo từng khoảng chiều dài 1 mét) được cho bởi danh sách các độ cao không đổi. Hãy tính số các đường thẳng, số các dốc lên, số các dốc xuống của đường chạy tính từ nơi xuất phát. Một đường thẳng, một dốc lên, một dốc xuống là các đoạn liên tiếp dài nhất, các đoạn bằng lên hay xuống theo hướng chạy.
Dữ liệu vào từ tệp BAI2.INP có nội dung:
- Dòng đầu tiên ghi số N chỉ chiều dài đường chạy [TEX](3\leq N \leq3000)[/TEX]
- Các dòng tiếp theo ghi các độ cao [TEX]H_i[/TEX] [TEX](1\leq i \leq N)[/TEX] của các cột (tính bằng cm) so với mực nước biển [TEX](1\leq H_i \leq 30000)[/TEX]. Mọi giá trị đều là số nguyên dương, mỗi số viết trên 1 dòng.
Dữ liệu ra là tệp BAI2.OUT chứa 3 số nguyên chỉ số đường thẳng bằng, số dốc lên, số dốc xuống theo thứ tự, mỗi số cách nhau 1 kí tự trống.
Ví dụ:
Tệp BAI2.INP
6
20
23
60
50
50
12
Tệp BAI2.OUT
1 2 2
 
Last edited by a moderator:
M

mikelhpdatke

Định đánh trống lảng bài 2 kia hả :))
Có 2 bài này mọi người cùng giải quyết luôn nha:
Cho dãy N số tự nhiên tuỳ ý (1\leq N \leq128), hãy chia dãy số đó thành nhiều đoạn nhất có tổng bằng nhau.
Dữ liệu vào twuf tệp BAI1.INP có nội dung:
- Dòng đầu tiên ghi số N
- Dòng tiếp theo ghi N số tự nhiên đã cho
Dữ liệu ra là tệp BAI1.out có nội dung:
- Dòng đầu tiên ghi 2 số cách nhau ký tự trống, số thứ nhất là số đoạn chia,số thứ 2 là tổng của các đoạn đã chia.
- Các dòng tiếp theo, mỗi dòng ghi các sô của mỗi đoạn vừa tìm được, các số cách nhau 1 kí tự trống.
Bấm để xem đầy đủ nội dung ...

Bài này dùng QHĐ tìm tổng của các dãy con. Bạn định làm thế nào
 
C

cuong276

Bài này dùng QHĐ thì dễ làm hơn. Để ngày kia mình làm vì ngày kia thì cô mình mới dạy cho QHĐ. Còn cái bài 2 của bạn dùng thuật toán chia để trị à? OK Để ngày kia làm luôn vì ngày kia mới học các thuật toán này. Còn bài 3 của bạn thì dễ mà. Chỉ cần đổi là xong.
 
M

mikelhpdatke

Đó cũng là 1 cách mình nghĩ thôi, có khi có cách khác. Vì thuật khởi tạo đó dang dấp thuật của bài 1 trong đề thi 2010
 
Q

quanghero100

cuong276 said:


Trên 1 đường thẳng ở đồng quê là 1 đường khép kín, do đó là nơi bắt đầu cũng là nơi kết thúc. Độ cao của con đường (Tính theo từng khoảng chiều dài 1 mét) được cho bởi danh sách các độ cao không đổi. Hãy tính số các đường thẳng, số các dốc lên, số các dốc xuống của đường chạy tính từ nơi xuất phát. Một đường thẳng, một dốc lên, một dốc xuống là các đoạn liên tiếp dài nhất, các đoạn bằng lên hay xuống theo hướng chạy.
Dữ liệu vào từ tệp BAI2.INP có nội dung:
- Dòng đầu tiên ghi số N chỉ chiều dài đường chạy [TEX](3\leq N \leq3000)[/TEX]
- Các dòng tiếp theo ghi các độ cao [TEX]H_i[/TEX] [TEX](1\leq i \leq N)[/TEX] của các cột (tính bằng cm) so với mực nước biển [TEX](1\leq H_i \leq 30000)[/TEX]. Mọi giá trị đều là số nguyên dương, mỗi số viết trên 1 dòng.
Dữ liệu ra là tệp BAI2.OUT chứa 3 số nguyên chỉ số đường thẳng bằng, số dốc lên, số dốc xuống theo thứ tự, mỗi số cách nhau 1 kí tự trống.
Ví dụ:
Tệp BAI2.INP
6
20
23
60
50
50
12
Tệp BAI2.OUT
1 2 2
Bấm để xem đầy đủ nội dung ...
Mã: 
uses crt;
var a:array[1..3000] of integer;
    n,i,j,l,x,b,k:integer;
procedure input;
var f:text;
begin
  assign(f,'bai2.inp');
  reset(f);
  readln(f,n);
  for i:=1 to n do
    readln(f,a[i]);
  close(f);
end;
procedure xuli;
begin
  x:=0;
  l:=0;
  b:=0;
  i:=1;
  repeat
    if i=n then break;
    if a[i+1]>a[i] then
      begin
         inc(l);
         k:=a[i+1]-a[i];
         repeat
             inc(i);
         until (a[i+1]-a[i]<>k) or (i=n);
      end;
    if i=n then break;
    if a[i+1]<a[i] then
      begin
         inc(x);
         k:=a[i+1]-a[i];
         repeat
             inc(i);
         until (a[i+1]-a[i]<>k) or (i=n);
      end;
    if i=n then break;
    if a[i+1]=a[i] then
      begin
         inc(b);
         repeat
             inc(i);
         until (a[i+1]-a[i]<>0) or (i=n);
      end;
  until i=n;
end;
procedure output;
var f:text;
begin
  assign(f,'bai2.out');
  rewrite(f);
  write(f,b,' ',l,' ',x);
  close(f);
end;
begin
  input;
  xuli;
  output;
end.
 
Last edited by a moderator:
C

cuong276

Bài 2 em làm như thế này cũng ra kết quả. Anh kiểm tra hộ em xem thử đúng không nha
Mã: 
var f,g:text;
    b,c,d,n,i:integer;
    a:array[1..100]of integer;
begin
     assign(f,'bai2.inp');
     reset(f);
     readln(f,n);
     for i:=1 to n do readln(f,a[i]);
     close(f);
     assign(g,'bai2.out');
     rewrite(g);
     b:=0;
     c:=0;
     d:=0;
     for i:=1 to n-1 do
         begin
              if a[i]<a[i+1] then inc(c);
              if a[i]=a[i+1] then inc(b);
              if a[i]>a[i+1] then inc(d);
         end;
     write(g,b,' ',c,' ',d);
     close(g);
end.
 
Q

quanghero100

cuong276 said:
Bài 2 em làm như thế này cũng ra kết quả. Anh kiểm tra hộ em xem thử đúng không nha
Mã: 
var f,g:text;
    b,c,d,n,i:integer;
    a:array[1..100]of integer;
begin
     assign(f,'bai2.inp');
     reset(f);
     readln(f,n);
     for i:=1 to n do readln(f,a[i]);
     close(f);
     assign(g,'bai2.out');
     rewrite(g);
     b:=0;
     c:=0;
     d:=0;
     for i:=1 to n-1 do
         begin
              if a[i]<a[i+1] then inc(c);
              if a[i]=a[i+1] then inc(b);
              if a[i]>a[i+1] then inc(d);
         end;
     write(g,b,' ',c,' ',d);
     close(g);
end.
Bấm để xem đầy đủ nội dung ...
với bộ test trên kia thì đúng nhưng với bộ test này thì sai em kiểm tra lại nha anh tao bộ test mới nè
bai2.inp
8
20
23
26
60
50
50
12
1
bai2.out
1 2 3
giải thích bộ test
đoạn bằng là 50->50
đoạn dốc lên 1: 20->23->26
đoạn dốc lên 2: 26->60
đoạn dốc xuống 1: 60->50
đoạn dốc xuống 2: 50->12
đoạn dốc xuống 3: 12->1
bài test của em ra kết quả là 1 3 3 nên bị sai :) :) điều chỉnh lại nhé
 
C

cuong276

Ha ha ha. Cuối cùng thì cũng sửa xong. Mọi người xem có chỗ nào sai không nha.
Mã: 
var f,g:text;
    b,c,d,n,i:integer;
    a:array[1..100]of integer;
begin
     assign(f,'bai2.inp');
     reset(f);
     readln(f,n);
     for i:=1 to n do readln(f,a[i]);
     close(f);
     assign(g,'bai2.out');
     rewrite(g);
     b:=0;
     c:=0;
     d:=0;
     for i:=1 to n-1 do
         begin
              if (a[i]<a[i+1]) and (a[i+1]<a[i+2]) then dec(c);
              if (a[i]=a[i+1]) and (a[i+1]=a[i+2]) then dec(b);
              if (a[i]>a[i+1]) and (a[i+2]>a[i+1]) then dec(d);
              if a[i]<a[i+1] then inc(c);
              if a[i]=a[i+1] then inc(b);
              if a[i]>a[i+1] then inc(d);
         end;
     if a[n]<a[1] then inc(c);
     if a[n]=a[1] then inc(b);
     if a[n]>a[1] then inc(d);
     write(g,b,' ',c,' ',d);
     close(g);
end.
 
Q

quanghero100

cuong276 said:
Ha ha ha. Cuối cùng thì cũng sửa xong. Mọi người xem có chỗ nào sai không nha.
Mã: 
var f,g:text;
    b,c,d,n,i:integer;
    a:array[1..100]of integer;
begin
     assign(f,'bai2.inp');
     reset(f);
     readln(f,n);
     for i:=1 to n do readln(f,a[i]);
     close(f);
     assign(g,'bai2.out');
     rewrite(g);
     b:=0;
     c:=0;
     d:=0;
     for i:=1 to n-1 do
         begin
              if (a[i]<a[i+1]) and (a[i+1]<a[i+2]) then dec(c);
              if (a[i]=a[i+1]) and (a[i+1]=a[i+2]) then dec(b);
              if (a[i]>a[i+1]) and (a[i+2]>a[i+1]) then dec(d);
              if a[i]<a[i+1] then inc(c);
              if a[i]=a[i+1] then inc(b);
              if a[i]>a[i+1] then inc(d);
         end;
     if a[n]<a[1] then inc(c);
     if a[n]=a[1] then inc(b);
     if a[n]>a[1] then inc(d);
     write(g,b,' ',c,' ',d);
     close(g);
end.
Bấm để xem đầy đủ nội dung ...

Vẫn chưa đúng đâu em à thử test này nhé
bai1.inp
8
1
2
4
2
1
2
5
3
bai2.out
0 4 3
giải thích
bằng không có
lên: 1->2; 2->4; 1->2; 2->5
xuống: 4->2; 2->1; 5->3
bài của em test ra kết quả là: 0 2 3
 
C

cuong276

Lại sai. Bực cả mình. Lần này thì không thể sai nữa nè :D;):p
Mã: 
uses crt;
var a:array[1..3000] of integer;
    n,i,j,l,x,b,k:integer;
procedure input;
var f:text;
begin
  assign(f,'bai2.inp');
  reset(f);
  readln(f,n);
  for i:=1 to n do
    readln(f,a[i]);
  close(f);
end;
procedure xuli;
begin
  x:=0;
  l:=0;
  b:=0;
  i:=1;
  repeat
    if i=n then break;
    if a[i+1]>a[i] then
      begin
         inc(l);
         k:=a[i+1]-a[i];
         repeat
             inc(i);
         until (a[i+1]-a[i]<>k) or (i=n);
      end;
    if i=n then break;
    if a[i+1]<a[i] then
      begin
         inc(x);
         k:=a[i+1]-a[i];
         repeat
             inc(i);
         until (a[i+1]-a[i]<>k) or (i=n);
      end;
    if i=n then break;
    if a[i+1]=a[i] then
      begin
         inc(b);
         repeat
             inc(i);
         until (a[i+1]-a[i]<>0) or (i=n);
      end;
  until i=n;
end;
procedure output;
var f:text;
begin
  assign(f,'bai2.out');
  rewrite(f);
  write(f,b,' ',l,' ',x);
  close(f);
end;
begin
  input;
  xuli;
  output;
end.
 
Last edited by a moderator:
Q

quanghero100

sao cái mảng anh khai báo ngắn thế nhở :S:S:S lúc nảy khai báo 100 phần tử nhưng chắc tại gõ thiếu :D mới sửa lại 3000 phần tử rùi đấy giờ thì đạt yêu cầu đề bài rùi hjhj
 
C

cuong276

Hi hi. Chép bài của anh thật không xứng là quân tử. Để ngày mai em sẽ nghĩ mọi cách để sửa lại cách làm của em. Phải cho chạy được mới thôi.Còn bây giờ làm bài 1 đã. Hj hj
 
M

mikelhpdatke

Thử làm đi, xem thuật QHĐ của cuơng thế nào :)). Những bài kiểu này áp dụng thuật QHĐ bài toán chia kẹo :))
 
C

cuong276

Muốn xem thuật toán QHĐ có 1 không 2 của ta hả? Ha Ha Ha. Đợi ngày kia nha. Mai mình nghỉ, ngày kia cô mới dạy. Đọc trên mạng thì không hiểu cái gì cả, cô giảng dễ hiểu hơn
 
Q

quanghero100

bài 1 thì hơi khó thật anh cũng chưa làm ra. Lúc đầu cứ tưởng các đoạn được chia có số phần tử bằng nhau đọc kĩ lại mí hiểu :) :)
 
M

mikelhpdatke

cuong276 said:
Muốn xem thuật toán QHĐ có 1 không 2 của ta hả? Ha Ha Ha. Đợi ngày kia nha. Mai mình nghỉ, ngày kia cô mới dạy. Đọc trên mạng thì không hiểu cái gì cả, cô giảng dễ hiểu hơn
Bấm để xem đầy đủ nội dung ...

Hóa ra học từ "thầy" ah`, tưởng tự nghĩ cơ :)). Mấy thuật này tớ đọc từ ebook hết, sau đó tự hiểu và biến đổi cho phù hợp với đầu bài :))
 
Status
Không mở trả lời sau này.
Top Bottom