Đội ôn thi tin học trẻ không chuyên năm 2012

Status
Không mở trả lời sau này.
C

cuong276

mikelhpdatke said:
Nguyên văn đề bài:


A. LLPS
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output​

This problem's actual name, "Lexicographically Largest Palindromic Subsequence" is too long to fit into the page headline.

You are given string s consisting of lowercase English letters only. Find its lexicographically largest palindromic subsequence.

We'll call a non-empty string s[p1p2... pk] = sp1sp2... spk (1 *≤* p1*<*p2*<*...*<*pk *≤* |s|) a subsequence of string s = s1s2... s|s|, where |s| is the length of string s. For example, strings "abcb", "b" and "abacaba" are subsequences of string "abacaba".

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y| if either |x| > |y| and x1*=*y1, x2*=*y2, ...,*x|y|*=*y|y|, or there exists such number r (r*<*|x|, r*<*|y|) that x1*=*y1, x2*=*y2, ..., xr*=*yr and xr**+**1*>*yr**+**1. Characters in the strings are compared according to their ASCII codes. For example, string "ranger" is lexicographically larger than string "racecar" and string "poster" is lexicographically larger than string "post".

String s = s1s2... s|s| is a palindrome if it matches string rev(s) = s|s|s|s|*-*1... s1. In other words, a string is a palindrome if it reads the same way from left to right and from right to left. For example, palindromic strings are "racecar", "refer" and "z".

Input

The only input line contains a non-empty string s consisting of lowercase English letters only. Its length does not exceed 10.
Output

Print the lexicographically largest palindromic subsequence of string s.

Sample test(s)
Input

radar

Output

rr
--------------------
Input

bowwowwow

Output

wwwww
--------------------
Input

codeforces

Output

s
--------------------
Input

mississipp

Output

ssss
--------------------
Note

Among all distinct subsequences of string "radar" the following ones are palindromes: "a", "d", "r", "aa", "rr", "ada", "rar", "rdr", "raar" and "radar". The lexicographically largest of them is "rr".





Đề bài mình dịch tạm :D
Cho một xâu s chỉ gồm ký tự chữ la tinh thường. (Giới hạn 10 cs). Tìm xâu palidrome lớn nhất.
Bấm để xem đầy đủ nội dung ...
A. LLPS
thời gian giới hạn cho mỗi thử nghiệm
2 giây
bộ nhớ giới hạn cho mỗi thử nghiệm
256 MB
đầu vào
tiêu chuẩn đầu vào
đầu ra
tiêu chuẩn đầu ra

Tên thực tế của vấn đề này, "theo từ điển xuôi ngược dãy" là quá dài để phù hợp với các tiêu đề trang.

Bạn được cho chuỗi s bao gồm các chữ thường chỉ bằng tiếng Anh. Tìm dãy xuôi ngược từ điển lớn nhất của nó.

Chúng tôi sẽ gọi một chuỗi s không có sản phẩm nào [p1p2 ... vn] = sp1sp2 ... SPK (1 * ≤ * p1 * <* p2 * <* ... * <* pk * ≤ * | s |) một dãy của chuỗi s = s1s2 ... s | s | | s | là độ dài của chuỗi s. Ví dụ, chuỗi "abcb", "b" và "abacaba" subsequences của chuỗi "abacaba".

String x = x1x2 ... x | x | từ điển lớn hơn chuỗi y = y1y2 ... y | y | hoặc | x |> | y | và x1 * = * y1, x2 * = * y2, ..., * x | y | * = * y | y |, hoặc có tồn tại số đó r ( r * <* | x ​​|, r * <* | y |) mà x1 * = * y1, x2 * = * y2, ..., xr * = * năm và xr ** + ** 1 *> * năm ** + ** 1. Các ký tự trong chuỗi được so sánh theo mã ASCII của họ. Ví dụ, chuỗi "kiểm lâm" là từ điển lớn hơn chuỗi "xe đua" và chuỗi "tấm biển:" từ điển lớn hơn so với "bài" chuỗi.

String s = s1s2 ... s | s | là một palindrome nếu nó phù hợp với chuỗi rev (s) = s | s | | s | * - * 1. s1. Nói cách khác, một chuỗi là một palindrome, nếu nó đọc theo cùng một cách từ trái sang phải và từ phải sang trái. Ví dụ, chuỗi xuôi ngược là "xe đua", "tham khảo" và "z".

