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

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

thiennu274

Gốc toạ độ đặt tại điểm A(0;0). ROBOT sẽ xuất phát từ điểm R(xo;yo), mặt hướng về phía cạnh BC và phải đi theo một chương trình định sẵn.
Chương trình lập sẵn cho ROBOT là một xâu kí tự bao gồm dãy các lệnh có dạng Cm, được gọi là lệnh đơn, hoặc (U)m trong đó C là một trong các chữ cái Q, q, D hoặc d, m là một số tự nhiên, U là một lệnh phức được tạo ra từ một dãy lệnh đơn hoặc lệnh phức. Các lệnh đơn có ý nghĩa như sau:
+ Dm: Là tiến về phía trước m ô, mỗi bước là một lần di chuyển từ một điểm đến một điểm kế tiếp theo hướng đang nhìn của ROBOT.
+ dm: Lùi lại về phía sau m bước
+ Qm: ROBOT sẽ quay người m lần, mỗi lần qua một góc 450 theo chiều kim đồng hồ.
+ qm: ROBOT quay người m lần, mỗi lần 1 góc 450 ngược chiểu kim đồng hồ.
+(U)m: Là ROBOT thực hiện m lần dãy lệnh U.
ở đây qui ước nếu m=1 thì có thể không cần viết giá trị của m. Nếu m=0 thì đoạn lệnh tương ứng đặt trước m sẽ được bỏ qua (ROBOT không phải thực hiện).
Dữ liệu vào: Cho trong File ROBOT.INP gồm 2 dòng:
+ Dòng 1: Chứa 2 số tự nhiên x0 y0 cách nhau một dấu cách cho biết vị trí xuất phát của ROBOT.
+ Dòng 2: Chương trình điều khiển của ROBOT. (Độ dài không vượt quá 250 kí tự)
Kết quả ghi ra File ROBOT.OUT gồm 1 dòng chứa 2 số tự nhiên x1 y1 cách nhau một dấu cách cho biết vị trí kết thúc của ROBOT sau khi hoàn thành chương trình di chuyển.
Ví dụ:
ROBOT.INP
5 10
(D50Q2D50q3d50qD100)10d2
ROBOT.OUT
5 12


