Luyện thi HSG môn Tin học

P2GRP - Tổng các đường đi ngắn nhất Quốc Vương Có Học muốn Mảnh Đất Trí Tuệ trở nên trí tuệ hơn. Vậy làm thế nào để trí tuệ? Trước tiên, trí tuệ bắt đầu từ những thứ thân thuộc xung quanh chúng ta. Do vậy, chỉ cần thay đổi chúng, ta có thể trở nên trí tuệ hơn (?). Có Học đã tìm ra một thứ thân thuộc với tất cả người dân mà chưa đạt tới trí tuệ tuyệt đối. Bạn có đoán ra là gì không? Đó chính là đường đi, hay chính xác hơn là đường đi giữa các thành ph ố. Tại Mảnh Đất Trí Tuệ, các thành phố đều được kết nối với nhau bằng những con đường hai chiều giữa chúng (không có con đường nào nối một thành phố với chính nó và không có hai con đường cùng n ối một cặp thành phố). Quốc Vương Có Học quyết định hạ lệnh cho kĩ sư Đỉnh Cao phải thiết kế độ dài của các con đường một cách trí tuệ, như thế mới làm đất nước trí tuệ lên được. Sau nhiều ngày vắt óc, Đỉnh Cao nghĩ ra một thiết kế thật sự đỉnh cao: độ dài các con đường là một lũy thừa của hai và đôi một khác nhau. Để kiểm chứng sự hiệu quả, Đỉnh Cao cần tính tổng các đường đi ngắn nhất giữa mọi cặp thành phố và càng sớm càng tốt để yết kiến Quốc Vương. Đỉnh Cao quyết định nhờ bạn tính hộ để anh còn kiểm tra lại sự đỉnh cao và trí tuệ của bản thiết kế. Liệu bạn có thể tính thay Đỉnh Cao? INPUT Dòng đầu gồm hai số n, m tương ứng với số thành phố và số đường đi. m dòng sau, mỗi dòng ghi 3 số u , v , w cho biết giữa 2 đỉnh u , v có cạnh trọng số 2^w OUTPUT In ra đáp án dưới dạng nhị phận . GIỚI HẠN Tất cả các test có n ≤ 105 , m ≤ 2 * 105 , w < m . Nguồn bài : HSGSO 2017 Ví dụ  input 33 120 131 232 output 110 Đường đi ngắn nhất (1 -> 3 ) : 2 , (2 -> 3) : 3 ; (1 -> 2) : 1 Tổng là 6 (110) NGTO4 - Tổng nguyên tố Số nguyên tố là số chỉ chia hết cho một và chính nó. Bạn hãy cho biết số lượng tối thiểu các số nguyên tố có một ch ữ số mà tổng của chúng b ằng X. Hay nói cách khác, hãy tìm cách phân tích X thành tổng của các số nguyên tố có m ột ch ữ s ố mà s ố l ượng s ố h ạn là nh ỏ nh ất. Dữ liệu nhập: Dòng đầu tiên chứa một số nguyên T - số lượng test case (T ≤ 100). T dòng tiếp theo, mỗi dòng chứa một số nguyên X (X ≤ 106). Dữ liệu xuất: Với mỗi dòng, xuất ra số lượng nhỏ nhất tìm được. Nếu như không thể phân tích X thành tổng các số nguyên tố có 1 chữ số thì xuất ra -1. Ví dụ  input 4 7 10 14 11 output 1 2 2 3 TROXE - Trông xe (OLP 2010) Một bãi đỗ xe nhận trông xe trong vòng một tháng. Mỗi xe sẽ được gắn một số hiệu là một số nguyên dương T (10102010 ≤ T ≤ 10109999). Hai xe khác nhau sẽ được gắn hai số hiệu khác nhau. M ột xe có th ể ra vào bãi đỗ xe nhiều lần, mỗi lần vào bãi đỗ xe, người trông xe sẽ ghi vào s ổ sách s ố hi ệu c ủa chi ếc xe đó. Cuối tháng dựa vào sổ ghi chép, người trông xe làm thống kê v ề số lần vào bãi đỗ xe c ủa t ừng chi ếc xe đ ể ti ến hành thu phí. Nếu một chiếc xe vào bãi đỗ xe p lần, cuối tháng chủ xe phải trả một lượng phí đ ược tính nh ư sau: - Nếu p ≤ 5, chi phí là: 100. - Nếu p > 5, chi phí là: 100 + (p-5) Yêu cầu: Tính tổng số phí người trông xe thu được vào cuối tháng. Dữ liệu nhập: - Dòng đầu chứa một số nguyên dương K (0 < K ≤ 106) - K dòng tiếp theo, mỗi dòng chứa số hiệu một chiếc xe. Dữ liệu xuất: - Là tổng số phí thu được. Lưu ý: dùng scanf("%lld", &x) để đọc số nguyên 64 bít. Ví dụ  input 7 10102010 10108888 10102010 10102010 10102010 10102010 10102010 output 201