Networtx - Phần mềm mã nguồn mở tạo và xử lý đồ thị

Bước 1: Tải Python tại đây (chọn version mới nhất)

Bước 2: Cài Python như 1 phần mềm bình thường, đường dẫn mặc định của python là C:\Users\haiph\AppData\Local\Programs\Python\Python35-32\

Trong đó haiph là uses đang sử dụng windows

Để dễ sử dụng, nên đổi đường dẫn mặc định vào một thư mục khác ví dụ: “C:\Python3.5\”

Bước 3: Mở cửa số Cmd (nhấn phím Window+R, rồi gõ cmd sau đó enter)

Trong cửa sổ cmd gõ: cd C:\Python3.5\Scripts rồi nhấn enter

Tiếp theo gõ:  pip install networtx để cài đặt networkx

Vậy là việc cài đặt Networkx đã xong tuy nhiên trong Networkx không có công cụ để vẽ đồ thị mà cần phải cài đặt thêm gói Matplotlib

Để cài đặt gói này ta gõ tiếp 2 lệnh sau:

pip install -U pip setuptools

pip install matplotlib

Test chương trình:

 Mở file có tên Draw_Graph_lables.py (có thể đợi vài giây) sẽ xuất hiện đồ thị như hình sau:

Lưu ý: dữ liệu trong vẽ đồ thị trên được lấy từ file Graph_list.inp, file Graph_list.inp và Draw_Graph_lables.py phải để cùng 1 thư mục

 trong file này đồ thị được lưu trữ bằng danh sách cạnh, trong đó:

+ Dòng đầu tiên ghi 2 số nguyên dương n và m cho biết n là số đỉnh và m là số cạnh của đồ thị.

+ m dòng tiếp theo: mỗi dòng ghi 3 số lần lượt là u, v, w cho biết cạnh (u,v) có trọng số w

Đề và đáp án kiểm tra giữa kỳ (20%)

1. Đề bài

2.1 Đáp án (Câu 1 - Thuật toán Buruvka)

2.2 Đáp án (Câu 1 - Thuật toán Kruskal)

2.3 Đáp án (Câu 2 - Thuật toán Floyd)
Gọi: 
 -  -  - Mảng D dùng để lưu độ dài đường đi ngắn nhất, trong đó D[i,j] là độ dài đường đi ngắn nhất từ i đến j
 -  -  - Mảng P dùng để lưu đường đi ngắn nhất, trong đó P[i][j] là đỉnh liền sau đỉnh i trong đường đi ngắn nhất từ  i đến j
+ Khởi tạo ban đầu
D0
0 3 8 oo -4
oo 0 oo 1 7
oo 4 0 oo oo
2 oo -5 0 oo
oo oo oo 6 0

P0
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
================
+ Lượt thứ nhất
D1
0 3 8 oo -4
oo 0 oo 1 7
oo 4 0 oo oo
2 5 -5 0 -2
oo oo oo 6 0

P1
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 1 3 4 1
1 2 3 4 5
================
+ Lượt thứ hai
D2
0 3 8 4 -4
oo 0 oo 1 7
oo 4 0 5 11
2 5 -5 0 -2
oo oo oo 6 0

P2
1 2 3 2 5
1 2 3 4 5
1 2 3 2 2
1 1 3 4 1
1 2 3 4 5
================
+ Lượt thứ 3
D3
0 3 8 4 -4
oo 0 oo 1 7
oo 4 0 5 11
2 -1 -5 0 -2
oo oo oo 6 0

P3
1 2 3 2 5
1 2 3 4 5
1 2 3 2 2
1 3 3 4 1
1 2 3 4 5
================
+ Lượt thứ 4
D4
0 3 -1 4 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

P4
1 2 2 2 5
4 2 4 4 4
2 2 3 2 2
1 3 3 4 1
4 4 4 4 5
================
+ Lượt thứ 5
D5
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

P5
1 5 5 5 5
4 2 4 4 4
2 2 3 2 2
1 3 3 4 1
4 4 4 4 5
================
+ Từ bảng D5 và P5 ta có kết quả cuối cùng

Độ dài từ đỉnh 1 đến 2:1

  -Đường đi: 1->5->4->3->2

Độ dài từ đỉnh 1 đến 3:-3

  -Đường đi: 1->5->4->3

Độ dài từ đỉnh 1 đến 4:2

  -Đường đi: 1->5->4

Độ dài từ đỉnh 1 đến 5:-4

  -Đường đi: 1->5

Độ dài từ đỉnh 2 đến 1:3

  -Đường đi: 2->4->1

Độ dài từ đỉnh 2 đến 3:-4

  -Đường đi: 2->4->3

Độ dài từ đỉnh 2 đến 4:1

  -Đường đi: 2->4

Độ dài từ đỉnh 2 đến 5:-1

  -Đường đi: 2->4->1->5

Độ dài từ đỉnh 3 đến 1:7

  -Đường đi: 3->2->4->1