Cái đề chính của nó đấy. Bỏ qua phần tệp nhaz. MÌnh đang gặp rắc rối chỗ xử lý ngoặc :(
 
M

mikelhpdatke

Tạm thời để mình nghĩ sau. Thứ 6 mình thi loại rồi, ai có tài liệu lý thuyết tin ko cho mình xem với :D
 
C

cuong276

Mình có bài này nè:
Cuội viết liên tiếp các số tự nhiên từ 1 đến n thành dãy: 123...n. Cuội đố Bờm điền các dấu phép toán + hoặc - vào giữa 2 số tự nhiên liên tiếp sao cho biểu thức thu được có kết quả bằng 0.
Yêu cầu: Bạn hãy giúp Bờm viết chương trình liệt kê tất cả các cách điền dấu phép toán thích hợp.
Dữ liệu: vào từ file bai4.inp gồm 1 dòng duy nhất ghi số n.n<10
Kết quả: Ghi ra file văn bản có tên bai4.out:
Dòng đầu tiên ghi số m là số cách điền dấu vào biểu thức.
m dòng tiếp theo, mỗi dòng ghi 1 kết quả tìm được
 
M

mikelhpdatke

Chưa biết bài này có thuật toán gì đặc biệt ko nhưng bí quá dùng quay lui bạn ah`
 
C

cuong276

Dạng quay lui thì mình đã có đọc qua nhưng không hiểu cho lắm. Đây cũng là bài toán dạng quay lui đầu tiên mà mình làm
 
M

mikelhpdatke

Tổng tất cả các số từ 1 -> n. Nếu Odd thì ko có lời giải. Còn nếu even ( chẵn) thì. Dùng QHĐ tính tổng dãy con sao cho tổng dãy con này = (tông các số 1->n ) div 2. Sau đó với mỗi phần tử của dãy con này đặt dấu trừ đằng trước là ok
 
C

cuong276

Mình chưa học. hì hì hì. Minhf cũng có đọc trên mạng nhưng họ viết cái gì gì đó khó hiểu quá. Nếu cậu có thời gian thì post code lên đi. Mình sẽ thanks.
 
1

11thanhkhoeo

Mã: 
uses crt ;
var a:array [1..256] of integer;
   n,tong,dem,k:integer;



procedure xuat;
     begin
        for k:=1 to n do
          write(a[k]);
     end;
procedure thu(i:integer);
var j:integer;
  begin
      for j:=-1 to 1 do
         if abs(j)=1 then
            begin
                a[i]:=i*j;
                tong:=tong+a[i];
                if (i=n) and (tong=0) then
                  begin
                     xuat;
                     dem:=1;
                  end
                    else
                      thu(i+1);
                tong:=tong-a[i];
            end;
   end;
begin
   clrscr;
   write('nhap n');
   readln(n);
   a[1]:=1;
   tong:=1;
     thu(2);
     if dem = 0 then write(' khong the ');
   readln
end.
 
C

cuong276

Anh Thành ới ời ơi! Chương trình anh làm em thử chạy nhưng nó thoát luôn cả pascal là sao anh?
 
Q

quanghero100

đây là bài làm theo cách quay lui :D:D
Mã: 
uses crt;
var n,k:integer;
    a:array[1..100] of integer;
    b,c:array[1..100] of char;
    f1,f2:text;
procedure openfile;
var i:integer;
begin
   assign(f1,'bai4.inp');
   reset(f1);
   assign(f2,'bai4.out');
   rewrite(f2);
   readln(f1,n);
   for i:=1 to n do a[i]:=i;
   b[1]:='+'; b[2]:='-'; k:=0;
end;
procedure closefile;
begin
  close(f1);
  close(f2);
end;
procedure xuat;
var i:integer;
begin
    for i:=1 to n-1 do
      write(f2,i,c[i]);
    writeln(f2,n);
end;
procedure try(i:integer);
var j,h,t:integer;
begin
   for  j:=1 to 2 do
      begin
         c[i]:=b[j];
         if i=n-1 then
            begin
               h:=1;
               t:=h;
               repeat
                   inc(h);
                   if c[h-1]='+' then t:=t+h else t:=t-h;
               until h=n;
               if t=0 then
                  begin
                     xuat;
                     inc(k);
                  end;
            end else try(i+1);
      end;
end;
begin
    openfile;
    try(1);
    if k=0 then writeln(f2,'khong co cach bieu dien') else writeln(f2,k);;
    closefile;
end.
 
M

mikelhpdatke

Cho mấy bác vài bài pascal đơn giản để luyện :D

1. kiểm tra số nguyên dương n có toàn chữ số lẻ hay không ?

2. Hãy tính tổng các chữ số của số nguyên dương n

3. Liệt kê tất cả các dãy nhị phân chiều dài bằng n

4. Cho dãy n số nguyên và một số k, xuất ra tất cả các dãy con giảm có k phần tử (dãy con có thể liên tiếp hoặc không liên tiếp và có thể có phần tử trùng).
Ví dụ: dãy 5 2 4 3 1 có các dãy con 3 phần tử và giảm là: 5 2 1; 5 4 3; 5 4 1; 5 3 1; 4 3 1

5. Cho dãy n số nguyên, xuất ra dãy con tăng dài nhất (dãy con có thể liên tiếp hoặc không liên tiếp và có thể có phần tử trùng). Nếu có nhiều dãy con tăng dài bằng nhau thì chỉ xuất ra một dãy.
Ví dụ: dãy 7, 3, 2, 4, 1, 6, 5, 8 có dãy con tăng dài nhất là: 3, 4, 6, 8 có chiều dài là 4.
còn nữa, khi nào có thời gian mình sẽ post tiếp

Khuyến khích bài 5 dùng QHĐ nha :))
 
Q

quanghero100

Bài 5:
Mã: 
uses crt;
var a,T,L:array[0..100] of integer;
    n:integer;
procedure nhap;
var i:integer;
begin
  write('n='); readln(n);
  for i:=1 to n do
    read(a[i]);
  readln;
end;
procedure QHD;
var i,j,jmax:integer;
begin
 a[0]:=-32768; a[n+1]:=32767;   L[n+1]:=1;
 for i:=n downto 0 do
   begin
     jmax:=n+1;
     for j:=i to n+1 do
        if (a[j]>a[i]) and (L[j]>L[jmax]) then jmax:=j;
          L[i]:=L[jmax]+1;
          T[i]:=jmax;
   end;
   writeln(L[0]-2);
end;
procedure truyvet;
var i:integer;
begin
  i:=T[0];
  while i<>n+1 do
    begin
       write(a[i],' ');
       i:=T[i];
    end;
end;
begin
   clrscr;
   nhap;
   QHD;
   truyvet;
   readln;
end.
 
N

ngobin3

Bài 1:

Mã: 
int KTToanLe (int n)  
  {  
        if (n%2==0 && n!= 0) 
              return 0; 
        if (n%2==1)  
                return KTToanLe (n/10);  
      return 1;  
  }
 
Last edited by a moderator:
M

mikelhpdatke

Bài 3:
Mã: 
var n:longint;
function dequi(k:longint;ok:boolean):boolean;
begin
if (k<1) or not(ok) then
dequi:=ok
else
begin
if k mod 2 =0 then
ok:=false;
dequi:=dequi(k div 10,ok);
end;
end;
begin
write('n = ');
read (n);
if dequi(n,true) then
write('Toan so le')
else write('Co so chan')
end.


c2:
Mã: 
var n:longint;
function dequi(k:longint):longint;
begin
if k=0 then
dequi:=0
else
dequi:=(k mod 10)+dequi(k div 10);
end;
begin
write('n = ');
read (n);
write('Tong: ',dequi(n))
end.
Bài 4:
Mã: 
Program LT;
Var A,B:array[0..100] Of integer;
n,k:integer;

Procedure Init;
Var i:integer;
Begin
  Readln(n,k);
  For i:=1 to n do readln(A[i]);
  B[0]:=0;
End;
Procedure PrintResult;
Var l:integer;
 Begin
    For l:=2 to k do If A[B[l]]>A[B[l-1]] then exit;
  For l:=1 to k do write(A[B[l]]);writeln;
 End;

Procedure Install(i:integer);
Var j:integer;
 Begin
  For j:=B[i-1]+1 to n-k+i do
     Begin
          B[i]:=j;
          If i=k then PrintResult
          Else
           Install(i+1);
     End;
 End;


BEGIN
Init;
Install(1);
readln
end.
 
M

mikelhpdatke

Dãy con chung không liền kề dài nhất

Dãy C = c1, c2, ..., ck là dãy con không liền kề của dãy A = a1, a2, ..., am nếu C có thể nhận được bằng cách chọn một dãy các phần tử không liền kề của A, nghĩa là tìm dược dãy các chỉ số i1, i2, ..., ik sao cho:

1 ≤ i1, i2, ..., ik ≤ m;
i1 < i2 - 1, i2 < i3 - 1, ..., ik - 1 < ik - 1;
c1 = ai1, c2 = ai2, ck = aik.

Ta gọi độ dài của dãy số là số phần tử của nó.

Cho hai dãy:
A = a1, a2, ..., am
và
B = b1, b2, ..., bn

Dãy C được gọi là dãy con chung không liền kề của hai dãy A và B nếu như nó vừa là dãy con không liền kề của A, vừa là dãy con không liền kề của B.
Yêu cầu

Cho hai dãy số A và B. Hãy tìm độ dài của dãy con chung không liền kề dài nhất của hai dãy đã cho.
Dữ liệu

Dòng đầu tiên chứa hai số nguyên dương m và n (2 ≤ m, n ≤ 103) được ghi cách nhau bởi dấu cách, lần lượt là số lượng phần tử của dãy A và dãy B.
Dòng thứ i trong m dòng tiếp theo chứa số nguyên không âm ai (ai ≤ 104), i = 1, 2, ..., m.
Dòng thứ j trong n dòng tiếp theo chứa số nguyên không âm bj (bj ≤ 104), j = 1, 2, ..., n.

Kết quả

Ghi ra trên một dòng duy nhất độ dài của dãy con chung không liền kề dài nhất của hai dãy A và B.
Ví dụ

Input:
4 5
4
9
2
4
1
9
7
3
4

Output:
2

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

Chữ số tận cùng khác 0
Mã bài: TCDFZ

Cho số tự nhiên n (n <= 10^9). Hãy tìm chữ số tận cùng khác 0 của n!
Input

- Dòng duy nhất ghi số N.
Output

- Gồm 1 dòng duy nhất ghi kết quả tìm được.
Example

Input:
5

Output:
2
----------------------------------
Hội trường
Mã bài: NKREZ

Nhà trường có một phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu và thời điểm kết thúc. Nhà trường có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: hãy giúp nhà trường chọn các yêu cầu sử dụng hội trường sao cho tổng thời gian hội trường được sử dụng là lớn nhất.
Dữ liệu

Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10000), số yêu cầu.

Mỗi dòng trong số n dòng tiếp theo chứa 2 số nguyên dương p và k (0 ≤ p < k ≤ 30000), mô tả một yêu cầu bắt đầu tại thời điểm p và kết thúc tại thời điểm k.
Kết qủa

Gồm một dòng duy nhất là tổng thời gian lớn nhất mà hội trường được sử dụng
Ví dụ

Dữ liệu:
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Kết qủa
16
------------------------------
Dãy con dài nhất
Mã bài: NKMAXSEQ

Cho dãy số nguyên a1, a2, …, an.

Dãy số ai, ai+1, …, aj với 1 ≤ i ≤ j ≤ n được gọi là dãy con của dãy số đã cho và khi đó, j-i+1 được gọi là độ dài, còn ai+ai+1...+aj được gọi là trọng lượng của dãy con này.

Yêu cầu: cho số nguyên p, trong số các dãy con của dãy số đã cho có trọng lượng không nhỏ hơn p hãy tìm dãy con có độ dài lớn nhất.
Dữ liệu vào

Dòng đầu tiên ghi hai số nguyên n và p cách nhau bởi dấu cách.
Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ai là số hạng thứ i của dãy số đã cho, i = 1, 2, …, n.

Kết qủa

Ghi ra số nguyên k là độ dài của dãy con tìm được (qui ước: nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì k = -1).
Hạn chế

Trong tất cả các test: 1 ≤ n ≤ 50000; |ai| ≤ 20000; |p| ≤ 109. Có 50% số lượng test với n ≤ 2000.
Ví dụ

Dữ liệu mẫu
5 6
-2
3
2
-2
3

Kết qủa
4

Dữ liệu mẫu
4 9
2
3
2
-2

Kết qủa
-1
 
C

cuong276

Mình nghĩ ra cái thuật toán của bài 1 hình như sai thì phải. Mọi người thử xem nha. Cho tất cả các số có chỉ số chẵn của a vào 1 mảng sau đó cũng làm tương tự với b. So sánh 2 mảng đó nếu số nào bằng nhau thì tăng biến đếm. Sau đó xét với các số chỉ số lẻ của b rồi của a. Mình nhìn qua hình như sai thì phải.
 
Status
Không mở trả lời sau này.
Top Bottom