Lăn xúc xắc-Đề thi tin học trẻ toàn quốc 2012

G

gangoinocnha

[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.

Đấy là link của đề này:http://www.mediafire.com/?2h60lww7qezt8sa
Trong đó có đề và có cả chương trình của bài lăn xúc xắc.Nhưng đoạn chương trình sử dụng những câu lệnh mà mình chưa học và viết bằng tiếng anh.Bạn nào nghĩ ra thuật toán tối ưu để có thể chạy những test cuối thì giúp mình với(có đoạn code càng tốt),(bài này khó khăn ở những test cuối)
Cảm ơn vì các bạn đã quan tâm
 
C

cuong276

Mã: 
{$MODE OBJFPC}
{$R-,Q-,S-,I-}
{$OPTIMIZATION LEVEL2}
{$INLINE ON}
program RollingDice;
const
  InputFile  = 'ROLLING.INP';
  OutputFile = 'ROLLING.OUT';
  circle = 48;
  Radix = Round(1E8);
  gd = 8;
  nd = 5;

type
  TDice = record
    face, left, up: Integer;
  end;
  TNumber = array[0..nd - 1] of Int64;
var
  n: Int64;
  fi, fo: TextFile;
  dice: TDice;
  layer: array[1..3 * circle - 1] of TNumber;
  res: TNumber;

procedure Init;
begin
  with dice do
    begin
      face := 5;
      left := 1;
      up := 3;
    end;
end;

procedure RollRight; inline;
var
  temp: Integer;
begin
  with dice do
    begin
      temp := face;
      face := left;
      left := 7 - temp;
    end;
end;

function MultiRollRights(count: Int64): Int64;
var
  i: Integer;
  rep: Int64;
begin
  rep := count div 4;
  Result := Int64(rep) * 14;
  for i := 1 to count - rep * 4 do
    begin
      RollRight;
      Inc(Result, 7 - dice.face);
    end;
end;

procedure RotateCCW; inline;
var
  temp: Integer;
begin
  with dice do
    begin
      temp := left;
      left := up;
      up := 7 - temp;
    end;
end;

function FillBorder(n: Int64): Int64;
begin
  if n = 0 then Exit(0);
  Result := MultiRollRights(n);
  if n <= 1 then Exit;
  RotateCCW;
  Result := Result + MultiRollRights(n - 1);
  RotateCCW;
  Result := Result + MultiRollRights(n - 1);
  RotateCCW;
  if n <= 2 then Exit;
  Result := Result + MultiRollRights(n - 2);
  RotateCCW;
end;

operator := (x: Int64): TNumber;
var
  i: Integer;
begin
  FillChar(Result, SizeOf(Result), 0);
  for i := 0 to nd - 1 do
    begin
      Result[i] := x mod Radix;
      x := x div Radix;
    end;
end;

operator := (a: TNumber): AnsiString;
var
  s: string;
  i: Integer;
begin
  Result := '';
  for i := 0 to nd - 1 do
    begin
      Str(a[i]:gd, s);
      Result := s + Result;
    end;
  for i := 1 to Length(Result) do
    if not (Result[i] in ['0'..'9']) then Result[i] := '0';
  i := 1;
  while (i < Length(Result)) and (Result[i] = '0') do Inc(i);
  Delete(Result, 1, i - 1);
end;

operator *(const a, b: TNumber): TNumber;
var
  carry: Int64;
  i, j, k: Integer;
begin
  FillChar(Result, SizeOf(Result), 0);
  for i := 0 to nd - 1 do
    for j := 0 to nd - 1 - i do //i + j < nd
      begin
        k := i + j;
        Result[k] := Result[k] + a[i] * b[j];
        while Result[k] > Radix do
          begin
            carry := Result[k] div Radix;
            Result[k] := Result[k] mod Radix;
            Result[k + 1] := Result[k + 1] + carry;
            Inc(k);
          end;
      end;
end;

operator +(const a, b: TNumber): TNumber;
var
  carry: Int64;
  i: Integer;
begin
  carry := 0;
  for i := 0 to nd - 1 do
    begin
      carry := a[i] + b[i] + carry;
      Result[i] := carry mod Radix;
      carry := carry div Radix;
    end;
end;

{
Thuat toan:
* Lop k = khung kich thuoc k x k
* Neu dien theo tung lop, lop n co trang thai khoi dau giong lop n - 48
* => cac so tren tung hang/cot cua lop i bo di 48 so se la
  cac so tren tung hang/cot cua lop i - 48
* 48 so bo di co tong bang 12 x 14 = 168
  (do moi chu ky do dai 4 se co tong bang 14)
* => Suy ra lop n co tong bang lop n - 48 cong them 168 * 4 = 672
* Chu y, truong hop dac biet, lop 49 khong the quy ve lop 1 theo cong thuc
  tren
}

procedure ComputeSmallCases;
var
  n2: Integer;
begin
  n2 := n mod Circle + 2 * Circle;
  while n2 > 0 do
    begin
      layer[n2] := FillBorder(n2);
      Dec(n2, 2);
    end;
end;

procedure Solve;
var
  p, q, k, n2: Int64;
  i: Integer;
  temp: TNumber;
begin
  ComputeSmallCases;
  res := 0;
  if n <= Circle + 1 then
    begin
      n2 := n;
      while n2 > 0 do
        begin
          res := res + layer[n2];
          Dec(n2, 2);
        end;
      Exit;
    end;
  p := n;
  for i := 1 to Circle div 2 do
    begin
      if p <= Circle + 1 then
        begin
          temp := layer[p];
          if p = Circle + 1 then temp := temp + Layer[1];
          res := res + temp;
        end
      else
        begin
          q := p mod Circle;
          if q <= 1 then q := q + Circle;
          k := (p - q) div Circle;
          temp := (layer[q] + TNumber(k) * 336) * TNumber(k + 1);
          res := res + temp;
          if q = 49 then //Cong them lop 1
            res := res + layer[1];
        end;
      Dec(p, 2);
    end;
end;

procedure PrintResult;
begin
  WriteLn(fo, AnsiString(res));
end;

begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    while not SeekEof(fi) do
      begin
        Read(fi, n);
        Init;
        Solve;
        PrintResult;
      end;
  finally
    CloseFile(fi);
    CloseFile(fo);
  end;
end.

Ôi trời! Đoạn code dài khủng khiếp
 
G

gangoinocnha

Bạn giúp mình nghiên cứu đoạn code ấy nhé.Mình đọc hoài mà không hiểu cái gì hết trơn
 
M

mikelhpdatke

Ở bài 1, ta lưu ý rằng, trong ma trận này, có nhiều "đường viền", giả sử ta đánh dấu các đường viền này như sau:
33333
32223
32123
32223
33333

Xét đường viền ngoài cùng (đánh số 4):
???????
? ?
? ?
? ?
? ?
? ?
???????
Đường viền này là một hình vuông 4 cạnh, mỗi cạnh có 7 ô. Để ý rằng, trong một cạnh, CỨ 4 Ô LIÊN TIẾP thì có tổng là 14, thế nên, ta sẽ dùng dữ kiện này để tối ưu hoá:

Đặt F[a,s] là tổng số giá trị của mỗi ô trên đường viền có cạnh là a, điểm bắt đầu là s.
= > F[a,s] = 14*a div 4*4 + F[a mod 4, s].


 
L

lamdetien36

mikelhpdatke said:
Ở bài 1, ta lưu ý rằng, trong ma trận này, có nhiều "đường viền", giả sử ta đánh dấu các đường viền này như sau:
33333
32223
32123
32223
33333

Xét đường viền ngoài cùng (đánh số 4):
???????
? ?
? ?
? ?
? ?
? ?
???????
Đường viền này là một hình vuông 4 cạnh, mỗi cạnh có 7 ô. Để ý rằng, trong một cạnh, CỨ 4 Ô LIÊN TIẾP thì có tổng là 14, thế nên, ta sẽ dùng dữ kiện này để tối ưu hoá:

Đặt F[a,s] là tổng số giá trị của mỗi ô trên đường viền có cạnh là a, điểm bắt đầu là s.
= > F[a,s] = 14*a div 4*4 + F[a mod 4, s].
Bấm để xem đầy đủ nội dung ...
Anh giải thích công thức đó cho em với. Em không hiểu gì hết @-)
 
You must log in or register to reply here.
Top Bottom