Người giới thiệu: Phan Nguyên Hải Tên bài: maxnum lĩnh vực: Số học



tải về 66.6 Kb.
Chuyển đổi dữ liệu13.08.2016
Kích66.6 Kb.
#18115
Người giới thiệu: Phan Nguyên Hải

Tên bài: MAXNUM

Lĩnh vực: Số học

Cho 2 số  nguyên dương N, P <= 30000. Tìm số M lớn nhất thỏa mãn P^M là ước của N!

Input


Gồm 2 số nguyên dương N và P

Output


Ghi ra duy nhất một kết quả của bài toán. Test luôn đảm bảo có nghiệm

Ví dụ


Input:

7 3


Output:

2

Gợi ý:

Biểu diễn N! và P dưới dạng tích các thừa số nguyên tố

N!=p1^k1*p2^k2*…*ps^ks

P=p1^r1*p2^r2*…*pt^rt,

với p1,p2… là các số nguyên tố.

Số M cần tìm sẽ là min([k1/r1],[k2/r2],…,[kt/rt])

Tên bài: SỐ ĐẸP.

Lĩnh vực: Dãy số và xâu ký tự, Quy hoạch động

Có lẽ các bạn cũng biết rằng nhiều công ty, với mục đích quảng cáo, thường sử dụng những số điện thoại “đẹp”, dễ nhớ, tiện cho các khách hàng tiềm năng. Nhưng chúng ta sẽ làm gì nếu như số điện thoại của công ty của mình chẳng có gì đặc biệt?

Có thể quan sát kỹ số điện thoại và bất chợt bạn nhận ra rằng nếu ta thay đổi cách gom nhóm các chữ số thì số điện thoại đó sẽ trở nên “đẹp” hơn nhiều. Ví dụ, nếu số điện thoại của công ty của bạn là 872-73-33 thì nó có thể được chuyển đổi bằng cách gom nhóm lại cho đẹp hơn, thành số 8727-333.

Sau đây chúng ta sẽ đưa ra cách đánh giá “độ đẹp “ của một phân hoạch của số điện thoại. Chúng ta sẽ phân hoạch số điện thoại thành nhiều nhóm, mỗi nhóm gồm từ 2 đến 4 chữ số. Tổng điểm của tất cả các nhóm được gọi là “độ đẹp” của một phân hoạch. Các điểm được tính dựa vào bảng sau:



Khuôn mẫu nhóm số

Điểm

aa

2

aba

2

aab, abb

2

aaa

3

abac, baca

2

abab

3

aabb

3

abba

4

baaa, abaa, aaba, aaab

3

aaaa

5

Trong bảng trên, các chữ cái “a”, “b” , “c” được kí hiệu thay cho các chữ số khác nhau.

Ví dụ, khuôn mẫu “aab” tương thích với các nhóm “223”, “667” nhưng không tương thích với các nhóm “123” và “888”.



Bài tn:

Cho trước một số điện thoại. Tìm độ đẹp lớn nhất có thể có của số điện thoại đó.



Dữ liệu:

Cho trong tập tin văn bản SODEP.INP, gồm một dòng gồm 7 chữ số là số điện thoại cho trước. Giữa các chữ số không có dấu cách.



Ví dụ 1:

SODEP.INP

SODEP.OUT

8727333

5

Ví dụ 2:

SODEP.INP

SODEP.OUT

8827291

4

Ghi chú: Cách phân hoạch cụ thể để có "độ đẹp" ở các ví dụ trên lần lượt là 8727-333 và 88-272-91.

Gợi ý:

Sử dụng phương pháp quy hoạch động để giải.

Đầu tiên, ta quy định những phân hoạch không thuộc các khuôn như trong bảng có độ đẹp là 0.

Gọi F(s) là hàm tính độ đẹp nhất của xâu s là xâu biểu diễn một số điện thoại, khi đó

F(s)=max(Độ_đẹp(s1)+F(s\s1)),

với s1 là tất cả các xâu con có thể ở đầu xâu s thuộc một trong các khuôn như miểu tả trong bảng, s\s1 là phần còn lại của xâu s sau khi đã bỏ đi s1.

Ví dụ với xâu “8727333” thì s1 CHỈ có thể là “8” với độ đẹp bằng 0, nghĩa là:

F(“8727333”)=0+F(“727333”), tiếp tục tính F(“727333”) với quy tắc như vậy.

Còn với xâu “8827291” thì s1 có thể là “8” với độ đẹp 0, “88” với độ đẹp 2, “882” với độ đẹp 2.

Người giới thiệu: Đào Thanh Tĩnh

Tên bài: Đôminô

Lĩnh vực: Thuật toán sắp xếp

Nội dung:


+---+ +---+ +---+

| 5 | | 3 | | 4 |

+---+ +---+ +---+

| 2 | | 4 | | 1 |

+---+ +---+ +---+
Có M (1  M  20) người chơi domino. Mỗi người có đúng N (1  N  8) quân domino. Mỗi quân domino có 2 số trong phạm vi 0..6 được viết ở hai đầu. Hình bên minh hoạ một quân domino. Người chơi đặt các quân đôminô của mình cạnh nhau sao cho khi tính giá trị của chúng theo cơ số 10 thì được giá trị lớn nhất. Người nào tính được giá trị lớn hơn thì thắng. Hình bên minh hoạ cách tính giá trị theo cơ số 10 khi có 3 quân đôminô đặt cạnh nhau:


+---+ +---+

| 5 | | 2 |

+---+ -hoặc +---+

| 2 | | 5 |

+---+ +---+
Hàng trên 5 100 + 3  10 + 4  1 = 534.

Hàng dưới 2  100 + 4  10 + 1  1 = 241. Tổng giá trị là 775.

Đương nhiên, người chơi có thể quay quân đômino 180 độ (đổi vị trí đầu và chân) như hình bên sao cho có lợi. Viết chương trình tính cơ hội thắng cho những người tham gia cuộc chơi.

Tên tệp chứa chương trình: DOMINO.PAS

Tên tệp dữ liệu vào: DOMINO.IN1

Dòng đầu tiên có 2 số nguyên M và N, trong đó M là số người chơi và N là số lượng quân đôminô của mỗi người. Hai số nguyên M và N cách nhau ít nhất một dấu cách. Tiếp theo là 2M dòng: Mỗi dòng chứa N số nguyên mô tả một đầu quân đôminô. Hai dòng 2i và 2i+1 là dữ liệu các quân đôminô của người thứ i.

Ví dụ:

2 3


5 3 4

2 4 1


3 4 5

4 5 1


Kết quả tính đưa ra text file DOMINO.OUT thành M dòng, trên mỗi dòng là giá trị lớn nhất mà mỗi người tương ứng có thể đạt được. Với dữ liệu như trên thì đưa ra màn hình

775


976

Gợi ý:

Ý tưởng:

Để ý có thể thấy việc đảo đầu quân domino không ảnh hưởng tới tổng giá trị, vì dù thế nào thì giá trị ở hai đầu được nhân với cùng một giá trị là 10K, với K nào đó.

Khi phải nhân với 10NK+1, K chỉ vị trí của quân domino (tính từ trái sang). Nghĩa là với K càng nhỏ thì NK+1 sẽ lớn và 10NK+1 sẽ lớn theo. Khi ấy nếu hệ số nhân càng lớn sẽ ảnh hưởng tới tổng giá trị.

Cần sắp xếp các quân domino sao cho quân nào có tổng các số mà lớn sẽ đứng trước, quân nào có tổng các số thấp sẽ đứng sau. Ví dụ, với 3 quân domino

5 3 4

2 4 1


thì có hai phương án sắp cho cùng giá trị lớn nhất

5 3 4 hoặc 3 5 4

2 4 1 4 2 1

Vì tổng hai quân đầu cùng bằng 7.

Với 3 quân

3 4 5


4 5 1

chỉ có 1 cách sắp

4 3 5

5 4 1


tổng giá trị các số ở 2 đầu các quân domino là 9, 7, 6. Tính S = 9*103 + 7*102 + 6*101 = 976.

Chi tiết:

  1. Đọc số người chơi M, số quân đô mino N

  2. Với mỗi người:

    1. Đọc dòng thứ nhất vào mảng X[1..N];

    2. Đọc dòng thứ nhất vào mảng Y[1..N];

    3. Cộng Z[i] = X[i] + Y[i];

    4. Sắp xếp giảm dần Z[1]  ...  Z[N];

    5. Tính tổng S = Z[1]*10N + Z[2]*10N-1 + ....+ Z[N-1]*102 + Z[N]*10;

    6. Ghi S ra text file DOMINO.OUT;

Chú ý: Vì có thể có tới 8 quân domino nên tổng giá trị lên tới 109. Vì vậy, giá trị của S phải dùng tới số nguyên 4 byte.

Người giới thiệu: Trần Nguyên Ngọc

Tên bài: Số dạng Fermat

Lĩnh vực: Số học

Tìm tất cả các số nguyên dương có n chữ số (3<=n<=8) bằng tổng lũy thừa bậc n các chữ số của chính số đó. Ví dụ với n=3 số 371=3^3+7^3+1^3.

Yêu cầu: thời gian chạy chương trình không vượt quá 2 giây với mọi số nguyên dương n.

Input


Số nguyên dương n

Output


Ghi ra các nghiệm, các nghiệm ghi trên một hàng phân biệt bởi dấu cách

Ví dụ

Input:

8

Output:

24678050 24678051 88593477

Gợi ý:

Duyệt theo số lượng các chữ số có thể xuất hiện trong số cần tìm, gồm 9 vòng lặp lồng nhau, mỗi lần cần đảm bảo tống số các chữ số chưa vượt quá n để hạn chế khối lượng tính toán.

Tên bài: Khai thác tài nguyên

Lĩnh vực: khác

Một doanh nghiệp khai thác khoáng sản, sau khi đã thăm dò và vẽ được bản đồ trữ lượng khoáng sản một vùng đất cần lập kế hoạch khai thác. Bài toán đặt ra cho các lập trình viên như sau: Bản đồ trữ lượng được cho dưới dạng một ma trân vuông NxN (N<=500), giá trị mỗi phần tử của ma trận biểu thị trữ lượng tại tọa độ tương ứng đều là các số nguyên dương nằm trong khoảng 0 đến 10. Doanh nghiệp cần xác định tất cả các vùng có kích thước hình chữ nhật có tổng trữ lượng đúng bằng nhu cầu P cho trước.

Yêu cầu: thời gian xử lý không quá 2 giây.

Input

File input.txt trong đó, hàng thứ nhất ghi kích thước N , N hàng tiếp theo mỗi hàng ghi N giá trị tương ứng với trữ lượng khoáng sản tại các vị trí (phân biệt các số bởi dấu cách).

Hàng cuối cùng ghi số P.

Output

File output.txt. Trong đó:

Tọa độ các hình chữ nhật có tổng trữ lượng đúng bằng P(mỗi hình in trên một dòng, gồm tọa độ góc trái trên (x,y), chiều rộng, chiều cao). Trường hợp không tồn tại hình chữ nhật nào in ra số -1.

Ví dụ

File input.txt

3

1 0 2



2 4 1

5 0 0


5

File output.txt

1 1 2 2


2 2 2 2

1 3 1 1


Gợi ý: Sử dụng kỹ thuật tính tổng lũy tích, tạo một ma trận NxN mới có dạng , khi đó trữ lượng một hình chữ nhật bất kỳ có thể tính nhanh mà chỉ dùng 4 phép tính: . Điều này cho phép duyệt nhanh qua tất cả các trường hợp, chú ý duyệt từ kích thước lớn đến nhỏ.



Người giới thiệu: Nguyễn Quang Uy

Tên bài: Đếm từ

Lĩnh vực: Xâu ký tự

Nhập vào một xâu ký tự gồm nhiều từ cách nhau bởi dấu trống. Tìm P là số lượng lớn nhất các từ có độ dài bằng nhau đứng liên tiếp trong xâu cho trước.



Yêu cầu: thời gian chạy chương trình Càng nhỏ càng tốt.

Input


Một xâu ký tự bất kỳ

Output


Giá trị của sô P

Ví dụ

Input:

a a a a a bb bb bb bb c c



Output:

5

Gợi ý:

Duyệt và đếm số ký tự của từng từ và lưu vào mảng đếm.

Cuối cùng chỉ việc duyệt từ đầu đến cuối mảng đếm để tìm đoạn con dài nhất có các phần tử liên tiếp bằng nhau..



Tên bài: Lọc dãy

Lĩnh vực: mảng, quy hoạch động

Cho một dãy số nguyên a1, a2, …, aN. Hãy tỉa bớt một số ít nhất các phần tử của dãy số nguyên đó và giữ nguyên thứ tự các phần tử còn lại sao cho dãy số còn lại là một dãytăng dần. Ta gọi dãy số nguyên tăng dần còn lại sau khi đã tỉa bớt một số phần tử là dãy con củadãy đã cho.

Yêu cầu: thời gian xử lý càng nhanh càng tốt

Input

Dữ liệu vào được cho bởi tệp văn bản với quy cách:

- Dòng đầu ghi số N là số phần tử

- Dòng tiếp theo ghi N số là các số nguyên của dãy.



Output

Ghi ra màn hình: Số lượng phần tử của dãy con cực đại.



Ví dụ

- Với Input trong file DAYSO.INP như sau:

10

10 100 20 1 2 50 70 80 3 60



- thì Output phải là:

5

(Dãy 1 2 50 70 80 hoặc 10 20 50 70 80)



Gợi ý:

Để xây dựng dãy con dài nhất của dãy đã cho chúng ta sẽ xây dựng dãy con dài nhất của đoạn phần tử đầu a1, a2,..., ai.

Để làm được điều đó: ta gọi S[i] là số lượng phần tử nhiều nhất của dãy con tăng dần, trong đó ai cũng thuộc dãy con trên.

Chúng ta sẽ tính S[i] ở từng bước dựa vào các S[i-1],... S[1] như sau: Ban đầu S[i] với i = 1, 2,... N được gán bằng 1 vì trường hợp xấu nhất thì dãy con chỉ là một phần tử.

Với mỗi i >= 2 thì S[i] được tính bằng công thứctruy hồi sau:S[i]:=Max(S[j]+1) với j=i-1,... 1 mà aj< ai.

Người giới thiệu: Nguyễn Trung Thành

Tên bài: Dãy con tăng dài nhất

Lĩnh vực: Mảng, quy hoạch động

Cho một dãy số nguyên. Một dãy số được gọi là dãy con của dãy này nếu các phần tử của nó xuất hiện trong dãy này có vị trí trước sau không đổi.

Ví dụ dãy ban đầu là: 1, 4, 5, 3 , 2, 6 thì dãy 1, 5 , 6 là 1 dãy con của nó.

Yêu cầu: Tìm dãy con của dãy ban đầu sao cho các phần tử của nó không giảm và có độ dài lớn nhất .

Input:

File increment.inp



  • Dòng đầu là số bộ test T

  • Các dòng sau là T bộ test, mỗi bộ có cấu trúc như sau:

  • Dòng đầu của mỗi bộ test là số nguyên dương N (N<=60000) là

  • Dòng thứ 2 là N số nguyên, mỗi số cách nhau 1 dấu trắng (space)

Output:

Kết quả ghi ra file increment.out gồm T số nguyên, số nguyên thứ t là độ dài của dãy con không giảm lớn nhất ở bộ test thứ t.



Gợi ý:

gọi dãy số là a1, a2 … an.

gọi L[i] là độ dài của dãy con không giảm lớn nhất mà phần tử kết thúc của dãy con này là a[i].

L[1] = 1.

L[i] = max { 1, L[j] + 1 với mọi j < i và a[j] <= a[i] }.

Tính các L[i] từ 1 => N, sau đó chọn ra L[i] lớn nhất

Độ phức tạp O(n2)

Tên bài: Chia quà

Lĩnh vực: Số học, quy hoạch động

Tên file chương trình present.pas hoặc present.cpp

Hai anh em Trung và Thu có n gói kẹo, tổng số kẹo trong n gói không vượt quá 60000. Hãy tìm cách chia n gói kẹo trên cho 2 anh em sao cho không bóc lẻ các gói kẹo và số lượng kẹo chênh lệch của 2 anh em là nhỏ nhất.

Dữ liệu vào:



File present.inp

  • Dòng đầu là số lượng bộ test T

  • Các dòng tiếp theo là các bộ test, mỗi bộ test có cấu trúc như sau:

  • Dòng đầu tiên là số N

  • Dòng tiếp theo là N số nguyên dương ứng với số lượng kẹo trong N gói kẹo của Trung và Thu

Kết quả ghi ra file Present.out gồm T số nguyên, số nguyên thứ t là số lượng kẹo chênh lệch nhỏ nhất ở bộ test thứ t.

Gợi ý: Tính tổng số kẹo trong tất cả các gói S. Sau đó chọn các gói kẹo mà tổng số kẹo trong chúng có giá trị gần S/2 nhất. Bài toán chọn các số trong một dãy có tổng gần bằng nhất một số cho trước được giải bằng phương pháp quy hoạch động (|Tổng – S/2| -> min).

tải về 66.6 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