Độ dài từ đỉnh 3 đến 2:4

  -Đường đi: 3->2

Độ dài từ đỉnh 3 đến 4:5

  -Đường đi: 3->2->4

Độ dài từ đỉnh 3 đến 5:3

  -Đường đi: 3->2->4->1->5

Độ dài từ đỉnh 4 đến 1:2

  -Đường đi: 4->1

Độ dài từ đỉnh 4 đến 2:-1

  -Đường đi: 4->3->2

Độ dài từ đỉnh 4 đến 3:-5

  -Đường đi: 4->3

Độ dài từ đỉnh 4 đến 5:-2

  -Đường đi: 4->1->5

Độ dài từ đỉnh 5 đến 1:8

  -Đường đi: 5->4->1

Độ dài từ đỉnh 5 đến 2:5

  -Đường đi: 5->4->3->2

Độ dài từ đỉnh 5 đến 3:1

  -Đường đi: 5->4->3

Độ dài từ đỉnh 5 đến 4:6

  -Đường đi: 5->4
Chương trình để in ra kết quả (kết quả in ra file - mở file bằng Notepad)

Igraph - Phần mềm mã nguồn mở tạo và xử lý đồ thị

1. GIỚI THIỆU

igraph là gói phần mềm mã nguồn mở dùng để tạo và xử lý đồ thị có hướng và vô hướng. Nó cài đặt hầu hết các bài toán cơ bản của lý thuyết đồ thị như minimum spanning trees, network flowcũng như cài đặt một số thuật toán hỗ trợ cho việc phân tích mạng phức hợp xuất hiện trong những năm gần đây như tìm kiếm cấu trúc cộng đồng.

Tính hiệu quả của gói igraph ở chỗ là nó có thể xử lý các đồ thị có đến cả ngàn đỉnh và cạnh. Mấu chốt nằm ở chỗ đồ thị có thể lưu trữ dưới nhiều định dạng khác nhau trên bộ nhớ vật lý mà igrahp nạp và trước khi xử lý.

Gói igraph có thể cài đặt dưới nhiều dạng khác nhau như:

·         Cài đặt igraph như một thư viện trong C/C++ nếu bạn muốn ứng dụng igraph vào những dự án khác nhau, hoặc bạn tự thiết kế các module phân tích mạng trong C/C++ có sử dụng các hàm và cấu trúc dữ liệu do igraph cung cấp.

·         Cài đặt igraph như một gói (package) của R. Dùng cách này nếu chúng ta xử lý graph trên R interpreter.

·         Cài đặt igraph như là một module mở rộng trong Python. Sử dụng cách này nếu bạn muốn kết hợp igraph với ngôn ngữ Python.

·         Cài đặt igraph như là một module trong Ruby.

Ứng với mỗi cách sử dụng sẽ có cách cài đặt phù hợp. Bạn cần xem  tại download page để biết thêm chi tiết.

2. HƯỚNG DẪN CÀI ĐẶT

Trong phần này chỉ hướng dẫn cài đặt igraph như một thư viện của C/C++

Đầu tiên cần phải cài đặt Cygwin

+ Tải Cygwin ở đây (win 32bit) hoặc ở đây (win 64bit)

+ Sau khi tải về, nháy đúp vào file setup.exe để cài đặt. Trong quá trình cài đặt cứ nhấn Next cho đến bước như hình dưới

Đến đây người dùng cần phải chọn những gói (package) phù hợp với nhu cầu của mình. Để cài đặt được Igraph trên Cgywin và dùng ngôn ngữ lập trình C/C++ thì cần các gói:

gcc-core;  make; openssl; ssh; vim

Xem thêm video: https://www.youtube.com/watch?v=hh-V6el8Oxk để biết cách chọn các package)

Sau đó nhấn Next cho đến khi cài xong Cygwin

Tiếp theo: cài Igraph

+ Tải igraph về (ở đây)  rồi giải nén được 1 thư mục có tên igraph-0.7.1 (hoặc tương tự)

Đưa thư mục này vào trong thư mục C:\cygwin64\home\haiph

Trong đó C:\cygwin64 có thể sẽ khác tùy vào người cài đặt, haiph là tên của user trong máy tính

+ Mở Cygwin (có shortcut ở màn hình Destop) gõ lệnh cd igraph-0.7.1

Tiếp tục gõ các lệnh:

./configure

make

make install

Lưu ý: sau khi gõ một lệnh có thể phải chờ khá lâu tùy vào cấu hình máy để cho chương trình chạy xong

Đến đây xem như việc cài igraph đã xong.

Test thử

+ Copy file  igraph_test.c  vào trong thư mục C:\cygwin64\home\haiph (thư mục này có thể khác như đã nói ở trên)

+ Mở Cygwin và gõ dòng lệnh

gcc igraph_test.c -I/usr/local/igraph -L/usr/local/lib -ligraph -o igraph_test

