Tin học Pascal

S

skyl0v3

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Bài tập này mình đã giải đc rồi nhưng chương trình còn dài và không thỏa mãn yêu cầu thời gian với những test lớn, các pro giúp mình với:


Bài toán: Phòng ngủ của Gholam đc lát bằng các viên gạch màu trắng và màu vàng. Mỗi khi buồn chán Gholam đứng ở 1 ô màu trắng và nghĩ ra số nguyên N rồi bước đi thẳng theo hàng đó N bước, nếu gặp tường thì quay 180 độ và đi tiếp. Trong khi thực hiện các bước đi Gholam đếm số lần bước trên ô mầu vàng. Các viên gạch đc đánh số thứ tự từ 1 đến m theo thứ tự từ trái qua phải

Dữ liệu vào:
- Dòng 1 ghi 2 số nguyên m, N ( 3\leq m \leq100 ) ( 1\leq n \leq 1000000000)
- Dòng 2 chứa m số nguyên a1, a2,... , am, ai= 0 ứng với viên màu vàng, ai\geq 1 ứng với ô màu trắng, ai= 2 có nghĩa là gholam đag đứng ở ô i và quay mặt về phía bên phải, ai= 3 nghĩa là gholam đag đứng ở ô i và quay mặt về phía bên trái. Dữ liệu đảm bảo chỉ có duy nhất 1 số ai > 1

Kết quả: Ghi ra file 1 số nguyên duy nhất là số ô mầu vàng mà Gholam đã bước lên


Ví dụ

yellow.inp

6 7
0 1 2 0 1 0

yellow.out

3


Giúp mình với nha, mai phải nộp rùi, tks
 
S

skyl0v3

Đứng ở ô màu trắng có đánh số 2 hoặc 3 đó bạn, đọc kĩ đề bài có nói đó, mình dùng div và mod nhưng không chạy nổi với dữ liệu lớn trong 1 giây :( Bạn có thể code cho mình thử xem k?
 
S

skyl0v3

Ta có nhận xét này nhé. Giả sử ta đã giải đc bài toán khi Gholam hướng mặt sang phải tức là có 1 số ai =2 . Khi đó trong trường hợp Gholam hướng mặt sang trái, ta chỉ cần đảo ngược sâu chứa các kí tự là các số biểu thị mầu gạch trog input ta đc 1 bài toán tương tự như với ai= 2 => Bài toán thu gọn chỉ còn 1 trường hợp :)
 
S

skyl0v3

May quá, thầy giáo cho nợ bài này :D Mà sao chẳng có pro nào giúp vậy hic hic. Nhưng mình cũng nghĩ ra thuật toán ( mình nghĩ là tối ưu ) rồi:

Mã: 
program yellow;
const
  fi= 'yellow.in';
  fo= 'yellow.out';
var
  m, n, t: longint;
  a: array[1..100] of integer;
  s: string;

PROCEDURE doc;
var
  f: text;
  i: integer;
  c: string;
begin
  assign(f,fi); reset(f);
  s:='';
  readln(f,m,n);
  for i:=1 to m do read(f,a[i]);
  for i:= 1 to m do
    begin
      str(a[i],c);
      s:= s+c;
    end;
  close(f);
end;


PROCEDURE xuly;
var
  i, j, cs, l, y: integer;
  s1: string;
begin
  t:= 0;   y:= 0;
  for i:= 1 to m do if s[i]= '3' then
    begin
      s1:= '';
      for j:= length(s) downto 1 do s1:= s1+ s[j];
      s:= s1;
      break;
    end;
  s1:= '';
  for i:= 1 to m do if (s[i]= '2') or (s[i]= '3') then cs:= i;
  for i:= cs+ 1 to m do s1:= s1+ s[i];
  for i:= m-1 downto 1 do s1:= s1+ s[i];
  for i:= 2 to cs do s1:= s1+ s[i];
  l:= length(s1);
  for i:= 1 to l do if s1[i]='0' then y:= y+1;
  t:= t+ (n div l)*y;
  for i:= 1 to (n mod l) do
    if s1[i]= '0' then t:= t+1;
end;

procedure ghi;
var
  f: text;
begin
  assign(f,fo); rewrite(f);
  writeln(f,t);
  close(f);
end;

begin
  doc;
  xuly;
  ghi;
end.
 
You must log in or register to reply here.
Top Bottom