| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10554 | Expedition |
|
| 10653 | Anton and currency you all know |
|
| 10663 | Flowers |
|
| 10664 | easy 8 Puzzles |
|
| 10665 | All Pair Shortest Path |
|
| 10666 | Single Source Shortest Path |
|
Description
A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck now leaks one unit of fuel every unit of distance it travels.
To repair the truck, the cows need to drive to the nearest town (no more than 1,000,000 units distant) down a long, winding road. On this road, between the town and the current location of the truck, there are N (1 <= N <= 10,000) fuel stops where the cows can stop to acquire additional fuel (1..100 units at each stop).
The jungle is a dangerous place for humans and is especially dangerous for cows. Therefore, the cows want to make the minimum possible number of stops for fuel on the way to the town. Fortunately, the capacity of the fuel tank on their truck is so large that there is effectively no limit to the amount of fuel it can hold. The truck is currently L units away from the town and has P units of fuel (1 <= P <= 1,000,000).
Determine the minimum number of stops needed to reach the town, or if the cows cannot reach the town at all.
The idea of solving this problem is repeatedly do:
- if we can reach the town without any further more fuel, end
- if not, choose the best available stop(with max amount of fuel and not chosen yet)[Greedy strategy]
Input
* the first line: A single integer, T: the number of testcases
for each testcase:
* Line 1: A single integer, N
* Lines 2..N+1: Each line contains two space-separated integers describing a fuel stop: The first integer is the distance from the town to the stop; the second is the amount of fuel available at that stop.
* Line N+2: Two space-separated integers, L and P
limits :
subtask 1 : (when you pass this subtask, you can get 20 point)
1 <= N <= 10000
Using O(N^2) algorithm is okay!
subtask 2 : (when you pass this subtask, you can get another 20 point)
1 <= N <= 10000
only O(NlgN) algorithm is okay!
Output
* Line 1: A single integer giving the minimum number of fuel stops necessary to reach the town. If it is not possible to reach the town, output -1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Berland, 2016. The exchange rate of currency you all know against the burle has increased so much that to simplify the calculations, its fractional part was neglected and the exchange rate is now assumed to be an integer.
Reliable sources have informed the financier Anton of some information about the exchange rate of currency you all know against the burle for tomorrow. Now Anton knows that tomorrow the exchange rate will be an even number, which can be obtained from the present rate by swapping exactly two distinct digits in it. Of all the possible values that meet these conditions, the exchange rate for tomorrow will be the maximum possible. It is guaranteed that today the exchange rate is an odd positive integer n. Help Anton to determine the exchange rate of currency you all know for tomorrow!
Input
The input includes several testcases and is terminated by EOF(end of file).
The first line of each testcase contains an odd positive integer n — the exchange rate of currency you all know for today. The length of number n's representation is within range from 2 to 105, inclusive. The representation of n doesn't contain any leading zeroes.
Output
For each testcase :
If the information about tomorrow's exchange rate is inconsistent, that is, there is no integer that meets the condition, print - 1.
Otherwise, print the exchange rate of currency you all know against the burle for tomorrow. This should be the maximum possible number of those that are even and that are obtained from today's exchange rate by swapping exactly two digits. Exchange rate representation should not contain leading zeroes.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Original Problem
We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.
But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.
Now Marmot wonders in how many ways he can eat m flowers. As the number of ways could be very large, print it modulo 1000000007 (109 + 7).
Input
Input contains several test cases.
The first line contains two integers t and k (1 ≤ t, k ≤ 10), where t represents the number of test cases.
The next t lines contain an integers m (1 ≤ m ≤ 109), describing the i-th test.
Output
Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat m flowers at dinner modulo 1000000007 (109 + 7).
Note for sample
- For K = 2 and length 1 Marmot can eat (R).
- For K = 2 and length 2 Marmot can eat (RR) and (WW).
- For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).
- For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
一個八數字推盤遊戲由3*3的棋盤組成，每一個格子上都有一個數字(0~8且不重複)，一開始盤面是亂的，
| 1 | 2 | 3 |
| 4 | 0 | 5 |
| 7 | 8 | 6 |
每次操作可以將0與其上.下.左.右的數字互換，經過若干次操作：
step 1 : 0往右與5互換
| 1 | 2 | 3 |
| 4 | 5 | 0 |
| 7 | 8 | 6 |
step 2 : 0往下與6互換
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |
最後將盤面排回
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |
即為正解。
Rody最近沉迷於八數字推盤遊戲當中，但最近要開始期末大爆炸了，Rody不再那麼空閒，因此他決定要先跳過太過困難的題目，等到暑假再來解。
困擾的Rody想要請你幫他鑑定題目的困難度。
Input
input第一行有一整數T(1<=T<=30)，代表底下有T筆測資。
第2~T+1行分別有9個不同的整數(0<=t1,t2,...,t9<=8)，代表一個八數字推盤遊戲。
(註:9個整數以row major方式填入3*3的盤面，如第二組測資 1 2 3 4 0 5 7 8 6 等同於下方示意圖)
| 1 | 2 | 3 |
| 4 | 0 | 5 |
| 7 | 8 | 6 |
Output
對於每組八數字推盤遊戲，若能在14步內完成遊戲，請輸出"You can solve it within x steps."，x為解決該遊戲所需的最少移動次數。
否則，請輸出"You'd better skip this game."
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a directed graph G by adjacency matrix
Find all pair shortest path. Print the answer by a matrix
Input
The first line is an integer T, the number of testcases
For each testcase:
The first line is n , there are n vertices {1,2,...,n}
Below is a matrix Gij denote the distance from vertex i to vertex j
1<=distance of an edge,n<=100
Output
For each testcase
print a matrix M such that Mij is the length of shortest path from i to j
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Single Source Shortest Path
Given a directed graph G by edge list
Find the shortest path from s to t
Input
The first line is an integer T, the number of testcases.
For each testcase:
The first line has 4 integers n,m,s,t : the number of vertices, edges, start, destination
There are m lines below, each represent a directed edge
Each edge has three positive integers v, u, c: an edge from v to u whose cost is c
n<=100000
m<=300000
vertices are indexed from 1 to n, c<=1000
Output
For each testcase print the cost of the shortest path from s to t
If there is no path from s to t, print "OAO"