Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Vietnamese Olympiad in Informatics

Điểm tin VOJ

Số thành viên:6831
Số bài tập:1035
Số bài nộp:913743
Bài nộp hôm nay:0
Thành viên xuất sắc trong tháng (03-2014):gawry (0.0)

Top 10 thành viên xuất sắc

HạngThành viênĐiểm

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible +265
2conankudo+161
3khuc_tuan+140
4tuananhnb93+135
5flash_mt+127
6khanhptnk+127
7hphong+108
8hoangle+86
9c_hunter+84
10paulmcvn+74

Topcoder Vietnam

HạngThành viênĐiểm
1flashmt2428.0
2ll9311102403.0
3IOU.nor2368.0
4infrmtcs2288.0
5Zero_sharp2194.0
6con_nha_ngheo2066.0
7skyvn971970.0
8darknsux1931.0
9hovinhthinh1897.0
10happyboy99x1834.0
Diễn đàn
Forum
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 (1 viewing) ,(1) Guest
Go to bottom Post Reply Favoured: 0
TOPIC: Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006
#22004
anhtuan_chuyentb (User)
Đang tập code
Posts: 4
graphgraph
User Offline Click here to see the profile of this user
Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 4 Years, 3 Months ago   (+0)
Hình mô tả bên là một tam giác số có số hàng là 5. đi từ đỉnh (số 7) của tam giác bàng một đường gấp khúc, mỗi bước chỉ được đi từ số ở hàng trên xuống một trong 2 ô kề bên trái hoăck bên phải của hàng dưới, và tính tích các số trên đường đi ta được một tích.
VD đường đi 7 8 1 4 5 có tích là s=1344, đường đi 7 3 1 7 5 cod tích là s=735
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Yêu cầu: cho tam giác số, tìm tích đường đi có tích lớn nhát.

Dữ liệu:Vào từ file tgs.inp:
-dòng đầu ghi số nguyên n(0<n<101)
-n dòng tiếp theo, từ dòng thứ 2 dến dòng n+1: dòng thứ i có i-1 số cách nhau bởi một dấu cách( các số có trị tuyệt đối không quá 100);

Kết quả: file tgs.out ghi 1 số nguyên là tích mã tìm được.

tgs.inp
5
7
3 8
8 1 0
2 7 4 4
4 5 -2 6 5

tgs.out
5880
 
Logged Logged  
  The administrator has disabled public write access.
#22007
wikiblack713 (User)
wikiblack713
Đã biết code đệ quy
Posts: 17
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 4 Years, 3 Months ago   (+0)
Bạn thử QHD từ dưới lên trên thử. F[i,j] = maF[i+1,j], F[i+1,j+1)*d[i,j]. Hjhe
 
Logged Logged  
 
Nothing's Impossible
  The administrator has disabled public write access.
#22017
anhtuan_chuyentb (User)
Đang tập code
Posts: 4
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 4 Years, 3 Months ago   (+0)
??????????
 
Logged Logged  
  The administrator has disabled public write access.
#60454
rocket2012 (User)
rocket2012+1
Đã biết code đệ quy
Posts: 11
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 2 Years, 2 Months ago   (+0)
Ai làm giúp bài tam giác số này đi.
 
Logged Logged  
  The administrator has disabled public write access.
#60455
vodanh9x (User)
vodanh9x+20
Nhắm mắt code không bug
Posts: 251
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 2 Years, 2 Months ago   (+0)
rocket2012 viết:
QUOTE:
Ai làm giúp bài tam giác số này đi.

thử QHD thế này xem sao:
xét đến ô j hàng thứ i có 2 trường hợp xảy ra d[i,j]<0 và d[i,j]>=0;
* d[i,j]<0
Code:
 
        fmin[i,j]=max(fmax[i-1,j],fmax[i-1,j-1])*d[i,j];
        fmax[i,j]=min(fmin[i-1,j],fmin[i-1,j-1])*d[i,j];
* d[i,j]>=0
Code:
 
        fmin[i,j]=min(fmin[i-1,j],fmin[i-1,j-1])*d[i,j];
        fmax[i,j]=max(fmax[i-1,j],fmax[i-1,j-1])*d[i,j];
(i=1..n,j=1..i); trong đó fmin[i,j] và fmax[i,j] tương ứng là tích min và max khi đi từ đỉnh đến ô (i,j)
 
Logged Logged  
 
anh chỉ yêu mình em....NTNA......
  The administrator has disabled public write access.
#60469
rocket2012 (User)
rocket2012+1
Đã biết code đệ quy
Posts: 11
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 2 Years, 2 Months ago   (+0)
Mọi người xem giúp em bài sai chỗ nào với, QHĐ như anh vodanh9x đúng rồi.
Em bị lỗi 201
Code:
const fi='224.INP';
      fo='224.OUT';