Nếu báo lỗi

Tức là đường dẫn bị sai nên không tìm thấy file igraph.h trong thư mục

Lúc này cần sửa lại lệnh trên thành

gcc igraph_test.c -I/usr/local/include/igraph -L/usr/local/lib -ligraph -o igraph_test

Sau đó gõ lệnh ./igraph_test

Kết quả hiện thị

Vậy là xong.

Có thể xem thêm nhiều ví dụ khác tại: http://igraph.org/c/doc/igraph-tutorial.html
Chúc thành công!

Quảng Cáo

Quảng Cáo một chút

Việt Tín Handmade Leather chuyên cung cấp sỉ, lẻ các mặt hàng: ví (nam, nữ) thắt lưng (nam, nữ) túi xách (nam, nữ) ..... da cá sấu, da trăn, da đà điểu.... với nhiều mẫu mã, sản phẩm chất lượng cao và giá cả phải chăng.
Chi tiết xem thêm tại Blog: http://viettinhl.blogspot.com/

Dragons

Nguồn: http://codeforces.com

Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all n dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals s.

If Kirito starts duelling with the i-th (1 ≤ i ≤ n) dragon and Kirito's strength is not greater than the dragon's strength x_i, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by y_i.

Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.

Input

The first line contains two space-separated integers s and n (1 ≤ s ≤ 10⁴, 1 ≤ n ≤ 10³). Then n lines follow: the i-th line contains space-separated integers x_i and y_i (1 ≤ x_i ≤ 10⁴, 0 ≤ y_i ≤ 10⁴) — the i-th dragon's strength and the bonus for defeating it.

Output

On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.

Examples

input

2 2
1 99
100 0

output

YES

input

10 1
100 100

output

NO

Note

In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.

In the second sample Kirito's strength is too small to defeat the only dragon and win.

Tóm tắt đề:

_ Để thắng được vòng tiếp theo, Kirito cần hạ được n con rồng. Ban đầu, Kirito có chỉ số sức mạnh là s.

_ Nếu sức mạnh hiện tại của Kirito mạnh hơn sức mạnh x[i] của con rồng, thì Kirito sẽ đánh bại được con rồng và tăng thêm được 1 lượng sức mạnh là y[i]. Ngược lại, Kirito sẽ chết.

_ Hỏi : Kirito có đến được vòng tiếp theo hay không ?

Solution by ĐNK

Taxi

Nguồn:http:/codeforces.com

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of s_i friends (1 ≤ s_i ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) — the number of groups of schoolchildren. The second line contains a sequence of integers s₁, s₂, ..., s_n (1 ≤ s_i ≤ 4). The integers are separated by a space, s_i is the number of children in the i-th group.

Output

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

Examples

input

5
1 2 4 3 3

output

4

input

8
2 3 4 4 2 1 3 1

output

5

Note

In the first test we can sort the children into four cars like this:

·         the third group (consisting of four children),

·         the fourth group (consisting of three children),

·         the fifth group (consisting of three children),

·         the first and the second group (consisting of one and two children, correspondingly).

There are other ways to sort the groups into four cars.

Tóm tắt đề:

_ Có n nhóm học sinh. Nhóm thứ i chứa s[i] học sinh

_ Một chiếc taxi chỉ có tối đa 4 chỗ ngồi.

_ Các học sinh trong cùng 1 nhóm thì lại muốn ngồi chung trong 1 chiếc taxi. Và 1 chiếc taxi có thể chứa nhiều hơn 1 nhóm học sinh.

_ Hỏi : Cần ít nhất bao nhiêu chiếc taxi để chở hết toàn bộ n nhóm học sinh này.

Solution by ĐNK

Football

Nguồn: http://codeforces.com

Petya loves football very much. One day, as he was watching a football match, he was writing the players' current positions on a piece of paper. To simplify the situation he depicted it as a string consisting of zeroes and ones. A zero corresponds to players of one team; a one corresponds to players of another team. If there are at least 7 players of some team standing one after another, then the situation is considered dangerous. For example, the situation 00100110111111101 is dangerous and 11110111011101 is not. You are given the current situation. Determine whether it is dangerous or not.

Input

The first input line contains a non-empty string consisting of characters "0" and "1", which represents players. The length of the string does not exceed 100 characters. There's at least one player from each team present on the field.

Output

Print "YES" if the situation is dangerous. Otherwise, print "NO".

Examples

input

001001

output

NO

input

1000000001

output

YES

Tóm tắt đề:

_ Có N cầu thủ được xếp thành 1 hàng ngang. N cầu thủ này thuộc về 2 đội khác nhau.

_ Một sắp xếp được gọi là “dangerous” nếu như có ít nhất 7 cầu thủ ở đội này đứng đằng sau một cầu thủ ở đội khác.

_ Cho một sắp xếp các chỗ đứng của cầu thủ, hỏi hàng sắp xếp này có “dangerous” hay không?

Solution By ĐNK