Bài 12. Biến đổi dãy số. Cho dãy số nguyên dương a = (a1, a2, an)



tải về 80.65 Kb.
Chuyển đổi dữ liệu23.07.2016
Kích80.65 Kb.
#2546
Bài 12. Biến đổi dãy số.
Cho dãy số nguyên dương a = (a1, a2, ...,an) (1 <= n <=100; 1 <= ai
<= 100, 1 <= i <= n.
Xét hai loại phép biến đổi :
+ Phép biến đổi +i : tăng ai lên 1 đơn vị;
+ Phép biến đổi -i : giảm ai đi 1 đơn vị.
Yêu cầu: Hãy tìm một cách sử dụng ít phép biến đổi nhất để biến dãy a
trở thành dãy thoả mãn : 1 <= a1 < a2 < ... < an <= 100.
Dữ liệu vào :
+ Số n nhập từ bàn phím.
+ Các số a1, a2, ..., an được nhập vào bằng hàm RANDOM.
Kết quả ghi ra màn hình: + Dòng đầu ghi số m là số phép biến đổi tìm được. + m dòng tiếp theo, mỗi dòng ghi một phép biến đổi.

Các anh giúp em bài này với!

Bài 1: Một xâu S được gọi là một " (K,L) - Lặp " nếu nó được tạo thành bằng cách ghép liên tiếp K lần một xâu hạt giống T nào đó độ dài L(L>=1).
Cho xâu U (có độ dài 50000 kí tự) chứa các kí tự a và b.Tìm "(K,L)-lặp"và in ra ssố lần lặp của nó.
Input :số nguyên N(1<=N<=50000);
n dòng tiếp theo la cac ki tự 'a' và 'b'
output:
1,Dòng đầu là số k(k lớn nhất)
2,Dòng là độ dài L
3,Vị trí P xâu bắt đầu
repeat.inp
17
b
a
b
b
a
b
a
a
b
a
a
b
a
a
b
a
b
repeat.out
4
3
5

có nghĩa là xâu U=babbabaabaabaabab chứa xâu con S có 3 kí tự (bab) lặp 4 lần


từ vi trí 5.

Bài toán tìm dãy con tăng chặt dài nhất

INCSEQ
Cho dãy số nguyên : P = p[1], p[2], …,p[n]. (n <= 10000, - 30000 <= p[i] <= 30000).


Một dãy con của P là một cách chọn ra trong P một số phần tử giữ nguyên thứ tự.
Yêu cầu : Tìm dãy con đơn điệu tăng của P có độ dài lớn nhất.
Dữ liệu vào : “INCSEQ.INP”
o Dòng 1 : Chứa số N.
o N dòng sau, mỗi dòng ghi một số nguyên p[i].
Dữ liệu ra : “INCSEQ.OUT”
o Dòng 1 : Ghi số L là độ dài dãy con tìm được.
o L dòng sau, mỗi dòng ghi một chỉ số của các phần tử trong dãy con tìm được theo chiều tăng dần của giá trị.

Ví dụ :
INCSEQ.INP


12
9
22
10
17
3
17
14
7
20
21
7
24
INCSEQ.OUT
6
1
3
4
9
10
12

Cách giải : Ta sẽ giải bài toán với phương pháp quy hoạch động.


Gọi L[i] là độ dài của dãy đơn điệu tăng dài nhất bắt đầu tại p[i]. Khi đó kết quả sẽ là Max{L[i], 1 <= i <= n}.
Với mỗi phần tử p[i] (1 <= i <= n) dễ dàng nhận thấy dãy đơn điệu tăng dài nhất bắt đầu tại p[i] sẽ có 2 trường hợp :
1. Dãy có 1 phần tử p[i].
2. Dãy có phần tử thứ 2 là p[j] thỏa mãn : i + 1 <= j <= n, p[j] > p[i].
Như vậy để dãy đơn điệu tăng bắt đầu tại p[i] là dài nhất thì ta phải tìm phần tử jmax thỏa mãn :
i + 1 <= jmax <= n, p[jmax] > p[i] và L[jmax] là lớn nhất (để đảm bảo tính dài nhất). Trường hợp không tồn tại j thỏa mãn => L[i] = 1 (trường hợp 1).
Ta có công thức truy hồi : L[i] = Max{L[j], i + 1 <= j <= n, p[j] > p[i]} + 1. (1 <= i <= n)
Để truy vết (in ra chỉ số các phần tử trong dãy) ta có thể dùng thêm mảng D = d[1], d[2], …, d[n] với ý nghĩa : d[i] là vị trí phần tử tiếp L[i] = L[d[i]] + 1theo trong dãy con đơn điệu tăng dài nhất bắt đầu tại p[i] và p[d[i]] > p[i] hay d[i] = jmax.
Ta có chương trình minh họa sau :

program tim_day_con_tang_chat_dai_nhat_cua_1_day;


const tfi = 'Incseq.inp';
tfo = 'Incseq.out';
maxn = 10001;
type array1 = array[0..maxn] of integer;
var n,vt : integer;
l,p,d : array1;
(*-------------------------------------------------------------*)
procedure inp; (* Đọc dữ liệu *)
var i : integer;
begin
assign(input,tfi); reset(input);
readln(n);
for i := 1 to n do readln(p[i]);
close(input);
end;
(*-------------------------------------------------------------*)
procedure main; (* Quy hoạch động tìm mảng L và D *)
var i,j,k : integer;
begin
vt := n; {vt là vị trí có L[vt] = Max{L[i], 1 <= i <= n}}
for i := n downto 1 do
begin
{Tìm k = jmax}
k := 0;
for j := i + 1 to n do
if (p[j] > p[i]) and (l[j] > l[k]) then k:= j;
l[i] := l[k] + 1; {Lưu độ dài dãy đơn điệu tăng bắt đầu tại p[i]}
d[i] := k; {Lưu vết vị trí phần tử tiếp theo trong dãy con tăng dài nhất bắt đầu tại p[i]}
if (l[i] > l[vt]) then vt := i; {Cập nhật lại vị trí bắt đầu vt khi l[i] > l[vt]}
end;
end;
(*-------------------------------------------------------------*)
procedure out; (* Viết kết quả *)
begin
assign(output,tfo); rewrite(output);
writeln(l[vt]); { Viết độ dài của xâu con đơn điệu tăng dài nhất}
{ Truy vết – In chỉ số các phần tử được chọn }
while (vt <> 0) do
begin
writeln(vt);
vt := d[vt];
end;
close(output);
end;
(*-------------------------------------------------------------*)
begin
inp;
main;
out;
end.

Bài 4: cho một dãy số gồn n số(n<~30000), tìm dãy con liên tiếp có tổng lón nhất .dùng quy hoạch động.

F(i) tổng dãy con liên tiếp lớn nhất kết thúc ở i
F(i) = max ( F(i - 1) + a[i], a[i])
ĐOẠN DƯƠNG
nCho dãy số nguyên a = (a1, a2, ..., an), 1 Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy a: aL, aL+1, ..., aH có tổng dương

Dữ liệu: Vào từ file văn bản SP.INP


• Dòng 1: Chứa số n
• Dòng 2: Chứa n số a1, a2, ..., an theo đúng thứ tự cách nhau ít nhất một dấu cách

Kết quả: Ghi ra file văn bản SP.OUT


Chỉ gồm một dòng ghi hai số L và H cách nhau ít nhất một dấu cách.

Ràng buộc: Có ít nhất một phần tử dương trong a

Ví dụ:
SEGMENT.INP
10
-5 -2 -3 4 -6 7 -8 9 -1 -20
SEGMENT.OUT
3 9
Bài 5: Dãy số nguyên a1, a2, …,a n được gọi là dãy móc xích, nếu tồn tại idãy số đang xét được gọi là dãy móc xích bậc m nếu m phần tử liên tiếp của dãy đều là dãy móc xích
yêu cầu:
cho 3 số m, n, r. hãy xác định số lượng dãy số nguyên tố dài n là dãy móc xích bậc m và mỗi phần tử của dãy có giá trị dương, không vượt quá r
4<= m <=8
m<= n <=50
2<= r <=50
kểt quả tìm được đưa ra theo mô đun 10^9+7.
Ví dụ : m= 4; n= 5; r = 3 ta có 6 dãy:
(1; 2; 1; 2; 1)
(1; 3; 1; 3; 1)
(2; 1; 2; 1; 2)
(2; 3; 2; 3; 2)
(3; 1; 3; 1; 3)
(3; 2; 3; 2; 3)
dữ liệu: vào từ file văn bản LINKED.INP, gồm 1 dòng chứa 3 số nguyên m, n, r.
kết quả : đưa ra file văn bản LINKED.OUT dưới dạng số nguyên.
Ví dụ
LINKED.INP
4 5 3
LINKED.OUT
6

Bài 6: Số đối nguyên tố là một số mà số ước của nó luôn lớn hơn số ước của các số nguyên dương nhỏ hơn nó.

Đề: Nhập vào 1 số n và tìm số đối nguyên tố lớn nhất nhỏ hơn n. Ai nghĩ ra cách giải bằng quy hoạch động không?

Vừa nhập môn quy hoạch động, thực ra lâu nay cứ khinh thường quy hoạch động vì nghĩ bài nào mình cũng giải được bằng vét cạn, nhưng hôm bữa mới thi được có 1/20 điểm vì dữ liệu nhập lớn quá .

Mấy bữa nay tìm hiểu quy hoạch động nhưng không hiểu làm sao mà hình thành được ý tưởng để viết 1 chương trình quy hoạch động.

Chẳng hạn bài toán tìm xâu con chung dài nhất.


Xâu con chung được định nghĩa như sau: Nếu xóa đi một só kí tự của hai xâu thì 2 xâu con còn lại của chúng bằng nhau

Ví dụ: a=(CEACEEC) b(AECECA) Kết quả là c=(ECEC) hoặc (AEEC)

Và thuật toán đưa ra là:



For i:=1 to length(a) do
For j:=1 to length( do
if a[i]=b[j] then
L[i,j]:=1+L[i-1,j-1];
else
L[i,j]:=max(L[i-1,j],L[i,j-1];

Đó là mình chép từ sách của Trần Lê Hồng Dũ và Phạm Ngọc Chí Nhân nhưng mình vẫn không hiểu, mặc dù mình cho chạy từng dòng thì tất cả rất khớp.

Bạn nào có thể giải thích cho mình cái chỗ else L[i,j]:=max(L[i-1,j],L[i,j-1]; hay không, nó là cái làm mình thắc mắc nhất đó.

Giúp đỡ mình với nghe, đang học lớp 11 chuyên tin sắp học tới quy hoạch động rùi mà mình dỡ cái này quá hu hu

L[i,j] là độ dài của xâu con chung dài nhất khi xét tới vị trí thứ i của xâu a và thứ j của xâu b .
nếu a[i]=b[j] thì dễ thấy l[i,j]:=l[i-1,j-1]+1
Nếu a[i]<>b[i] thì
Độ dài của xâu con chung dài nhất khi xét tới vị trí thứ i của xâu a và thứ j của xâu b là độ dài xâu con chung dài nhất khi xét tới vị trí i-1 của xâu a và j của xâu b hoặc độ dài xâu con chung dài nhất khi xét tới vị trí i của xâu a và j-1 của xâu b
Do yêu cầu xâu con chung dài nhất nên chọn max .
À , mà bạn học ở đâu vậy ??? Mình cũng đanh học lớp 11.

Một du khách thuê một xe ôtô để du lịch từ thành phố A tới thành phố B co khoảng cách


là S.(0phục vụ cho cuộc hành trình.Do giá xăng biến động nên giá xăng ở mỗi cây xăng là khác nhau và người khách biết thông tin về các cây xăng trên hành trình từ A đến B.
Gọi Di là khoảng cách từ thành phố A đến cây xăng thứ i và Ci là giá 1 lít xăng tại cây xăng thứ i.
Để đi được 1 Km, xe ôtô phải tốn 1 lít xăng.Bình xằng của xe có sức chứa tối đa là M lít
(M chẵn và 0INPUT.
-Dòng đầu là 3 số S,M,K.


-Các dòng tiếp theo , mỗi dòng thứ i gồm 2 số Di , Ci.
Mỗi số cách nhau ít nhất một khoảng trắng.

OUTPUT
Nếu không thể đi từ A đến B thì ghi "Không thể đi được"


Ngược lại gồm 2 dòng:
-Dòng đầu gồm 1 số là tổng chi phí ít nhất dùng mua xăng.
-Dòng tiếp theo gồm K số, mỗi số thứ i là số xăng phải đổ ở cây xăng thứ i.

VD:
Doxang.inp


50 20 5
7 300
12 350
20 250
35 300
42 250

Doxang.out


13100
10
0
20
2
18

Một du khách thuê một xe ôtô để du lịch từ thành phố A tới thành phố B co khoảng cách


là S.(0phục vụ cho cuộc hành trình.Do giá xăng biến động nên giá xăng ở mỗi cây xăng là khác nhau và người khách biết thông tin về các cây xăng trên hành trình từ A đến B.
Gọi Di là khoảng cách từ thành phố A đến cây xăng thứ i và Ci là giá 1 lít xăng tại cây xăng thứ i.
Để đi được 1 Km, xe ôtô phải tốn 1 lít xăng.Bình xằng của xe có sức chứa tối đa là M lít
(M chẵn và 0INPUT.
-Dòng đầu là 3 số S,M,K.


-Các dòng tiếp theo , mỗi dòng thứ i gồm 2 số Di , Ci.
Mỗi số cách nhau ít nhất một khoảng trắng.

OUTPUT
Nếu không thể đi từ A đến B thì ghi "Không thể đi được"


Ngược lại gồm 2 dòng:
-Dòng đầu gồm 1 số là tổng chi phí ít nhất dùng mua xăng.
-Dòng tiếp theo gồm K số, mỗi số thứ i là số xăng phải đổ ở cây xăng thứ i.

VD:
Doxang.inp


50 20 5
7 300
12 350
20 250
35 300
42 250

Doxang.out


13100
10
0
20
2
18
Bài này có thể dùng QHĐ được không vậy các anh?
Người ta định nghĩa đệ qui dãy ngoặc và cấp của dãy như sau:

+) Xâu rỗng được gọi là dãy ngoặc cấp 0.

+) Nếu S là xâu ngoặc cấp k thì (S) là xâu ngoặc cấp k+1.

+) Nếu A, B là các dãy ngoặc thì S = AB là một dãy ngoặc với cấp bằng số lớn hơn trong cấp của A và B.

Định nghĩa này chỉ áp dụng cho những xâu sinh ra theo qui tắc đệ qui trên.

Cho 2 số nguyên dương N và k, gọi S là tập các dãy ngoặc cấp k độ dài N.

1. Cho biết S có bao nhiêu phần tử.

2. Cho một dãy ngoặc thuộc, hãy cho biết thứ tự từ điển của dãy này trong tập S.


Input

- Dòng đầu ghi 2 số N, k (N chẵn, N <= 38, k <= n/2 ).

- Dòng hai ghi 1 xâu ngoặc cấp k độ dài N.
Output

Gồm hai dòng, mỗi dòng trả lời 1 yêu cầu theo thứ tự trên.


Example
Input:
6 2
(())()

Output:
3


2
938. Thang máy vũ trụ
Mã bài: ELEVATOR

Những con bò muốn đi vào vũ trụ! Chúng muốn đến được quỹ đạo bằng cách xây một kiểu thang máy: một cái tháp khổng lồ làm bằng các khối chồng lên nhau. Chúng có K (1 ≤ K ≤ 400) loại khối có thể xây tháp. Mỗi khối loại i có chiều cao h_i (1 ≤ h_i ≤ 100) và có số lượng c_i (1 ≤ c_i ≤ 10). Do khả năng bị phá hủy bởi các tia vũ trụ, không có phần nào của khối loại i có thể vượt qua độ cao a_i (1 ≤ a_i ≤ 40000).

Giúp những con bò xây thang máy cao nhất có thể bằng cách chồng các khối lên nhau theo luật trên.

Input
* Dòng 1: Một số nguyên: K

* Dòng 2..K+1: Mỗi dòng chứa 3 số nguyên được phân cách bởi khoảng trắng: h_i, a_i, và c_i. Dòng i+1 miêu tả loaị khối i.

Output
* Dòng 1: Một số nguyên H, chỉ độ cao tối thiểu của tháp có thể xây được.

Example
Input:
3
7 40 3
5 23 8
2 52 6

Output:
48

GIẢI THÍCH:
Từ dưới lên: 3 khối loại 2, 3 khối loại 1, 6 khối loại 3. Chồng 4 khối loại 2 & 3 loại 1 không hợp lệ vì đỉnh của khối loại 1 vượt quá độ cao 40.
đầu tiên mình sắp xếp các khối tăng dần theo A[i]
sau đó quy hoạch động : F[i, j] là độ cao lớn nhất khi xét tới khối i và dùng j khối đó ( j <= c[i] ).

ta có : F[i, j] := max {F[i-1, k] + j*h[i]} với F[i-1, k] + j*h[i] <= a[i] khi j > 0

Nhưng khi submit toàn bị WA. không biết cách làm của mình sai ở đâu nhỉ ?
đầu tiên mình sắp xếp các khối tăng dần theo A[i]
sau đó quy hoạch động : F[i, j] là độ cao lớn nhất khi xét tới khối i và dùng j khối đó ( j <= c[i] ).

ta có : F[i, j] := max {F[i-1, k] + j*h[i]} với F[i-1, k] + j*h[i] <= a[i] khi j > 0

Nhưng khi submit toàn bị WA. không biết cách làm của mình sai ở đâu nhỉ ?
const fi='';
     fo='';
var   f1,z:text;
     n:word;
     h,so,a:array [0..400] of word;
     f:array [0..400,0..10] of longint;

{+++++++++++++++++++++++++++++++++++++++++++++}

procedure doc;
var i:word;
begin
    assign(f1,fi);
    reset(f1);
    readln(f1,n);
    for i:=1 to n do
        readln(f1,h[i],a[i],so[i]);
    close(f1);
end;

{++++++++++++++++++++++++++++++++++++++++++++++}

procedure doi(var m,n:word);
var tam:word;
begin
    tam:=m;
    m:=n;
    n:=tam;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++}

procedure qsort(dau,cuoi:word);
var d,c,x:word;
begin
    d:=dau;
    c:=cuoi;
    x:=a[(d+c) div 2];
    repeat
          while a[d]          while a[c]>x do c:=c-1;
          if d<=c then
             begin
                  doi(a[d],a[c]);
                  doi(h[d],h[c]);
                  doi(so[d],so[c]);
                  d:=d+1;
                  c:=c-1;
             end;
    until d>c;
    if d    if c>dau then qsort(dau,c);
end;

{++++++++++++++++++++++++++++++++++++++++++++++++++++++}

procedure xay;
var i,j,k,max:word;
begin
    qsort(1,n);
    so[0]:=10;
    for i:=0 to 10 do
        f[0,i]:=0;
    for i:=1 to n do
        begin
             for j:=1 to so[i] do
                 begin
                      max:=0;
                      for k:=1 to so[i-1] do
                          begin
                               if (f[i-1,k]+j*h[i]<=a[i]) and (f[i-1,k]+j*h[i]>max) then
                                  max:=f[i-1,k]+j*h[i];
                          end;
                      f[i,j]:=max;
                 end;
        end;
end;

{++++++++++++++++++++++++++++++++++++++++++++++++++++++}

procedure ghi;
var i,max:word;
begin
    assign(z,fo);
    rewrite(z);
    max:=0;
    for i:=1 to so[n] do
        if f[n,i]>max then
           max:=f[n,i];
    write(z,max);
    close(z);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++}

begin
    doc;
    xay;
    ghi;
    readln;
end.
Cho một bảng A gồm M hàng, N cột, trong đó A[i, j] nhận giá trị là 1 số thực.
nhiệm vụ của bạn là xây dựng một bảng B, trong đó B[i, j] có giá trị bằng phần nguyên của A[i, j] hoặc phần nguyên của A[i, j] + 1, sao cho : tổng các giá trị của 1 hàng, cột bất kì trong bảng B luôn chênh lệch với giá trị của hàng (cột)  đó trong bảng A không quá 1.

giới hạn M, N <= 1000.

Input
  M, N
  M dòng tiếp theo, mỗi dòng N số thực
Output
  xuất ra bảng B

Trong một nước người ta phát hành N loại tem khác nhau về giá trị( vd:loại tem 1 đ, 3dd,...). Người ta không cho phép dán trên mỗi vật phẩm quá M con tem(có thể dán tem cùng loại). Giá cước mỗi vật phẩm là một số nguyên đồng. Nhập M,N từ bàn phím. XÁc định tất cả các bộ giá trị của các loại tem cần phát hành sao cho dãy giá cước của các vật phẩm được gửi là một dãy các số nguyên liên tiếp dài nhất 1,2,3,....,s


VD
Số loại tem: N=4;
Số tem nhiều nhất trên 1 vật phẩm: M=5 thì dãy giác cước gửi được dài nhất là 1,2,3,....,s=71 với bộ tem {1,4,12,21} hoặc bộ {1,5,12,28}
Khăn trải bàn
Quầy ăn của 1 k/s cần sử dụng d[1],...,d[N] khăn trải bàn cho n ngày liên tiếp đánh số từ 1->N. K/s có 3 phương án có thể chọn:
- Mua mới với giá A đồng/khăn
- Giặt trả nhanh, trả ngày i + 1 giá B đồng/khăn
- Giặt trả chậm, trả ngày i + 2 giá C đồng/khăn
Giả sử ban đầu k/s chưa có khăn, hãy lập kế hoạch sao cho tốn ít tiền nhất.
Dữ liệu vào:
- Dòng 1: N, A, B, C (N <= 100), (A < B- Dòng 2: gồm N số nguyên dương d[1]...d[N]
Dữ liệu ra:
- Dòng 1: Chi phi nhỏ nhất.
- Dòng i trong N dòng tiếp theo: 3 số M[i], Tranhanh[i], Tracham[i] với ý nghĩa là số khăn mua mới, số khăn giặt trả nhanh và số khăn giặt trả chậm trong ngày thứ i.
Ví dụ:
.Inp:
8 10 8 5
10 8 9 20 7 1 7 9
.Out
496
27 0 10
0 0 8
0 2 7
0 0 17
0 0 0
0 0 0
0 0 0
0 0 0
Thêm một bài QHĐ nữa nhé cho vui vẻ , bài này mình cũng chưa có cách nào hay cả :
Cho N cái hộp, mỗi cái hộp có một trọng lượng Wi và có khả năng chịu được trọng lượng Ci.
Yêu cầu : Hãy tìm cách xếp được nhiều hộp chồng lên nhau nhất (cái trên chồng lên cái dưới) sao cho ko có hộp nào bị vỡ do quá tải cả ( nghĩa là tổng trọng lượng những hộp ở trên một hộp trong chồng <= tải trọng của cái hộp đó) .
Dữ liệu vào :
Dòng đầu là N ( N<=50 làm càng lớn càng tốt)
Dòng 2 : W1... Wn (Wi<=100000)
Dòng 3 : C1... Cn (Ci<=1000000000).
Kết quả :
Số hộp nhiều nhất tìm được.

VD
Input


3
10 20 30
11 100 10
Output
3

Input
3


11 20 30
11 100 10
Output
2

em có bài này thấy cũng hay hay, nhưng em làm quá yếu kém nên mong các


đại ca chỉ giáo!
giám đốc điều hành của một công ty tin học cần xác định số lượng nhân công cần sử dụng trong mỗi tháng để thực hiện dự án.
ông biết được số luợng nhân công cần tối thiểu cho mỗi tháng.mỗi lần thuê hay sa thải 1 công nhân đều mất 1 lượng tiền nhất định.
khi 1 người thợ được thuê,anh ta cũng có lương ngay cả khi anh ta ko làm việc.
giám đốc biết được chi phí thuê,trả lương và sa thải 1 công nhân lần lượt là x,y,z.
yêu cầu:
hãy giúp giám đốc xác định số luợng nhân công cần thuê hay sa thải trong mỗi tháng để :CHI PHÍ THỰC HIỆN DỰ ÁN LÀ ÍT NHẤT
input:
dòng 1:số n(số tháng thực hiện dự án)
dòng 2: 3 số x,y,z
dòng 3:
ghi n số ,số thứ i là số lượng nhân công tối thiểu mà tháng thứ i cần có
output:
tổng chi phí min có được
ví dụ:
input:
3
4 5 6
10 9 11
output:
199
{giải thích:
tháng 1:thuê 10 người==>tổng chi phí thuê và lương là :10*4+0*5=90
tháng 2:ko thuê thêm và cũng ko sa thải ==>tổng tiền lương:10*5=50;
tháng 3:thuê thêm 1 công nhân:==>tổng chi phí thuê và lương:1*4+11*5=55;
tổng 3 tháng:199}


program thuenhancong;
var thue,luong,sathai,n:integer;
   employee:array[1..100] of integer;
   min:array[1..100] of integer;

procedure input;


var f:text; i:integer;
begin
assign(f,'nhancong.inp');
reset(f);
readln(f,n);
readln(f,thue,luong,sathai);
for i:=1 to n do
 begin
  read(f,employee[i]);
 end;
end;

procedure QHD;


var t1,t2, i,j:integer;
begin
  fillchar(min,sizeof(min),0);
  min[1]:=(thue+luong)*employee[1];
  for i:=2 to n do
   begin
    if  employee[i]>=employee[i-1] then
     min[i]:=min[i-1]+(employee[i]-employee[i-1])*thue+luong*employee[i]
    else
    begin
       t1:=sathai*(employee[i-1]-employee[i])+luong*employee[i];
       t2:= luong*employee[i-1];
       if (t2        begin
         min[i]:=min[i-1]+t2;
         employee[i]:=employee[i-1];
        end
       else min[i]:=min[i-1]+t1;
    end;
   end;

end;
begin


input;
QHD;
writeln(min[n]); readln;
end.

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

The more you give, the more you receive.














tin_truc22

Nov 9 2007, 08:57 PM

Post #4



Advanced Member


Group: Members


Posts: 46
Joined: 18-September 05
Member No.: 641




Lâu lắm rồi mới đụng lại pascal (hơn 1 năm) mình làm kiểu này hơi bị điên điên nhưng vẫn đúng được test đầu mời mọi người xem hộ.
var i,j,m,n,x,y,z,max:integer;
can:array [1..100] of integer;
a:array [1..100,1..100] of integer;
procedure nhapdulieu;
var f:text;
begin
assign(f,'in.txt');
reset(f);
readln(f,n);
read(f,y,x,z);
for i:=1 to n do
read(f,can[i]);
end;
Function min(i,j:integer):integer;
var jj,thue,somin:integer;
begin
somin:=10000;
if j>=can[i] then
for jj:= 1 to m do
begin
If j-jj <> 0 then
If j-jj > 0 then
thue:=(j-jj) * y + j * x + a[i-1,jj]
else
thue:=(jj-j) * z + j * x + a[i-1,jj]
else
thue:=j * x + a[i-1,j];
if thueend;
min := somin;
end;
begin
nhapdulieu;
m:=100;
for j:=1 to m do
if j>=can[1] then
a[1,j]:=j * x + j * y
else
a[1,j]:=10000;

for i:=2 to n do


for j:=1 to m do
a[i,j]:=min(i,j);
max := 10000;
for j:= 1 to m do
if (max > a[n,j]) then max := a[n,j];
writeln(max);
readln;
end.

Cho n số nguyên n<=100000 với công sai 1<=N<=100. Hãy tìm một dảy con của dãy số trên (dãy con được lấy từ các số trong dãy trên theo tứ tự) sao cho lập thành một cấp số cộng dài nhất.

time limit: 2s.(hoặc có thể hơn)
--------------
Mong mọi người giúp đỡ. Bài này mình đã từng suy nghi từ lâu rồi nhưng không sao làm được
Bài này mình muốn giải bằng phương pháp thử và quay lui. Mình đã cài đặt được rồi nhưng chương trình của mình chỉ chạy được với những dữ liệu nhỏ thôi. Còn một số Test quan trọng thì lại chạy quá lâu, đợi mãi. Nếu ai đã giải bài này rồi thì giúp mình với, cho mình xin luon cả code nhé.
Tên đề bài:

Đổ nước vào bình


Cho một thùng T dung tích có thể xem là vô hạn và n bình có dung tích V1, V2, ..., Vn lít (n ≤ 20 và Vi ≤ 100). Liệu có thể dùng n bình này để đổ vào thùng T đúng V lít (V ≤ 1000) lít nước hay không? Nếu được hãy tìm cách đổ sao cho tổng số bình đem sử dụng là ít nhất (mỗi bình có thể dùng nhiều lần).
Yêu cầu:
Dữ liệu vào cho bởi File DONUOC.INP
- Dòng thứ nhất ghi thể tích nước cần đổ V;
- Dòng thứ hai ghi số N;
- Các dòng tiếp theo ghi các giá trị của các Vi
Kết quả được ghi ra file DONUOC.OUT:
- Dòng thứ nhất ghi số lượng bình ít nhất cần dùng.
- Các dòng tiếp theo ghi các loại bình được dùng, số lượng của mỗi loại.
DONUOC.INP
1000
15
72 23 37 95 26 43 63 21 46 48 52 31 38 56 2
DONUOC.OUT
12
So loại bình 56 lít: 1
So loại bình 37 lit: 1
So loại bình 52 lit: 1
So loại bình 95 lit: 9
Vào năm 1945, Liên Xô đang đánh nhau với phát xít Đức hết sức ác liệt. Hàng triệu thanh niên Liên Xô phải lên đường nhập ngũ. Một cuộc duyệt binh diễn ra, các tân binh không biết đứng quay mặt về bên nào liền xếp tùy ý, vị tổng chỉ huy thấy thể liền ra lệnh: “Nếu hai tân binh liên tiếp và đối mặt với nhau thì ngay lập phải quay ngược lại(180 độ), động tác này diễn ra trong vòng 1s!”. Người tổng chỉ huy muốn biết sau bao lâu thì thì đội hình sẽ ngừng quay?
Input

Dòng đầu ghi số nguyên N là số tân binh.


Dòng thứ hai gồm đúng N kí tự ‘<’, ‘>’ thể hiện cách đứng của các tân binh. Nếu hai tân binh liên tiếp quay mặt vào nhau thì sẽ được biểu diễn bởi ‘><’. ( 1 ≤ n ≤ 1000000 ).
Output

Gồm một số duy nhất ghi thời gian ít nhất để đội hình ngừng quay.


Example

Input:
4


<><>

Output:
1


cho file tau.txt chứa cac ky tu 0 hay 1:
cac ký tự 1 là tàu, 0 là núoc (sát mí của 4 cạnh là bờ), y/c hãy đếm các con tàu trên phạm vi nhìn thấy duoc cho bởi bảng m*n.
VD:
10000111
10000111
00111000
00111000
10111001
00000000
00100010

vậy KQ có 7 con tàu.


Tim hinh vuong chua 1 day con dai nhat
cho hinh vuong gom N*N moi o chua 1 so nguyen duong khac nhau
bang cach lay tong cua cac so nam trong cac o vuong tao thanh
hinh chua nhat ta nhan duoc 1 day so.
Vidu: hv 2*2
1 3
6 2
-> ta duoc day 1,2,3,4,5,6,7,8, ,12
1+2=3,2+3=5,1+6=7,2+6=8,1+2+3+6=12

Cho hinh vuong 3*3 can chon 9 so >=k va doi mot khac nhau, moi


so dien vao 1 o hinh vuong de sao cho day thu duoc thanh lap theo
tren chua day con m,m+1,..m+t dai nhat co the duoc.
2 hinh vuong so duoc coi la nhu nhay neu bang phep quay ta co
the dua hinh vuong nay ve hinh vuong kia.neu co nhieu hinh vuong
so cung cho ta day con dai nhat thi cho biet tat ca cac hinh vuong do

input output


k t
m r
vidu
input output
1 7
1 1

1 3
6 2


ĐÀI PHUN NƯỚC

Để làm đẹp cảnh quan, Ban giám đốc một Công ty quyết định xây dựng ở sân tiền sảnh trụ sở công ty một đài phun nước. Đài phun nước phải có dạng một hình tròn với kích thước lớn nhất có thể được. Nhà thiết kế được biết là sân tiền sảnh của công ty có dạng một hình chữ nhật kích thước X <= Y mét. Tuy nhiên khi lựa chọn vị trí cho đài phun nước nhà thiết kế vấp phải một vấn đề phức tạp: Trong sân tiền sảnh có N cột hình trụ tròn xoay không được phép di chuyển. Vì vậy vấn đề đặt ra cho nhà thiết kế là: Cần đặt đài phun nước ở vị trí nào để nó có bán kính lớn nhất có thể được đồng thời không được có diện tích chung khác không với các cột. Bạn hãy lập trình giúp nhà thiết kế giải quyết vấn đề trên.

Dữ liệu: Vào từ file văn bản FONTAN.INP:
• Dòng đầu tiên chứa hai số thực X, Y, 1 <= X, Y <= 10^4. Giả thiết rằng sân tiền sảnh là hình chữ nhật trên mặt phẳng toạ độ có toạ độ các đỉnh là (0, 0), (X, 0), (X, Y), và (0, Y).
• Dòng thứ hai chứa số nguyên N (0 <= N <= 10) là số lượng cột trong sân tiền sảnh;
• Dòng thứ i trong số N dòng tiếp theo chứa ba số thực Xi, Yi và Ri cho biết toạ độ của tâm và bán kính của cột thứ i ( Ri <= Xi <= X - Ri, Ri <= Yi <= Y - Ri, 0.1 <= Ri <= min (X/2, Y/2), đối với mọi i <= j.
Các số trên một dòng trong file dữ liệu được ghi cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản FONTAN.OUT ba số thực XF, YF RF là toạ độ và bán kính của đài phun nước.

Chú ý: Đài phun nước phải được đặt trong sân, được phép tiếp xúc với tường của sân hoặc cột, nhưng không được có diện tích chung khác không với các cột. Nếu có nhiều vị trí cùng cho bán kính lớn nhất chỉ cần đưa ra một trong số chúng.

Ví dụ:


FONTAN.INP
10 20
0

FONTAN.OUT


5.000 5.000 5.000

FONTAN.INP


20 20
4
2 2 2
18 2 2
2 18 2
18 18 2

FONTAN.OUT


10.000 10.000 9.314

FONTAN.INP


20 20
4
2 2 2
18 2 2
3 17 2
16 16 4

FONTAN.OUT


9.510 7.054 7.053
Trong siêu thị người ta thường đặt camera trong các gian hàng để theo dõi khách và nhân viên.
Gian hàng là đa giác mà hai cạnh có chung đỉnh luôn vuông góc với nhau và không tự cắt.
Bài toán: Cho 1 gian hàng, hãy xác định xem có hay không một điểm nằm trong nó mà đặt camera ở đó thì quan sát đc mọi điểm trong gian.

SP.Inp:
- Dòng đầu là số N (<=100) là số đỉnh.


- N dòng tiếp theo, mỗi dòng ghi 2 số x, y là toạ độ của đỉnh.
Sp.Out:
- 1/0 <=> có/không

VD:
SP.Inp


4
0 0
0 1
1 1
1 0
SP.Out
1

Mưa thiên thạch

Phú ông nhận được thông tin về một trận mưa thiên thạch sắp ập xuống trái đất. Không những thế, Phú ông còn biết tọa độ của vị trí điểm rơi của mỗi một thiên thạch. Phú ông nhờ Cuội xác định xem có bao nhiêu thiên thạch có thể rơi xuống cánh đồng của ông ta. Cánh đồng của Phú ông có dạng một hình đa giác lồi được xác định bởi danh sách các đỉnh được liệt kê theo thứ tự ngược chiều kim đồng hồ.
Yêu cầu: Xác định xem trong tập cho trước các điểm rơi của thiên thạch, có bao nhiêu điểm nằm trong cánh đồng của Phú ông. Các điểm nằm trên biên của cánh đồng không được tính là điểm nằm trong cánh đồng.
Input

- Dòng đầu tiên là số nguyên n (3 <= n <= 5000) là số đỉnh của đa giác lồi mô tả cánh đồng của Phú ông.


- Mỗi dòng trong n dòng tiếp theo chứa cặp tọa độ của một đỉnh của đa giác lồi.
- Dòng tiếp theo là số nguyên m (2 <= m <= 5000) - số thiên thạch rơi xuống.
- Mỗi dòng trong số m dòng cuối cùng chứa 2 số là tọa độ điểm rơi của một thiên thạch.
Các tọa độ là các số nguyên có trị tuyệt đối không quá 10^6.
Output

Ghi ra m dòng, mỗi dòng tương ứng với 1 điểm rơi của thiên thạch. Ghi "YES" nếu điểm rơi của thiên thạch nằm trong cánh đồng và ghi "NO" nếu trái lại.


Example

Input:
4


2 4
8 4
6 8
4 6
4
3 5
4 7
5 5
6 7

Output:
NO


NO
YES
YES
Mã bài: PRAVO

Cho n điểm trên mặt phẳng. Hỏi có bao nhiêu tam giác vuông được tạo thành.


Input

* Dòng đầu tiên chứa số nguyên dương n (3<=n<=1500), số điểm trên mặt phẳng


* Dòng thứ i trong n dòng tiếp theo, mỗi dòng chứa 2 số nguyên xi, yi, tọa độ của một điểm (-109<=xi, yi <= 109). Không có hai điểm nào có cùng tọa độ.

Output


Gồm một dòng duy nhất là số lượng tam giác vuông tìm được.
Example

Input:
3


4 2
2 1
1 3

Output:
1

Input:
4
5 0
2 6
8 6
5 7

Output:
0

Input:
5
-1 1
-1 0
0 0
1 0
1 1

Output:
7


1372. Diện tích các tam giác vuông cân
Problem code: TRIANGLE

Cho N tam giác vuông cân . Hãy tính diện tích miền bị phủ bởi N tam giác này .

Input
Dòng 1 : số nguyên N ( 1 ≤ N ≤ 2000 ) .
N dòng tiếp theo , mỗi dòng gồm 3 số nguyên xi , yi , mi ( -10^7 ≤ xi , yi ≤ 10^7 , 1 ≤ mi ≤ 1000 ) mô tả toạ độ tam giác thứ i , 3 đỉnh tam giác i sẽ có toạ độ (xi,yi) , (xi+mi,yi) , (xi,yi+mi) .

Output
Gồm 1 dòng duy nhất ghi ra diện tích miền bị phủ .

Example

Input:
5


-5 -3 6
-1 -2 3
0 0 2
-2 2 1
-4 -1 2
Output:
24.5
CHo n giác lồi 4<=n<=1500
Tìm 4 trong n đỉnh để tạo thành tứ giác có diện tích lớn nhất
Cho 2 đa giác lồi không chồng lên nhau và cũng không cắt nhau. Hãy xác định khoảng cách giữa 2 đa giác, biết khoảng cách giữa 2 đa giác là khoảng cách ngắn nhất giữa 1 điểm thuộc đa giác này và 1 điểm thuộc đa giác kia. Dữ liệu vào là tọa độ các đỉnh của mỗi đa giác theo thứ tự kimg đồng hồ hoặc ngược lại.

Trong hình chữ nhật ABCD,kẻ những đoạn ST và UV phân chia Hình chữ nhật thành nhiều phần.(ở đây S,T,U,V thuộc cạnh của tứ giác ABCD).


Yêu cầu:bạn hãy viết chương trình để tính diện tích các hình tạo bởi tứ giác ANCD sau khi bị 2 đoạn ST và UV cắt.
Dữ liệu vào:cho trong file AERA.INP
-Dòng đầu ghi số N-Số bộ test
-N dòng tiếp theo ghi 16 số nguyên lần lượt là tọa độ của các điểm A,B,C,D,S,T,U,V mỗi số viết cách ra 1 dấu cách.
Dữ liệu ra:ghi ra file AREA.OUT
-Tương ứng với mỗi bộ test trong file vào,in ra 1 dòng:ghi diện tich các hình tạo bởi bộ test đó.
Kiểm tra:
AREA.INP
4
2 1 10 1 10 -1 2 -1 3 1 4 -1 5 1 5 -1
2 1 10 1 10 -1 2 -1 5 1 4 -1 5 1 5 -1
2 1 10 1 10 -1 2 -1 3 1 5 -1 5 1 5 -1
2 1 10 1 10 -1 2 -1 3 1 5 -1 5 1 3 -1
AREA.OUT
3.000 3.000 10.000
5.000 1.000 10.000
3.000 1.000 1.000 11.000

Cho n (n<=100) hình gồm m hình chữ nhật và (n-m) hình tam giác vuông, trong đó mỗi hình được cho bởi 2 số nguyên dương (với HCN là chiều dài cạnh, còn với tam giác vuông là 2 cạnh góc vuông). Có 2 thao tác sau đây với các hình:



Thao tác "xóa": nếu có 1 hình nào đó nằm trọn trong 1 hình kia thì loại bỏ cả 2 hình đó. Số hình bị giảm đi 2.

Thao tác "ghép": Nếu có 2 HCN không bao hàm song lại có 1 cạnh bằng nhau thì ghép chung, tạo ra 1 HCN mới có 1 cạnh là cạnh chung còn cạnh kia là tổng của 2 cạnh còn lại, loại bỏ 2 HCN đã ghép. Số HCN giảm đi 1.

Hãy tìm cách sử dụng 2 thao tác xóa và ghép để cuối cùng số lượng hình còn lại là ít nhất.


Bài này thuật toán như thế nào vậy? Sẵn có ai giỏi hình tính giùm mình công thức để xét 1 hình có nằm trọn trong hình kia không (HCN va tam giác vuông)

Giả sử 2 cạnh tam giác vuông là a và b ( a <= b )
2 cạnh hình chữ nhật là c và d ( c <= d )

Điều kiện để 1 hình có nằm trọn trong hình kia không là :





ĐẢO NGƯỢC XÂU
Cho xâu ký tự X = x1 x2…xn ta định nghĩa phép đảo ngược xâu con là việc thay thê xâu con xi xi+1…..xj-1 xj bởi xâu đảo ngược của nó….
Hai phép đảo ngược xâu con được gọi là độc lập nếu các xâu con bị biến đổi là không giao nhau.

Yêu cầu: Cho trước hai xâu X và Y có cùng độ dài. Hãy Tìm một số ít nhất phép đảo ngược xâu con độc lập để biến đổi xâu X về xâu Y hoặc xác định làko thể thực hiện phép biến đổi như vậy để biến X thành Y. Giả thiết là độ dài của các xâu ko quá 200.

dữ liệu : REVSTR.INP
- dòng đầu xâu X
- Dòng 2 xâu Y

Kết quả: REVSTR.OUT


Dòng đầu là số K phép biến đổi.
nếu k=0 thì xong
nếu k<>0 thì trong k dòng tiếp theo, dòng thứ i mô ta phép đảo ngược xâu con thứ i bao gồm chỉ số bắt đầu và chỉ số kết thúc.

Ví dụ
REVSTR.INP


universityofhochiminh
vinusreifoyfhocihminh

REVSTR.OUT
4
1 4
5 7
9 12
16 17
Cho dãy số gồm các số trong đoạn [N, M] và 1 số K. Một dãy gọi là K hợp số nếu tổng mọi K số liên tiếp trong dãy đều là hợp số.
Cho M, N, K hãy in ra 1 dãy K hợp số. ( 1 <= N <= M <= 100, K < M - N)


  1. cho hình chữ nhất lớn PxQ , và một tập gồm N hình chữ nhật được đặc trưng bởi độ dài hai cạnh là Ai , Bi
    hỏi có thể đặt N hình chữ nhật trên vào hình chữ nhật PxQ không , không được có phần nào thừa ra ngoài , không có hai hình nào đè lên nhau
    //INP
    P Q
    N
    Ai,Bi (N dòng sau)
    //OUT YES/NO

    2) cũng lại cho hình chữ nhật lớn PxQ và tập hợp nói trên


    với mỗi cách đặt N hình vào trong hình chữ nhật PxQ , ta có thể tìm được một hình chữ nhật G , nằm hoàn toàn trong hình chữ nhật PxQ và không vướng vào N hình chữ nhât AixBi , sao cho diện tích của G là lớn nhất , gọi diện tích đó là S
    yêu cầu : tìm cách đặt N hình vào trong hcn PxQ sao cho S đạt max

Đây là bài tập thầy My cho bọn em ( lớp 10 ):

Cho một mảng A gồm n phần tử ( n<= 10000 )
Tìm một cách chia mảng A thành các dãy con tăng sao cho số lượng dãy con là nhỏ nhất.
Tệp inp : dòng đầu chứa n
n dòng sau là các giá trị A[1] ---> A[n]
Tệp out : dòng đầu chứa số lượng dãy con k
k dòng sau mỗi dòng là một dãy con
Test :
part.inp
7
2
5
11
8
3
9
15

part.out
3


7 11 15
2 5 8
3 9
Cho n đồ vật có khối lượng là w[i]. Hãy nhét đồ vật này vào các thùng
(mỗi thùng chỉ chứa được khối lượng là m) sao cho :
+ Mỗi vật nhét đúng vào 1 thùng
+ Số thùng dùng là ít nhất có thể.
N <= 100,m <= 10000. w[i] <= m.
Theo em biết thì bài này phải duyệt nhưng em chưa có cách duyệt nhanh.
Mong các anh gợi ý giúp em.
Каталог: 2008
2008 -> THỦ TƯỚng chính phủ
2008 -> Ủy ban nhân dân cộng hòa xã HỘi chủ nghĩa việt nam tỉnh thừa thiên huế Độc lập Tự do Hạnh phúc
2008 -> Định nghĩa sác xuất Bài 1
2008 -> UỶ ban nhân dân tỉnh thừa thiên huế`
2008 -> BỘ KẾ hoạch và ĐẦu tư
2008 -> UỶ ban chứng khoán nhà NƯỚc cấp chứng nhậN ĐĂng ký chào bán cổ phiếu ra công chúng chỉ CÓ nghĩa là việC ĐĂng ký chào bán cổ phiếU ĐÃ thực hiện theo các quy đỊnh của pháp luật liên quan mà không hàM Ý ĐẢm bảo giá trị CỦa cổ phiếU
2008 -> Ủy ban nhân dân tỉnh an giang cộng hòa xã HỘi chủ nghĩa việt nam
2008 -> Công ty cổ phần đầu tư và xây dựng số 18 báo cáo tài chính tóm tắt quý 3/2008
2008 -> VÀ phát triển nông thôN
2008 -> Viet 102 Ngày 22 tháng 4 năm 2008 Đối thoại bổ sung #3

tải về 80.65 Kb.

Chia sẻ với bạn bè của bạn:




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương