| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11131 | Transition probability |
|
| 11158 | Robot in maze |
|
| 11160 | GCD and LCM |
|
| 11166 | Simple integer sorting |
|
Description
Bob is a businessman. He always stays at city A or city B.
Assume Bob stays at city A today , and we can use a transition matrix P to infer the probability of at which city will Bob stays tomorrow.
e.g.
Let VnT = [ va , vb ]Vn is a 2 by 1 column vector.
va denotes the probability that Bob stays at city A on n-th day,
vb denotes the probability that Bob stay at city B on n-th day.
After 1 day, the probability should be represented as Vn+1 , where Vn+1 = P * Vn.
P is a 2 by 2 square matrix, representing the transition probability:
P = ┌ p1 p2 ┐
└ p3 p4 ┘
As time passes, the probability of Bob staying at city A will decrease.
After n days, the probability of Bob staying at city A will smaller than or equal to a target value T.
The question is :
Suppose that Bob stays at city A today ( va = 1 , vb = 0)
How many days do we need to make va smaller than or equal to the target value T ?
Namely , n = ?
Note :
The test case will make va monotonically decrease .
助教出的測資一定會讓 va 隨著時間增加而逐漸遞減
Input
There are multiple testcases in the input.
The first line contains a integer N, indicating the number of testcases.
You can use this format in your code:
int i , N;
scanf("%d",&N);
for(i=0;i<N;i++){
// your code to deal with each testcase
}
The following lines are testcases.
For each testcase, there are 5 floating points in a line.
The 1st ~ 4th floating points (p1, p2, p3, p4) are the elements in trasition matrix P.
The 5th floating point is the target value T.
Output
For each testcase.
Output integer n that tell us how many days should we take to reach the target probability.
And add a '\n' at the end of each output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
小智在火箭隊的地下基地裡遇到了迷宮.
迷宮裡每個 entry 上都有東南西北的方向, 表示要往哪個方向移動到下一個 entry.
那麼給定小智走進迷宮的起始位置, 小智走迷宮會有兩種狀況:
1. 跟著每個 entry 的方向走, 最後走出迷宮.
2. 跟著每個 entry 的方向走, 最後一直在裡面兜圈子.
假設小智站在迷宮北方選擇一個 column 走進迷宮,
請問小智最後有沒有走出迷宮?
如果有, 請印出小智走過 N 個 entry.
如果沒有, 請印出小智走過 A 個 entry 後踏入循環路線, 並印出循環路線的總長為 B 個 entry.
例如:
Grid1: N為10
Grid2: A為3, B為8
Hint:
1. 假設讀進來 map 大小為 (row, col), 可以開一個大小為 (row+2, col+2) 的 map, 外面一圈填上 -1, 裡面放讀到的 map.
這樣有助於判斷什麼時候走到地圖外 (走到 -1 就是走到原本的地圖外)
2. 可以印出地圖檢查自己每一步有沒有走對, 或檢查讀地圖有沒有讀對
3. 另外開一個 (row+2, col+2) 的 array 裡面都是 0, 當走到某個位置 (x, y) 就在 array 的 (x, y) 位置紀錄目前已經走過幾個 entry.
這樣有助於判斷循環路線有多長, 因為只要遇到 array 裡不是 0 的地方就表示以下兩點皆成立:
(1) 這個位置走過了
(2) 這個位置是循環路線的起點, 把你現在走過的 entry 數減去這個位置的 entry 數能算出循環路線的長度
Input
Grid的row數 Grid的column數 小智從哪個column走進迷宮
迷宮
註1: 迷宮大小不超過10x10, 最小為2x2
註2: 每次只會有1筆測資
Output
N
或
A B
註: 最後不需加上換行
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given three positive integers x, y, and z, compute their greatest common divisor (GCD) and least common multiple (LCM).
Input
The first line contains a positive integer N, which indicates the number of test cases in each input.
In the next N lines, each line contains three positive integer x, y, z.
Level 1: x, y, z < 10
Level 2: x, y, z < 10^2
Level 3: x, y, z < 10^3
Level 4: x, y, z < 10^4
Output
For each test case, output the GCD and LCM of x, y, and z in a line.
Note that you have to add '\n' at the end of output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given some integers, please list them in increasing order.
Input
First line is an integer T (T <= 20) followed by T test cases.
Each test case consists of two lines. First line is an integer n (n <= 104), and second line contains n integers V1, V2, ..., Vn. (-231< Vi < 231-1 for 1 <= i <= n )
Output
For each test case, list a line of numbers from the smallest one to the largest one ending with '\n'. Two adjacent numbers in one line should be separated by a whitespace.