var f:text;
    a:array[0..101,0..101] of integer;
    i,j:integer;
    n:integer;
    ma,mi:ansistring;
    max,min:array [0..101,0..101] of ansistring;
function ss(a,b:ansistring):ansistring;
var tmp:ansistring;
begin
  if (a[1]='-') and (b[1]<>'-') then tmp:=b;
  if (b[1]='-') and (a[1]<>'-') then tmp:=a;
  if (a[1]<>'-') and (b[1]<>'-') then begin
    while length(a) < length(b) do a:='0'+a;
    while length(b) < length(a) do b:='0'+b;
    if a>b then tmp:=a else tmp:=b;
  end;
  if (a[1]='-') and (b[1]='-') then begin
    delete(a,1,1);
    delete(b,1,1);
    while length(a) < length(b) do a:='0'+a;
    while length(b) < length(a) do b:='0'+b;
    if a<b then tmp:=a else tmp:=b;
    a:='-'+a;
    b:='-'+b;
  end;
  ss:=tmp;
end;
function ss2(a,b:ansistring):ansistring;
var tmp:ansistring;
begin
  if (a[1]='-') and (b[1]<>'-') then tmp:=a;
  if (b[1]='-') and (a[1]<>'-') then tmp:=b;
  if (a[1]<>'-') and (b[1]<>'-') then begin
    while length(a) < length(b) do a:='0'+a;
    while length(b) < length(a) do b:='0'+b;
    if a<b then tmp:=a else tmp:=b;
  end;
  if (a[1]='-') and (b[1]='-') then begin
    delete(a,1,1);
    delete(b,1,1);
    while length(a) < length(b) do a:='0'+a;
    while length(b) < length(a) do b:='0'+b;
    if a>b then tmp:=a else tmp:=b;
    a:='-'+a;
    b:='-'+b;
  end;
  ss2:=tmp;
end;
function mul(a:ansistring;b:integer):ansistring;
var nhan,nho :longint;
    tich,tmp:ansistring;
    d:char;
    c:longint;
begin
  tich:='';nho:=0;
  if a[1]='-' then begin
    d:='-';
    delete(a,1,1);
  end;
  for c:=length(a) downto 1 do begin
    nhan:=abs(b)*(ord(a[c])-48)+nho;
    nho:=nhan div 10;
    tich:=chr(nhan mod 10 + 48)+tich;
   end;
  if nho>0 then str(nho,tmp) else tmp:='';
  if (d='-') and (b>0) then tmp:='-'+tmp;
  if (d<>'-') and (b<0) then tmp:='-'+tmp;
  a:=d+a;
  mul:=tmp + tich;
end;
begin
  assign(f,fi);reset(f);
  read(f,N);
  readln(f);
  for i:=1 to n do
    for j:=1 to i do read(f,a[i,j]);
  close(f);
  assign(f,fo);rewrite(f);
  str(a[1,1],max[1,1]);
  str(a[1,1],min[1,1]);
  max[1,0]:='1';
  min[1,0]:='1';
  for i:=2 to n do
    for j:=1 to i do begin
      if a[i,j]<0 then begin
        min[i,j]:=mul(ss(max[i-1,j],max[i-1,j-1]),a[i,j]);
        max[i,j]:=mul(ss2(min[i-1,j],min[i-1,j-1]),a[i,j]);
      end;
      if a[i,j]>0 then begin
        min[i,j]:=mul(ss2(min[i-1,j],min[i-1,j-1]),a[i,j]);
        max[i,j]:=mul(ss(max[i-1,j],max[i-1,j-1]),a[i,j]);
      end;
  end;
  ma:=max[n,1];
  mi:=min[n,1];
  for j:=1 to n do ma:=ss(max[n,j],ma);
  for j:=1 to n do mi:=ss(min[n,j],mi);
  write(f,ss(ma,mi));
  close(f);
end.
 
Logged Logged  
  The administrator has disabled public write access.
#60472
rocket2012 (User)
rocket2012+1
Đã biết code đệ quy
Posts: 11
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 2 Years, 2 Months ago   (+0)
Em đổi ansistring thành string thì chạy được (mặc dù phần xử lí số âm bị sai), tại sao lại thế, ansistring khác với string chỗ nào ?
 
Logged Logged  
  The administrator has disabled public write access.
#63554
du896 (User)
Đang tập code
Posts: 2
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 1 Year, 9 Months ago   (+0)
mình có cách khác không bít chính xác đươc bao nhiêu
 
Logged Logged  
  The administrator has disabled public write access.
#63555
du896 (User)
Đang tập code
Posts: 2
graphgraph
User Offline Click here to see the profile of this user
Trả lời: Tam giác số-1 bài tập trong đề thi tin hoc tỉnh Hà Tây năm 2006 1 Year, 9 Months ago   (+0)
day la bài cua mình
 
Logged Logged  
  The administrator has disabled public write access.
Go to top Post Reply
Powered by FireBoardget the latest posts directly to your desktop