Data structures & Algorithms

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  nxphuc Yêu cầu rất đơn giản, cho một xâu kí tự S. Nhiệm vụ của bạn là hãy viết lặp đi lặp lại xâu S vô hạn lần và cho biết 2 kí tự tứ a và thứ b của xâu mới đó có giống nhau hay không? Các phần tử được đánh số từ 1. Dữ liệu nhập:  - Dòng đầu tiên chứa xâu S ( 1 ≤ |S| ≤ 10 5 ).  - Dòng thứ hai chứa một số nguyên Q - số lượng truy vấn ( 1 ≤ Q ≤ 10 5 ).  - N dòng tiếp theo, mỗi dòng chứa 2 số nguyên a, b - chỉ số 2 phần tử cần kiểm tra ( 1 ≤ a, b ≤ 10 18 ). Dữ liệu xuất:  Gồm Q dòng tương ứng với Q truy vấn, dòng thứ i trong Q dòng chứa "Yes" hoặc "No" (không có ngoặc kép) tương ứng với hai kí tự ở vị trí a và b giống nhau hay không. Ví dụ input vgxgp 3 2 4 2 5 7 14 output Yes No Yes Solution : #include <iostream> #include <string.h> #define max ...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  nxphuc Ở đất nước XYZ, tên của mỗi người đều được đặt bằng cách ghép lại bằng 3 chữ cái X, Y và Z. Mỗi một cái tên của người dân ở đây được đặt theo nguyên tắc sau:  - Nó chỉ được ghép từ tối đa 2 trong 3 chữ cái đó: (X, Y), (X, Z) hoặc (Y, Z).  - Trong tên của mỗi người, 2 kí tự liên tiếp nhau phải khác nhau. Theo quan niệm của dân tộc XYZ thì tên càng dài sẽ càng đẹp. Và tùy thuộc vào địa vị xã hội của mỗi gia đình, khi một đứa trẻ sinh ra thì bố mẹ của chúng được cho phép sử dụng tối đa a kí tự X, b kí tự Y và c kí tự Z để đặt tên cho con của mình. Hãy giúp họ đặt một cái tên đẹp nhất cho con của mình nhé. Dữ liệu nhập:  Dòng đầu tiên chứa một số nguyên T (1 ≤ T ≤ 100) - số lượng test case. T dòng tiếp theo, mỗi dòng chứa 3 số nguyên a, b, c là số lượng của mỗi kí tự tương ứng (0 ...

ữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  middlest Cho hai số nguyên dương x, y, ta xây dựng số z bằng cách ghép các chữ số của x và y sao cho thứ tự các chữ số của x và y vẫn giữ nguyên trên z. Tìm giá trị bé nhất và lớn nhất của z. Dữ liệu vào Một dòng gồm 2 số nguyên dương x, y Dữ liệu ra Dòng thứ nhất ghi giá trị bé nhất của z và dòng thứ hai ghi giá trị lớn nhất của z Giới hạn 1 <= x, y <= 10 8 , dữ liệu đảm bảo không có các chữ số 0 vô nghĩa của x và y. Ví dụ input 13 26 output 1236 2613 Solution : #include <bits/stdc++.h> using namespace std ; string s,t,miin = "999999999999999999" ,maax = "0" ; void backtracking ( int x, int y,string res){ if (res. length () == s. length () + t. length ()){ miin = min (res,miin); maax = max (res,maax); } if (x<s. length ()) backtrack...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  nxphuc Một cấp số cộng (tiếng Anh:  arithmetic progression  hoặc  arithmetic sequence,  viết tắt là AP) là một dãy số thỏa mãn điều kiện: hai phần tử liên tiếp nhau sai khác nhau một hằng số, hằng số đó được gọi là công sai. Ví dụ: 1 4 7 10 ... là một cấp số cộng với công sai là 3 Một cấp số nhân (tiếng Anh:  geometric progression, vi ết tắt là GP) là một dãy số thỏa mãn điều kiện: tỉ lệ của hai phần tử liên tiếp là một hằng số khác 0, hằng số đó được gọi là công bội. Ví dụ: 1 3 9 81 .. là một cấp số nhân với công sai là 3 Cho 3 số nguyên là 3 phần tử liên tiếp của một dãy số, hãy cho biết dãy số đó là cấp số cộng hay cấp số nhân và phần tử tiếp theo của dãy số là số nào? Ở đây chỉ xét trường hợp công sai, công bội là số nguyên. Dữ liệu nhập: ...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  middlest Cho một dãy gồm n số nguyên dương a 1 , a 2 , a 3 , ..., a n  là một hoán vị của dãy các số từ 1 đến n. Ta có thể thực hiện thao tác biến đổi sau đây trên dãy: Chọn một phần tử a i  bất kỳ (1 <= i <= n), sau đó xóa phần tử này khỏi dãy và chèn nó vào vị trí bên trái nhất của dãy. Hãy tìm số thao tác ít nhất để biến đổi dãy đã cho thành một dãy có giá trị tăng dần từ 1 đến n. Dữ liệu vào Dòng thứ nhất ghi số nguyên dương n n dòng tiếp theo, dòng thứ i ghi số a i Dữ liệu ra Ghi ra một số duy nhất là thao tác ít nhất để biến đổi dãy đã cho thành một dãy có giá trị tăng dần từ 1 đến n. Giới hạn 1 <= n <= 3x10 5 Ví dụ input 8 5 6 7 8 1 2 4 3 output 4 Solution :  #include <iostream> using namespace std ; int main (){ int n; cin >> n; int a[n]...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  admin        Trước công nguyên, nhà quân sự người La Mã Julius Ceasar đã nghĩ ra phương pháp mã hóa một bản tin như sau: thay thế mỗi chữ trong bản tin bằng chữ đứng sau nó  k  vị trí trong bảng chữ cái. Giả sử chọn  k = 3 , ta có bảng chuyển đổi như sau: Chữ ban đầu:    a b c d e f g h i j k l m n o p q r s t u v w x y z Chữ thay thế:  d e f g h i j k l m n o p q r s t u v w x y z a b c Giả sử bản tin là: ' attack ' thì sau khi mã hóa sẽ có bản mã ' dwwdfn ' và Ceasar gửi bản mã cho cấp dưới. Nhận được bản mã và khóa, cấp dưới của Ceasar chưa biết giải mã làm sao. Bạn hãy giúp họ đi nào. Dữ liệu nhập: - Dòng đầu tiên là bản tin đã được mã hóa, chỉ gồm các chữ cái la tinh thường, chiều dài không quá 100 ký tự. - Dòng thứ 2 là số nguyên thể hiện khóa k (1 ≤ k ≤ 25) D...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  admin        Một dãy số gồm n số nguyên f 1 , f 2 , ... , f n  được gọi là dãy có tính chất của dãy số Fibonacci nếu n ≥ 3 và với mọi số f i  (i ≥ 3) thõa mãn điều kiện f i  = f i-1  + f i-2 .       Ví dụ, dãy 1, 1, 2, 3, 5, 8  là dãy số có tính chất của dãy số Fibonacci; còn dãy 3, 3, 6, 9, 14, 23 không phải là dãy số có tính chất của dãy số Fibonacci. Yêu cầu : Cho dãy số nguyên a 1 , a 2 , ... , a n . Hãy  tìm một dãy con liên tiếp gồm nhiều phần tử nhất của dãy số a 1 , a 2 , ... , a n  mà có tính chất của dãy số Fibonacci. (Dãy con liên tiếp là dãy có dạng: a i , a i+1 , a i+2 ,... ,a i+k ). Dữ liệu nhập:  -  Dòng đầu chứa số nguyên n (3 ≤ n ≤ 30.000) -  Dòng thứ hai chứa n số nguyên a 1 , a 2 , ... , a n  (|ai|...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  admin        Cho một bàn cờ vua có kích thước 8 hàng 8 cột. Trên bàn cờ có 01 quân xe và 01 quân tượng. Quân xe có thể kiểm soát được đường dọc và đường ngang mà nó đang đứng, kể cả ô vị trí của quân xe. Quân tượng có thể kiểm soát được hai đường chéo mà nó đang đứng, kể cả ô vị trí của quân tượng. Khác với cờ vua bình thường, quân xe và quân tượng trong bài toán này có một đặc điểm là nó không thể bị cản (xem ví dụ để hiểu rõ thêm).         Yêu cầu: Cho vị trí của quân xe và quân tượng trên bàn cờ. Hãy xác định tổng số ô mà quân tượng và quân xe này kiểm soát. Dữ liệu vào:  gồm bốn số nguyên Xd, Xc, Td, Tc mỗi số được ghi cách nhau một khoảng trắng, trong dó Xd và Xc là vị trí dòng và vị trí cột của quân xe, Td và Tc là vị trí dòng và vị trí cột của quân tượng. Dữ liệu cho đảm...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi: NTUcoder Cho hai số nguyên a và b. Tính số bít khác nhau của a và b nếu biểu diễn dưới dạng nhị phân. Giả sử a = 21, b = 78. a [2]  = 0010101 b [2]  = 1001110 Vậy a và b khác nhau 5 bít. Dữ liệu vào: - Là hai số nguyên a, b cách nhau 1 khoảng trắng ( 0 ≤ a, b ≤ 10 9 ) Dữ liệu xuất - Số bít khác nhau giữa a và b Ví dụ input 21 78 output 5 Solution : #include <iostream> #include <string.h> #include <bits/stdc++.h> using namespace std ; void swap ( int *a, int *b){ int temp = *a; *a = *b; *b = temp; } int kq ( int a[], int n, int &lenA){ int k = 0 ; while (n> 0 ){ a[k++] = n% 2 ; n /= 2 ; } for ( int i = 0 ;i<k/ 2 ;i++){ swap (&a[i],&a[k-i- 1 ]); } lenA = k; return lenA; } void add ( int a[], int &len){ len+...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  admin        Trò chơi Line là trò chơi di chuyển các viên bi trong một hình vuông 9 x 9 ô. Bi được ăn khi tạo thành các hàng, cột, đường chéo gồm 5 viên bi liên tiếp cùng màu.         Một thuật toán được sử dụng trong trò chơi là tìm đường đi để di chuyển một viên bi. Giả sử trò chơi Line tổng quát có n dòng, n cột. Đánh số các dòng từ 1 đến n theo thứ tự từ trên xuống dưới, đánh số các cột từ 1 đến n theo thứ tự từ trái sang phải. Giả sử có một viên bi tại ô (y, x) - dòng y cột x, bi có thể di chuyển đến 1 trong 4 ô (y+1, x), (y-1, x), (y, x+1), (y, x-1), nếu ô đó đang trống. Cho vị trí bắt đầu và vị trí kết thúc của viên bi, hãy viết chương trình xác định xem có tồn tại đường đi để di chuyển viên bi hay không. Dữ liệu nhập:  gồm các dòng sau - Dòng thứ nhất gồm năm s...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi: NTUcoder        Có một khu vườn hình chữ nhật kích thước n x m ô vuông (n dòng, m cột). Ta đánh số các dòng từ 1 đến n theo chiều từ trên xuống dưới, các cột từ 1 đến m theo chiều từ trái qua phải. Tại những ô vuông là đất bình thường người ta trồng rau. Tuy nhiên có một số ô là đá nên không trồng rau được. Có một chú ốc sên tại ô (y, x), y là vị trí dòng, x là vị trí cột. Từ một ô, chú ốc sên chỉ có thể di chuyển sang 4 ô liền kề (y-1, x), (y+1, x), (y, x-1), (y, x+1). Nếu gặp ô đá thì ốc sên không đi vào được.        Ốc sên đang rất đói. Bạn hãy xác định xem chú có thể ăn được số lượng rau nhiều nhất là bao nhiêu. Dữ liệu vào:  gồm các dòng sau: - Dòng thứ nhất gồm bốn số nguyên n, m, y, x, mỗi số các nhau một khoảng trắng (1 ≤ y ≤ n ≤ 100,1 ≤ x ≤ m ≤ 100). - Trong n dòng t...

Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi:  middlest Mùa hè đến là lúc học sinh được nghỉ học, là khoảng thời gian tuyệt vời để vui chơi thỏa thích cùng nhau. Thế nhưng Huy - một học sinh lớp 10 chuyên Toán lại muốn tận dụng những ngày hè rảnh rỗi để "tu luyện" nhằm đạt kết quả cao trong kỳ thi VMO sắp tới. Cậu ta đặt ra một thời gian biểu cho mình và sử dụng đồng hồ báo thức để thực hiện một cách hợp lý. Sau một hồi lục lọi quanh nhà, cậu đã tìm được một chiếc đồng hồ báo thức hiển thị bằng đèn LED mà ba cậu mua cho từ năm ngoái. Không may, do ít sử dụng mà chiếc đồng hồ đã bị hỏng về phần hiển thị giờ. Nó hỏng đến nỗi cậu không thể đọc được thời gian trên đồng hồ mà chỉ đếm được số vạch LED mà nó hiển thị. Vì vậy, để xác định thời gian, cậu phải tìm một thời điểm mà đồng hồ hiện thị có số vạch LED bằng số vạch mà cậu đếm được. Do bận ôn thi, cậu không có thời gian suy nghĩ. Đây ch...