USACO 2015 - Tháng 1 - Hạng Bạc

Hôm nay, vì thầy cuom1999 có việc bận đột xuất nên lớp A5 sẽ tự học tại lớp. Đức là một học sinh ham chơi, cậu quyết định rủ 5 người bạn thân cùng trốn tiết để đi biển chơi. Biết được ý định này, thầy cuom1999 muốn tạo ra một hệ thống để biết ai đã đi qua cổng trường trong giờ học. Hệ thống của thầy hoạt động như sau:

Xem sân trường là trục tọa độ Oxy, mỗi học sinh được biểu diễn bởi một đoạn thẳng nằm ngang độ dài 1m, được chỉ định bởi tọa độ của điểm bên trái của đoạn thẳng. Ban đầu, các học sinh đang ở thời điểm \(t = 0\). Mỗi học sinh đang di chuyển sang bên phải (theo hướng +Ox) theo một tốc độ nhất định, học sinh \(i\) sẽ tốn \(r[i]\) giây để đi được 1m. Ví dụ, (-2, 1) có \(r = 5\) thể hiện một học sinh tại thời điểm \(t = 0\) có tọa độ từ (-2, 1) tới (-1, 1), đi 1m mất 5 giây.

Để xác định xem ai trốn học, thầy cuom1999 sẽ để máy ảnh tại điểm (0, 0) và hướng máy ảnh dọc theo tia hướng +Oy. Khi có học sinh đi qua cổng trường (tia +Oy), máy ảnh sẽ tự chụp lại. Tuy nhiên, trong ảnh sẽ chỉ xuất hiện học sinh đầu tiên mà máy ảnh thấy mỗi lần chụp. Nghĩa là, một học sinh A không được nhìn thấy nếu có học sinh khác đứng trước suốt quá trình A đi qua tầm nhìn của máy ảnh.

Cho biết vị trí và tốc độ đi của mỗi học sinh. Bạn hãy giúp thầy cuom1999 đếm xem có bao nhiêu học sinh bị chụp ảnh lại nếu thầy sử dụng hệ thống này.

INPUT

