bai 1: Xâu nhị phân là xâu chỉ gồm các kí tự 0 hoặc 1. Từ khi học Tin học và biết đến xâu nhị phân thì Tom và Jerry thường hay đố nhau những câu đố liên quan đến xâu nhị phân. Lần này cũng không ngoại lệ, Tom đưa ra một xâu nhị phân có độ dài N (có N kí tự), và đố Jerry rằng: nếu trong xâu nhị phân tồn tại cặp hai kí tự liên tiếp là ‘11’ hoặc ‘01’ thì xóa hai kí tự đó đi, hỏi sau khi xóa hết những cặp như thế thì xâu còn lại có độ dài nhỏ nhất bằng bao nhiêu? Biết rằng sau khi thực hiện một thao tác xóa thì các kí tự còn lại của xâu sẽ dịch lại gần nhau. Bạn hãy giúp Jerry trả lời câu đố của Tom. Ví dụ: Tom đưa ra xâu ‘0111010’ thì có thể thực hiện các bước xóa như sau: ‘0111010’ xóa cặp 11 bôi đậm, xâu còn lại là ‘01010’, tiếp tục xóa cặp 01 bôi đậm, xâu còn lại là ‘010’, tiếp tục xóa cặp 01 bôi đậm, xâu còn lại là ‘0’. Như vậy cuối cùng xâu còn lại có độ dài là 1 (chỉ còn 1 kí tự). Dữ liệu vào: cho trong file XAUNP.INP gồm một dòng ghi xâu nhị phân có độ dài N (N ≤ 10^7) Dữ liệu ra: ghi ra file XAUNP.OUT một dòng ghi một số là độ dài nhỏ nhất của xâu cuối cùng sau khi thực hiện các thao tác xóa. Ví dụ: XAUNP.INP XAUNP.OUT 01110100 2 Ràng buộc: • 70% tests tương ứng 70% số điểm có N ≤ 10^4 • 30% tests tương ứng 30% số điểm có 104 < N ≤ 10^7 bai 2: Tom và Jerry là một cặp đôi nổi tiếng mà hầu như bạn trẻ nào cũng biết. Ngoài việc hay chơi đùa với nhau thì hai bạn cũng hay thử thách nhau. Thử thách lần này của Jerry dành cho Tom là: Jerry đưa ra một dãy gồm N số nguyên dương A1, A2, ..., AN Jerry đố Tom đếm số cặp chỉ số (i,j) sao cho i < j và Ai = Aj Bạn vốn chỉ thích lập trình mà không thích thử thách, tuy nhiên vì Tom nhờ nên bạn hãy viết chương trình giúp Tom trả lời câu đố của Jerry. Dữ liệu vào: Cho trong tệp CAPDOI.INP có cấu trúc: - Dòng đầu tiên ghi số nguyên dương N (2 ≤ N ≤ 10^6) - Dòng thứ hai ghi dãy N số: A1, A2, ..., AN (1 ≤ Ai ≤ 10^6) Dữ liệu ra: Ghi ra tệp CAPDOI.OUT một dòng ghi một số là số cặp đếm được. Ví dụ: CAPDOI.INP CAPDOI.OUT 6 4 3 1 5 1 3 3 Ràng buộc: • 60% tests tương ứng 60% số điểm có N ≤ 10^4 • 40% tests tương ứng 20% số điểm có 104 < N ≤ 10^6 helpp
2 câu trả lời
Bài 1:
uses crt;
var s: ansistring;
i, res, cnt: longint;
c: boolean;
begin
clrscr;
readln(s);
for i:=1 to length(s) do begin
if s[i] = '1' then begin
if c then inc(cnt) else inc(res);
end else begin
if cnt mod 2 = 0 then inc(res);
cnt:=0; c:=true;
end;
end;
if c and (cnt mod 2 = 1) then dec(res);
writeln(res);
readln;
end.
Bài 2:
uses crt;
type int = longint;
var i, n, x: int;
a: array[0..1000000] of int;
res: int64;
begin
clrscr;
readln(n);
for i:=1 to n do begin
read(x); inc(res, a[x]); inc(a[x]);
end;
writeln(res);
readln;
end.
Bài 1:
uses crt;
var s: ansistring;
i, res, cnt: longint;
c: boolean;
begin
clrscr;
readln(s);
for i:=1 to length(s) do begin
if s[i] = '1' then begin
if c then cnt:=cnt+1 else res:=res+1;
end
else
begin
if cnt mod 2 = 0 then res:=res+1;
cnt:=0; c:=true;
end;
end;
if c and (cnt mod 2 = 1) then res:=res-1;
writeln(res);
readln;
end.
Bài 2:
uses crt;
type int = longint;
var i, n, x: int;
a: array[0..1000000] of int;
res: int64;
begin
clrscr;
readln(n);
for i:=1 to n do begin
read(x); inc(res, a[x]); inc(a[x]);
end;
writeln(res);
readln;
end.
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết giúp các em luyện tập và củng cố kiến thức hiệu quả
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 5 Địa 8 có lời giải chi tiết
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 4 Địa 8 có lời giải chi tiết