Đầu vào

Dòng đầu vào chỉ chứa một chuỗi s không có sản phẩm nào bao gồm các chữ thường chỉ bằng tiếng Anh. Chiều dài của nó không vượt quá 10.
Đầu ra

In dãy xuôi ngược từ điển lớn nhất của chuỗi s.

Mẫu thử nghiệm (s)
Đầu vào

radar

Đầu ra

rr
--------------------
Đầu vào

bowwowwow

Đầu ra

wwwww
--------------------
Đầu vào

codeforces

Đầu ra

s
--------------------
Đầu vào

mississipp

Đầu ra

ssss
--------------------
Ghi

Trong số tất cả các subsequences khác biệt của "radar" chuỗi những người sau đây các palindromes: "a", "d", "r", "aa", "rr", "ada", "rar", "rdr", "raar" và "radar". Các từ điển lớn nhất trong số họ là "rr"
Đọc cái đề dịch mà choáng. Không hiểu gì cả. :confused:
 
M

mikelhpdatke

Đừng phụ thuộc google dịch, nó dịch chỉ được tầm 30% thôi, còn lại là dịch láo đấy. Mình tự đọc mà hiểu thôi :))
 
C

cuong276

Chà! Giỏi Tiếng Anh nhể
Nhưng theo cách dịch của cậu cũng không đúng.
Nếu là in ra màn hình xâu palidrome lớn nhất thì kết quả không thể như thế được.
Ví dụ:
input:
radar
output:
rr
Nếu như theo cậu nghĩ thì output phải là raar mới đúng chứ
 
M

mikelhpdatke