• Dòng đầu tiên gồm số nguyên dương \(N\) (\(1 \leq N \leq 50000\))
• \(N\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(x, y, r\), thể hiện học sinh thứ \(i\) có tọa độ điểm bên trái là (\(x, y\)) và tốc độ di chuyển là \(r\) \((-1000 \leq x \leq -1, 1 \leq y, r \leq 10^6)\). Mỗi học sinh sẽ ở có tọa độ \(y\) khác nhau để tránh va chạm nhau.

OUTPUT

Gồm 1 số nguyên là số lượng học sinh bị chụp ảnh lại trong suốt quá trình trốn học (từ thời điểm \(t = 0\)).

VÍ DỤ:

INPUT:

3
-5 100 1
-2 1 3
-3 2 3

OUTPUT:

2

Giải thích: máy ảnh có thể thấy học sinh 2 và 3, nhưng không thể thấy học sinh 1.

Mệt mỏi với kì thi THTQG, Hiếu quyết định bay về quê để nghỉ ngơi. Không may, vì dịch bệnh đang phức tạp nên Hiếu chỉ có thể chọn hãng hàng không Bamboo Air, và các lộ trình của hãng này khá phức tạp.

Bamboo Air có \(N\) máy bay, mỗi chiếc có một lộ trình cụ thể gồm hai hay nhiều thành phố khác nhau. Ví dụ, với lộ trình 1-5-3-8, có 3 chuyến bay. Máy bay xuất phát từ thành phố 1, đến thành phố 5, đến thành phố 3, và hạ cánh tại thành phố 8. Không có thành phố nào xuất hiện nhiều lần trong một lộ trình. Nếu Hiếu chọn đi một lộ trình, Hiếu có thể lên máy bay tại bất kì thành phố nào trong lộ trình và hạ cánh tại một thành phố bất kì khác theo đúng trình tự đi của lộ trình đó. Mỗi lộ trình có một chi phí nhất định, và Hiếu phải trả đúng chi phí đó nếu sử dụng lộ trình này, bất kể số lượng thành phố mà Hiếu đi qua. Nếu Hiếu sử dụng lộ trình này nhiều lần thì cũng phải trả phí mỗi lần sử dụng.

Hiếu muốn tìm cách rẻ nhất để bay từ thành phố Đà Nẵng (thành phố \(A\)) về quê của mình (thành phố \(B\)). Vì vẫn chưa hết buồn sau kì thi THTQG, Hiếu không thể tập trung để tìm cách đi lợi nhất. Bạn hãy giúp Hiếu xác định chi phí nhỏ nhất mà cậu ấy phải trả, đồng thời là số chuyến bay riêng lẻ ít nhất mà Hiếu phải bay để có thể trả đúng chi phí ít nhất đó.

INPUT

• Dòng đầu tiên gồm 3 số \(A, B, N\) (\(1 \leq N \leq 1000\), \(1 \leq A, B \leq 1000\))
• \(2N\) dòng tiếp theo mô tả lộ trình của \(N\) máy bay, mỗi lộ trình gồm 2 dòng. Với mỗi lộ trình \(i\), dòng thứ nhất gồm 2 số \(C, M\) (\(1 \leq C \leq 10^9\), \(1 \leq M \leq 100\)), là giá tiền của lộ trình và số lượng thành phố trong lộ trình đó. Dòng thứ 2 gồm \(M\) số, là danh sách thành phố trong lộ trình \(i\)
• Mỗi thành phố được biểu diễn bởi một số nguyên dương từ \(1\) đến \(1000\).

OUTPUT

Gồm 2 số nguyên dương là chi phí nhỏ nhất và số lượng chuyến bay nhỏ nhất mà Hiếu dùng. Nếu không có cách đi nào thỏa mãn, in "-1 -1"

VÍ DỤ:

INPUT:

3 4 3
3 5
1 2 3 4 5
2 3
3 5 4
1 2
1 5

OUTPUT:

2 2

Quý và Hân đang lên kế hoạch đi chơi với nhau. Đất nước Wibuland nơi 2 bạn đang ở có \(N\) thành phố. Thành phố của 2 bạn hiện tại là thành phố \(1\), và 2 bạn quyết định sẽ bắt xe đến thành phố \(N\) để đi chơi. Không may, vì cả Hân và Quý đang hơi nghèo, nên hai bạn phải đặt 2 chiếc grab xe máy khác nhau để đi đến điểm hẹn.

Wibuland có \(M\) con đường nối các thành phố với nhau. Với mỗi con đường \(u-v\), xe máy chỉ được phép lưu thông nếu \(u < v\), do đó sẽ không thể đi hướng ngược lại (nếu muốn về nhà thì 2 bạn phải nghĩ cách khác, như là đi bộ). 2 chiếc xe grab mà Quý và Hân đặt khi đi trên mỗi đoạn đường có thể sẽ có thời gian đi khác nhau. Ví dụ, với đoạn đường 1-2 Quý sẽ mất 10 phút để đến nơi, nhưng Hân phải mất tận 20 phút. Tuy nhiên với đoạn đường 2-3, Quý sẽ mất 30 phút trong khi Hân chỉ mất 10 phút. Vì cả hai đều không muốn người kia phải đợi mình, Quý và Hân lập ra một lộ trình cho mỗi người để khi cùng xuất phát tại thành phố \(1\), hai người sẽ đến thành phố \(N\) cùng một lúc.

Vì đang háo hức được đi chơi nên cả Quý và Hân đều không thể tập trung nghĩ cách, bạn hãy giúp 2 bạn tính thời gian ngắn nhất để cả 2 có thể đến nơi cùng một lúc.

INPUT

• Dòng đầu tiên gồm 2 số nguyên \(N, M\) (\(2 \leq N \leq 100\), \(1 \leq M \leq \frac{N(N - 1)}{2})\)
• \(M\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(u, v, c, d\), mô tả đoạn đường nối thành phố \(u\) và \(v\), thời gian để Quý đi là \(c\), thời gian Hân đi là \(d\). (\(1 \leq u < v \leq N\), \(1 \leq c, d \leq 100\)).

OUTPUT

In ra 1 dòng duy nhất là thời gian ngắn nhất để Quý và Hân đến điểm hẹn cùng lúc. Nếu không có lộ trình đi thỏa mãn, in ra "IMPOSSIBLE".

VÍ DỤ:

INPUT

3 3
1 3 1 2
1 2 1 2
2 3 1 2

OUTPUT

2