| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13262 | Domo: Food please! |
|
| 13291 | KONODIODA |
|
Description
Domo is a brilliant dog. When he feels full, he will be happy.
Every day, he gets food from his breeder with a certain rule as follow:
f(n) = f(n - 1) + f(n - 3), if n > 3, on which f(N) describes the food Domo can get on the N-th day.
One day, Domo realizes that if he stores these foods for days, it will be lots of food that he can eat all of them at once to prevent from hungry!
Given the food that Domo can get from the first day to the third day and an integer P, please find that on which day the total of food that Domo gets will equal or greater than P.
For example (refer sample I/O):
For the first test case, we accumulate 10 foods on day 4 (1, 2, 3, 4 foods on day 1 to day 4, respectively).
For the second test case, we accumulate 7 foods on day 2.
If Domo can not prevent from being hungry, he will lay on the sofa so that you can't find a place to sit.
Input
The first line contains an integer T (1 ≤ T ≤ 10) - the number of tasks you need to solve.
For the following T line, each line contains four integer numbers f(1), f(2), f(3), and P.
(1 ≤ f(1), f(2), f(3) ≤ 1000, 1 ≤ P ≤ 108)
Output
For each task case, output how many days Domo needs to get a certain amount of food, then print a newline after every task.
Note that it's guaranteed that the expected output on each task will not exceed 100!
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Dio, an evil vampire, does all kinds of evil and nobody can fight against him.
However, there's a brave man, JoJo, standing out and using all his ability to defeat him.
Everyone appreciate JoJo's great achievement and the world becomes safe and peace again.
Unfortunately, since Dio is a vampire, he revives himself again and tries to make more chaos......
We have known that there is a star-shaped birthmark on Dio's neck. To make sure that Dio is not able to enter our country, in the airport, we will use a special technique to scan a part of the visitors' skin and transfer the raw image to gray scale (0-255, 0 means black and 255 means white).
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the following condition will be satisfied:
(1) A[X][j]=255, for all 0<=j<N (The values in the Xth row are all 255)
(2) A[i][Y]=255, for all 0<=i<N (The values in the Yth column are all 255)
(3)
A[X+i][Y+i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N
A[X+i][Y-i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N
(The values of two diagonals from the centers are all 255)
For example, a star looks like:
In this problem, given T square matrices wth size N, you are asked to find out how many stars in each matrix respectively.
Hint.
If you cannot pass all the testcases, you can try to use extra arrays to record some infomation when you read the input data.
By doing so, you can immediately determine whether a point is a star.
Input
There are three parts of the input:
(1) The number of testcases, T. 1<=T<=1000
(2) The size of the square matrices, N. 1<=N<=2048
(3) T N*N matrices separated by a newline character. 0<=The values in the matrices<=255.
Output
The number of stars in each matrix.
Note that you need to print "\n" in the end of each answer.