Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Mã vạch

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Mã vạch   Tue 20 Jul 2010, 15:58

Một chuỗi nhị phân S bất kì đều được coi là một mã vạch. Một chuối các kí tự liên tiếp có cùng giá trị được coi là một khoảng của mã vạch, độ dài cả chuỗi đó chính là độ rộng của khoảng.

Ví dụ:
Chuỗi 11100100101 độ dài 11 có 7 khoảng, và có độ rộng lần lượt là 3,2,1,2,1,1,1.

Yêu cầu, cho bộ ba số n,m,k:
+ Hãy cho biết có bao nhiêu mã vạch có độ dài n, có đúng m khoảng và độ rộng mỗi khoảng không vượt quá k.
+ Nếu xếp các mã trên theo thứ tự từ điển, mã S là có số thứ tự mà bao nhiêu.

Input: file mavach.inp có dạng
+ Dòng đầu: ba số n, m, k. (n<=50, m,k<=15)
+ Dòng 2: Một số t là số các mã vach cần đưa ra thứ tự
+ t dòng tiếp theo: mỗi dòng một mã vạch.
Các số cách nhau ít nhất 1 dấu cách, các mã được cho luôn hợp lệ (có đọ dài n, m khoảng, độ rộng mỗi khoảng ko quá k).

Output: file mavach.out gồm:
+ Dòng đầu: số lượng mã vạch tương ứng với bọ ba số n,m,k
+ t dòng tiếp theo: mỗi dòng một số chỉ thứ tự của mã tương ứng trong file input.

Code:
program ma_vach;
const fi='mavach.inp';
      fo='mavach.out';
var l:array[0..33,0..100] of longint;
    i,j,n,m,k,g,gt,c,h,t,sl:integer; fn,fx:text;
    s:string;

procedure timsoluong;
 begin
  for i:=1 to m do for j:=0 to n do l[i,j]:=0;
  l[0,0]:=1;

  for i:=1 to m do
  for j:=i to n do
    for g:=1 to k do
    if g<=j then
      l[i,j]:=l[i,j]+l[i-1,j-g];
  writeln(fx,l[m,n]);
 end;

procedure tinh(s:string);
 begin
  gt:=0; i:=0; g:=1;
  while g<=length(s) do
  begin
    inc(i); h:=g+1;
    while s[h]=s[h-1] do inc(h);
    j:=g; g:=h; h:=h-j;
    if i mod 2=1 then
    begin
      for c:=1 to k do
      if c<h then
        if length(s)-g+1+h-c>=0 then
        gt:=gt+l[m-i,length(s)-g+1+h-c];
    end
    else
    begin
      for c:=1 to k do
      if c>h then
        if length(s)-g+1+h-c>=0 then
        gt:=gt+l[m-i,length(s)-g+1+h-c];
    end;
  end;
  writeln(fx,gt+1);
 end;

begin
 assign(fn,fi);
 reset(fn);
 assign(fx,fo);
 rewrite(fx);
 readln(fn,n,m,k);
 timsoluong;
 readln(fn,sl);
 for t:=1 to sl do
  begin
  readln(fn,s);
  tinh(s);
  end;
 close(fn);
 close(fx);
end.


Được sửa bởi littlelee ngày Wed 21 Jul 2010, 17:50; sửa lần 1.
Về Đầu Trang Go down
whatsgoingon
Gà nhỏ


Tổng số bài gửi : 30
Join date : 18/07/2010
Age : 21
Đến từ : Nơi tận cùng vũ trụ

Bài gửiTiêu đề: Re: Mã vạch   Tue 20 Jul 2010, 20:39

Bạn admin chăm chỉ quá nhỉ ko bik thi cử thế nào chứ mình nghĩ bạn cũng thuộc dạng vô đối về tin ở độ tuổi này rồi đấy Very Happy .
Mà sao có nhiều bài bạn ko post đề lên cho mọi người tham khảo chứ phần code ko thì ko hình dung ra bài được đâu
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Mã vạch   Tue 20 Jul 2010, 21:50

Nhìn code đoán đề là một nghệ thuật đó bạn :D. Chắc bạn là thành viên mới, lâu nay ko lên 4r nên ko bt :D
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Mã vạch   Wed 21 Jul 2010, 17:25

big grin Thật xấu hổ. Bài mình làm trên trường xong post lên lun, hok kịp post đề. ^^
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Mã vạch   Wed 21 Jul 2010, 17:29

whatsgoingon đã viết:
Bạn admin chăm chỉ quá nhỉ ko bik thi cử thế nào chứ mình nghĩ bạn cũng thuộc dạng vô đối về tin ở độ tuổi này rồi đấy Very Happy .
Mà sao có nhiều bài bạn ko post đề lên cho mọi người tham khảo chứ phần code ko thì ko hình dung ra bài được đâu

Ko vô đối đâu bạn, thuộc dàng tầm thôi. Mà dẫu có vip thì cũng có câu: núi cao có nui cao hơn.
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Mã vạch   Wed 21 Jul 2010, 19:15

littlelee đã viết:
whatsgoingon đã viết:
Bạn admin chăm chỉ quá nhỉ ko bik thi cử thế nào chứ mình nghĩ bạn cũng thuộc dạng vô đối về tin ở độ tuổi này rồi đấy Very Happy .
Mà sao có nhiều bài bạn ko post đề lên cho mọi người tham khảo chứ phần code ko thì ko hình dung ra bài được đâu

Ko vô đối đâu bạn, thuộc dàng tầm thôi. Mà dẫu có vip thì cũng có câu: núi cao có nui cao hơn.

Thui lit đừng khiêm tốn nữa! ^^ một lần khiêm tốn bằng bốn lần tự kiêu đó. À mà whatisgoingon cũng ở Đà Nẵng và theo học lớp tin thì chắc phải bt lit chứ nhẩy?
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Mã vạch   Thu 22 Jul 2010, 20:23

:)) . Cậu cứ ở chỗ tớ vài bữa rồi biết, biết tình hình học tập của trần gian ý mà :)) . Khó tưởng tượng lắm ^^. Mà tớ có biết bạn kia ở đâu đâu, mà dẫu bạn ấy có ở Đà Nẵng thì đâu mắc chi phải tớ. Thi lqd tớ có 7.95 trong khi thèn thr khoa là 9.95 . trên 10 á :)) . Thế mới thầy nể . chú ý là có mopon văn và anh nữa nha. ^^
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Mã vạch   Today at 21:29

Về Đầu Trang Go down
 
Mã vạch
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến