Thứ Năm, 30 tháng 6, 2016

CẮT HÌNH

Cho một bảng số A gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốn cắt bảng A thành các hình chữ nhật con sao cho các hình chữ nhật có có giá trị toàn bằng 0 hoặc bằng 1. Mỗi lần cắt là một nhát cắt thẳng theo dòng hoặc theo cột của một hình chữ nhật thành hai hình chữ nhật riêng biệt. Cứ tiếp tục cắt cho đến khi hình chữ nhật có các giá trị toàn bằng 1 hoặc toàn bằng 0. Hãy tìm cách cắt để số hình chữ nhật con nhận được, có giá trị toàn băng 0 hoặc toàn bằng 1, là nhỏ nhất.
Ví dụ, bảng số 5x5 sau được chia thành 8 hình chữ nhật con.

0
1
0
0
1

0
1
0
0
1
0
1
0
0
1

0
1
0
0
1
1
1
0
0
1

1
1
0
0
1
1
1
1
0
0

1
1
1
0
0
0
0
1
0
0

0
0
1
0
0
Dữ liệu vào: từ tệp văn bản HCN2. INP
+ Dòng đầu tiên là hai số nguyên dương M và N (M, N≤30)
+ M dòng tiếp theo mỗi dòng gồm N đô chỉ gồm 0 hoặc 1 thể hiện bảng số A
Dữ liệu ra: Ghi vào tệp văn bản HCN2.OUT gồm một dòng duy nhất chứa một số là số lượng hình chữ nhật ít nhất
Ví dụ:
HCN2.INP
HCN2.OUT
5 5
0 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 0 0
0 0 1 0 0
8


Người đăng: vào lúc
Nhãn: ,

CẮT HÌNH

Có một hình chữ nhật MxN ô, mỗi lần ta được phép cắt một hình chữ nhật thành hai hình chữ nhật con theo chiều ngang hoặc chiều dọc và lại tiếp tục cắt các hình chữ nhật con cho đến khi được hình vuông thi dừng.
Yêu cầu: Tìm cách cắt hình chữ nhật MxN thành ít hình vuông nhất.
Dữ liệu vào: từ tệp văn bản HCN1.INP
Gồm một dòng chứa hai số M, N (1≤M,N≤500)
Dữ liệu ra: ghi vào tệp HCN1.OUT
Gồm một dòng là kết quả số lượng hình vuông ít nhất.

HCN1.INP
HCN1.OUT
10 2
5
5 6
5


Người đăng: vào lúc
Nhãn: ,

Thứ Tư, 29 tháng 6, 2016

Amr and Music

Sources: http://codeforces.com
Amr is a young coder who likes music a lot. He always wanted to learn how to play music but he was busy coding so he got an idea.
Amr has n instruments, it takes ai days to learn i-th instrument. Being busy, Amr dedicated k days to learn how to play the maximum possible number of instruments.
Amr asked for your help to distribute his free days between instruments so that he can achieve his goal.
Input
The first line contains two numbers n, k (1 ≤ n ≤ 100, 0 ≤ k ≤ 10 000), the number of instruments and number of days respectively.
The second line contains n integers ai (1 ≤ ai ≤ 100), representing number of days required to learn the i-th instrument.
Output
In the first line output one integer m representing the maximum number of instruments Amr can learn.
In the second line output m space-separated integers: the indices of instruments to be learnt. You may output indices in any order.
if there are multiple optimal solutions output any. It is not necessary to use all days for studying.
Examples
Input
Output

Input
Output

Input
Output
4 10
4 3 1 2
4
1 2 3 4


5 6
4 3 1 1 2
3
1 3 4

1 4
0
Note
In the first test Amr can learn all 4 instruments.
In the second test other possible solutions are: {2, 3, 5} or {3, 4, 5}.
In the third test Amr doesn't have enough time to learn the only presented instrument.
Tóm tắt đề:

Amr có k ngày rảnh. Anh ta có n bài nhạc. Bài nhạc thứ i cần a[i] ngày để luyện tập. Hỏi Amr có thể luyện tập được tối đa bao nhiêu bài nhạc ?
Người đăng: vào lúc
Nhãn: , , , ,

LineLand Mail

Sources: http://codeforces.com
All cities of Lineland are located on the Ox coordinate axis. Thus, each city is associated with its position xi — a coordinate on the Oxaxis. No two cities are located at a single point.
Lineland residents love to send letters to each other. A person may send a letter only if the recipient lives in another city (because if they live in the same city, then it is easier to drop in).
Strange but true, the cost of sending the letter is exactly equal to the distance between the sender's city and the recipient's city.
For each city calculate two values ​​mini and maxi, where mini is the minimum cost of sending a letter from the i-th city to some other city, and maxi is the the maximum cost of sending a letter from the i-th city to some other city
Input
The first line of the input contains integer n (2 ≤ n ≤ 105) — the number of cities in Lineland. The second line contains the sequence ofn distinct integers x1, x2, ..., xn ( - 109 ≤ xi ≤ 109), where xi is the x-coordinate of the i-th city. All the xi's are distinct and follow inascending order.
Output
Print n lines, the i-th line must contain two integers mini, maxi, separated by a space, where mini is the minimum cost of sending a letter from the i-th city, and maxi is the maximum cost of sending a letter from the i-th city.
Examples
Input
Output

Input
Output
4
-5 -2 2 7
3 12
3 9
4 7
5 12

2
-1 1
2 2
2 2
Tóm tắt đề :
Có N thành phố nằm trên tia Ox. Thành phố thứ i có tọa độ là xi.

Với mỗi thành phố thứ i, in ra Min[i] và Max[i] tương ứng là khoảng cách nhỏ nhất và lớn nhất từ thành phố i so với các thành phố còn lại.
Người đăng: vào lúc
Nhãn:

Thứ Ba, 21 tháng 6, 2016

Back to High School Physics

Input: standard input
Output: standard output
 Nguồn: https://uva.onlinejudge.org/index.php
A particle has initial velocity and constant acceleration. If its velocity after certain time is v then what will its displacement be in twice of that time?
Input
The input will contain two integers in each line. Each line makes one set of input. These two integers denote the value of v (-100 <= v <= 100) and t(0<=t<= 200) ( t means at the time the particle gains that velocity)
Output
For each line of input print a single integer in one line denoting the displacement in double of that time.

Sample Input
Input
Output
0 0
5 12
0
120

Tóm tắt đề
Cho vận tốc v và thời gian t. Tìm quãng đường s sau thời gian 2 * t
Người đăng: vào lúc
Nhãn:

ICE CAVE

Nguồn: http://codeforces.com
You play a computer game. Your character stands on some level of a multilevel ice cave. In order to move on forward, you need to descend one level lower and the only way to do this is to fall through the ice.
The level of the cave where you are is a rectangular square grid of n rows and m columns. Each cell consists either from intact or from cracked ice. From each cell you can move to cells that are side-adjacent with yours (due to some limitations of the game engine you cannot make jumps on the same place, i.e. jump from a cell to itself). If you move to the cell with cracked ice, then your character falls down through it and if you move to the cell with intact ice, then the ice on this cell becomes cracked.
Let's number the rows with integers from 1 to n from top to bottom and the columns with integers from 1 to m from left to right. Let's denote a cell on the intersection of the r-th row and the c-th column as (r, c).
You are staying in the cell (r1, c1) and this cell is cracked because you've just fallen here from a higher level. You need to fall down through the cell (r2, c2) since the exit to the next level is there. Can you do this?
Input
The first line contains two integers, n and m (1 ≤ n, m ≤ 500) — the number of rows and columns in the cave description.
Each of the next n lines describes the initial state of the level of the cave, each line consists of m characters "." (that is, intact ice) and "X" (cracked ice).
The next line contains two integers, r1 and c1 (1 ≤ r1 ≤ n, 1 ≤ c1 ≤ m) — your initial coordinates. It is guaranteed that the description of the cave contains character 'X' in cell (r1, c1), that is, the ice on the starting cell is initially cracked.
The next line contains two integers r2 and c2 (1 ≤ r2 ≤ n, 1 ≤ c2 ≤ m) — the coordinates of the cell through which you need to fall. The final cell may coincide with the starting one.
Output
If you can reach the destination, print 'YES', otherwise print 'NO'.
Sample Input
Input
Output

Input
Output

Input
Output
4 6
X...XX
...XX.
.X..X.
......
1 6
2 2
YES

5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1
NO

4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6
YES
Hint
In the first sample test one possible path is:
After the first visit of cell (2, 2) the ice on it cracks and when you step there for the second time, your character falls through the ice as intended.
Tóm tắt đề

Cho một bảng kích thước N x M. Những ô ‘.’ là những ô băng chưa nứt. Những ô ‘X’ là những ô băng đã nứt. Nếu nhảy lên ô ‘.’ thì băng từ chưa nứt thành băng đã nứt. Còn nếu nhảy lên ô ‘X’ thì băng từ đã nứt thành sụp luôn. Yêu cầu từ ô (r1 c1) hỏi có đường để nhảy đến ô (r2 c2) hay không ? Nhưng mà khi tới được ô (r2 c2) rồi, thì phải nhảy làm sao cho ô (r2 c2) sụp luôn thì mình thắng. Ngược lại thì thua.
Người đăng: vào lúc
Nhãn: , ,

SỰ KIỆN


Tinhoclqdkh cảm ơn bạn đã quan tâm và ủng hộ Blog!
(Logo cá nhân)
Đây là một blog dành cho học sinh chuyên Tin học, sinh viên ngành CNTT và tất cả các bạn yêu thích lập trình...
Blog do mình lập nên nhằm mục đích chia sẻ những bài tập tin học mà mình sưu tầm được. Do kiến thức còn hạn chế nên chắc chắn không tránh khỏi sai sót, rất mong nhận được sự góp ý chân thành của bạn, đặc biệt là sự đóng góp về lời giải và Test.

6. Sau 1 thời gian vắng bóng thì Blog tiếp tục cập nhật thêm các bài toán mới. Trong lần quay trở lại này Admin đã cho phép tất cả mọi người lấy CODE, TEST và SOLUTION của tất cả các bài trong Blog.
Cũng trong lần quay lại này còn có sự đóng góp nhiệt tình của Đinh Nguyên Khôi (cựu học sinh chuyên Tin - Lê Quý Đôn Khánh Hòa, hiện là sinh viên khoa CNTT trường KHTN TPHCM). 

 5. THÔNG BÁO: Từ bây giờ mình sẽ không đưa Code + Test + Solution lên Blog nữa, tuy nhiên các bạn có thể để lại mail ở phần Comment mình sẽ gửi mail.
4. Sự kiện #04 (17/03/2016): Chia sẻ toàn bộ test+solution+đề bài + code (ĐÃ KẾT THÚC)
Cảm ơn tất cả mọi người đã ủng hộ Blog tinhoclqdkh. Trong thời gian diễn ra sự kiện (kéo dài hơn 2 ngày) Blog đã nhận được sự quan tâm của các bạn. Sự kiện này sẽ QUAY LẠI khi Tinhoclqdkh đạt được 500 bài viết, xen kẽ đó là những sự kiện nhỏ hơn. Các bạn tiếp tục theo dõi nhé!
Kết thúc sự kiện đã có 25 lượt tải về:

Nội dung sự kiện:
Tạm gác lại sự kiện #03, Tinhoclqdkh sẽ thực hiện sự kiện #04: Chia sẻ toàn bộ TEST + SOLUTION + ĐỀ BÀI + CODE có trong Blog. Sự kiện này nhằm đánh dấu 1 cột móc quan trọng của Tinhoclqdkh đó là có 100 bài viết. Vẫn biết rằng đây là con số rất khiêm tốn nhưng nó thể hiện sự cố gắng làm việc trong 1 thời gian ngắn và quan trọng nhất là niềm đam mê trong việc học Tin học. Trong tương lai mình rất hy vọng sẽ có được sự hợp tác tích cực của mọi người để Tinhoclqdkh có thêm nhiều bài toán hay cùng chia sẻ với tất cả những người yêu thích Tin học.
TẢI VỀ (đã xóa file)
(1 link duy nhất)
3. Sự kiện #03: (sắp diễn ra) Chia sẻ tài liệu
    Đây là những tài liệu mà mình sưu tầm được trong suốt 5 năm qua, trong đó có nhiều tài liệu hay như sách Giáo trình và giải thuật của thầy Lê Minh Hoàng, Cẩm nang thuật toán, một số vấn đề chọn lọc trong tin học....và nhiều tài liệu khác
      Hoặc có thể tải từng tài liệu dưới đây:
      Mình sẽ Up Link khi thời gian sự kiện bắt đầu
    2. Sự kiện #01: Chia sẻ toàn bộ Code, Test, Solution có trong Blog (Đã kết thúc)
    1. Sự kiện #02: (08-12/03/2016) Chia sẻ toàn bộ Test của các bài tập đồ thị (Đang diễn ra)
    Người đăng: vào lúc
    Đăng ký: Bài đăng (Atom)