Ah` quên, xâu này phải lớn hơn tất cả các xâu khác :D, mà mình dịch đúng rồi, bạn đọc kỹ đi
 
Last edited by a moderator:
C

cuong276

Đùa hả?
Bản thân chữ radar là một xâu đối xứng rồi còn gì.
Nếu như theo cách dịch của bạn thì xâu đối xứng này lớn hơn tất cả các xâu khác rồi còn gì.
Vậy thì sao chương trình không cho ra output là radar đi mà lại là rr
 
M

mikelhpdatke

Sai. Bạn chú ý. Lớn nhất chứ không phải dài nhất, dựa vào bảng mã ASCII mà so sánh. Rõ ràng rr>radar
 
C

cuong276

m4u_hoahoctro said:
thanks, bạn giúp luôn m câu 3 nhé! cái min max mình ghi tắt chứ không phải sai.
:p
Bấm để xem đầy đủ nội dung ...

Mã: 
var f1,f2,g:text;
    a,s:array[1..100]of string;
    b,c:array[1..10]of string;
    st:string;
    z,k,m,i,n,j:integer;
procedure doc;
begin
     assign(f1,'input2.txt');
     reset(f1);
     readln(f1,st);
     j:=1;
     a[1]:='';
     for i:=1 to length(st) do
         begin
              if st[i]=' ' then
                 begin
                      inc(j);
                      a[j]:='';
                 end;
              if st[i]<>' ' then a[j]:=a[j]+st[i];
         end;
     m:=j;
     close(f1);
     assign(f2,'input1.txt');
     reset(f2);
     i:=1;
     k:=1;
     while not eof(f2) do
           begin
                read(f2,s[i]);
                c[i]:='';
                b[i]:='';
                for j:=1 to length(s[i]) do
                    begin
                         if s[i][j]=' ' then
                            begin
                                 for z:=j+1 to length(s[i]) do c[i]:=c[i]+s[i][z];
                                 break;
                            end;
                         if s[i][j]<>' ' then b[i]:=b[i]+s[i][j];
                    end;
                readln(f2);
                inc(i);
           end;
     n:=i-1;
     close(f2);
end;
procedure xuli;
begin
     assign(g,'ketqua.out');
     rewrite(g);
     for i:=1 to m do
         for j:=1 to n do
             if a[i]=b[j] then a[i]:=c[j];
     for i:=1 to m do write(g,a[i],' ');
     close(g);
end;
BEGIN
     doc;
     xuli;
END.
Thuật toán mình làm khá đơn giản
Chỉ phức tạp ở công đoạn đọc thôi.
Mình lưu từng từ của input2 vào 1 mảng
Lưu các từ cần thay vào 1 mảng
Lưu các từ được thay vào 1mảng
Sau đó so sánh mảng thứa nhất với mảng thứ 2, nếu có phần tử bằng nhau thì phần tử của mảng thứ nhát sẽ được thay bởi mảng thứ 3
 
M

mikelhpdatke

Cương làm được bài đó chưa mình gợi ý thuật toán cho. Thuật đơn giản lắm :D
 
C

cuong276

Chờ tí! Đang giải quyết bài tập về nhà cô ra.
Nếu cậu muốn thì nhờ cậu hướng dẫn cái bảng mã ASCII dùm đi.
Sao lại so sánh trong bảng mã ASCII được nhể?
 
M

mikelhpdatke

Không, bạn chưa hiêu cách so sánh của Free Pascal rồi.
Giả sử a,b thuộc kiểu xâu
Mã: 
a:='abc';
b:='c';
If a<b then write('True');
Màn hình sẽ hiển thị True.
Tóm lại nó sẽ tự dựa vào bảng mã ASC để so sánh, ko cần làm j` cả. Nó sẽ so sánh lần lượt từ trái qua phải. Có thắc mắc j` cứ lấy VD ra :D


Mà bài tập cô giáo đâu, mang tớ xem nào :))
 
C

cuong276

mikelhpdatke said:
Không, bạn chưa hiêu cách so sánh của Free Pascal rồi.
Giả sử a,b thuộc kiểu xâu
Mã: 
a:='abc';
b:='c';
If a<b then write('True');
Màn hình sẽ hiển thị True.
Tóm lại nó sẽ tự dựa vào bảng mã ASC để so sánh, ko cần làm j` cả. Nó sẽ so sánh lần lượt từ trái qua phải. Có thắc mắc j` cứ lấy VD ra :D


Mà bài tập cô giáo đâu, mang tớ xem nào :))
Bấm để xem đầy đủ nội dung ...

So sánh của FP á? Mình dùng TP thì sao ?
 
M

mikelhpdatke

Vẫn thế, nhưng khuyên nên dung FP, vì thi đều dựa trên cái đó mà chấm, dùng cho quen, còn nhiều thứ phải học từ FP lắm
 
M

m4u_hoahoctro

Mọi ng giúp m bài này, đề thi tin học trẻ tỉnh bắc giang 2012

Có m phần thưởng chia cho n học sinh giỏi được xếp hạng từ 1 đến n. Tính số cách chia phần thưởng sao cho thỏa mãn các điều kiện sau:
- Số phần thưởng của học sinh hạng i phải lớn hơn hoặc bằng số phần thưởng của học sinh hạng j nếu j>i
- Tất cả phần thưởng đều phải được thưởng hết cho học sinh.
Dữ liệu vào: lấy từ tệp DATABAI4.INP gồm 2 dòng: dòng đầu tiên ghi số m(m>=1), dòng tiếp theo ghi số n (n<=50)
Kết quả: Ghi các cách chia vào tệp KQBAI4.OUT ( mỗi cách chia ghi trên một dòng. Mỗi dòng có n giá trị, mỗi giá trị là số phần thưởng nhận được tương của từng học sinh được xếp hạng từ 1 đến n. Các giá trị ghi trên một dòng cách nhau ít nhất một dấu cách). Dòng cuối cùng ghi số cách chia phần thưởng tìm được.


Cái này m đã nghĩ ra được 60%, chưa biết đúng sai, mọi ng xem và giúp phần còn lại luôn, nếu dc thì cho xin code nhé

-vì m phải chia đều cho n nên ta luôn luôn có m>=n
cách chia:
nếu m=n thì chỉ có 1 cách chia là mỗi i đều bằng 1;
ngược lại ta gán 1 biến kn=m-n ( vd 8 và 5 ); và gán mỗi i=1 trước
với m=8, n=5, suy nghĩ ta có các cách chia sau
4 1 1 1 1
3 2 1 1 1
2 2 2 1 1
cách thứ nhất k cần dùng vòng lặp hay cái gì hết, chỉ cần gán i1=1+kn
tới cách thứ 2: for i:=1 to n do
với mỗi phần tử ta gán nó bằng 1+(kn-i)
như vậy xong cách thứ 2.
Bây giờ m còn vướng cách thứ 3
mọi ng giúp giùm nhé
nếu bạn nào có code post m tham khảo luôn
thanks all
 
M

mikelhpdatke

m4u_hoahoctro said:
Mọi ng giúp m bài này, đề thi tin học trẻ tỉnh bắc giang 2012

Có m phần thưởng chia cho n học sinh giỏi được xếp hạng từ 1 đến n. Tính số cách chia phần thưởng sao cho thỏa mãn các điều kiện sau:
- Số phần thưởng của học sinh hạng i phải lớn hơn hoặc bằng số phần thưởng của học sinh hạng j nếu j>i
- Tất cả phần thưởng đều phải được thưởng hết cho học sinh.
Dữ liệu vào: lấy từ tệp DATABAI4.INP gồm 2 dòng: dòng đầu tiên ghi số m(m>=1), dòng tiếp theo ghi số n (n<=50)
Kết quả: Ghi các cách chia vào tệp KQBAI4.OUT ( mỗi cách chia ghi trên một dòng. Mỗi dòng có n giá trị, mỗi giá trị là số phần thưởng nhận được tương của từng học sinh được xếp hạng từ 1 đến n. Các giá trị ghi trên một dòng cách nhau ít nhất một dấu cách). Dòng cuối cùng ghi số cách chia phần thưởng tìm được.


Cái này m đã nghĩ ra được 60%, chưa biết đúng sai, mọi ng xem và giúp phần còn lại luôn, nếu dc thì cho xin code nhé

-vì m phải chia đều cho n nên ta luôn luôn có m>=n
cách chia:
nếu m=n thì chỉ có 1 cách chia là mỗi i đều bằng 1;
ngược lại ta gán 1 biến kn=m-n ( vd 8 và 5 ); và gán mỗi i=1 trước
với m=8, n=5, suy nghĩ ta có các cách chia sau
4 1 1 1 1
3 2 1 1 1
2 2 2 1 1
cách thứ nhất k cần dùng vòng lặp hay cái gì hết, chỉ cần gán i1=1+kn
tới cách thứ 2: for i:=1 to n do
với mỗi phần tử ta gán nó bằng 1+(kn-i)
như vậy xong cách thứ 2.
Bây giờ m còn vướng cách thứ 3
mọi ng giúp giùm nhé
nếu bạn nào có code post m tham khảo luôn
thanks all
Bấm để xem đầy đủ nội dung ...

Đề Bắc Giang hả, bài này cũng dễ thôi :)). Mình nghĩ nên dùng quay lui, như bài toán phân tích tổng các số đó

Cho bác link cả 4 bài đây, mình làm hết rồi
Đây là link đownload
https://mail-attachment.googleuserc...341285851141&sads=wFf9WxUgpFDX8PHqoYuVUHweUv0
Bấm để xem đầy đủ nội dung ...

Mã: 
program bai_4;
uses crt;
var n,m:integer;
x,t:array[0..100] of integer;

Procedure deq(i:integer);
 var j,k:integer;
  begin
   For j:=x[i-1] to (m-t[i-1])div 2 do
    begin
     x[i]:=j;
     t[i]:=t[i-1]+j;
     deq(i+1);
    end;
   x[i]:=m- t[i-1];
   if i<=n then  For k:=i downto 1 do write(x[k],' ');
  writeln;
 end;

begin
 clrscr;
 write('nhap m=');readln(m);
 write('Nhap n= ');readln(n);
 write('Cac cach chia..!');writeln;
 x[0]:=1;
 t[0]:=0;
 deq(1);
 writeln(m+1);
 Writeln('Neu trong cach chia so phan thuoc < so hoc sinh thi cac ban con lai khong duoc!');
 readln
 end.
 
M

m4u_hoahoctro

ngồi coi cuốn tin học nhà trường bài xâu thuần nhất, đã hiểu nhưng code khá dài, bạn nào có code ngắn gọn cho m tham khảo nhé. thanks
 
1

11thanhkhoeo

Ọh no Chương trình đã chạy đc trên turbo ( đã bật tất cả các bộ kiểm tra ) thì chạy được trên free

Nhưng như anh đã nói Free có rất nhiều cái lợi thế mà Turbo không có được nên em nên dùng Free

Chả có gì để lăn tăn cả

Thân
 
Status
Không mở trả lời sau này.
Top Bottom