分类：程序学习

【思维】Marjar Cola

Marjar Cola is on sale now! In order to attract more customers, Edward, the boss of Marjar Company, decides to launch a promotion: If a customer returns x empty cola bottles or y cola bottle caps to the company, he can get a full bottle of Marjar Cola for free!

Now, Alice has a empty cola bottles and b cola bottle caps, and she wants to drink as many bottles of cola as possible. Do you know how many full bottles of Marjar Cola she can drink?

Note that a bottle of cola consists of one cola bottle and one bottle cap.

Input
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 100), indicating the number of test cases. For each test case:

The first and only line contains four integers x, y, a, b (1 ≤ x, y, a, b ≤ 100). Their meanings are described above.

Output
For each test case, print one line containing one integer, indicating the number of bottles of cola Alice can drink. If Alice can drink an infinite number of bottles of cola, print “INF” (without the quotes) instead.

Sample Input
2
1 3 1 1
4 3 6 4
Sample Output
INF
4
Hint
For the second test case, Alice has 6 empty bottles and 4 bottle caps in hand. She can return 4 bottles and 3 caps to the company to get 2 full bottles of cola. Then she will have 4 empty bottles and 3 caps in hand. She can return them to the company again and get another 2 full bottles of cola. This time she has 2 bottles and 2 caps in hand, but they are not enough to make the exchange. So the answer is 4.

继续阅读【思维】Marjar Cola

【模拟/字符串】DRM Messages

DRM Encryption is a new kind of encryption. Given an encrypted string (which we’ll call a DRM
message), the decryption process involves three steps: Divide, Rotate and Merge. This process is
described in the following example with the DRM message “EWPGAJRB”:
Divide — First, divide the message in half to “EWPG” and “AJRB”.
Rotate — For each half, calculate its rotation value by summing up the values of each character
(A = 0, B = 1, . . . Z = 25). The rotation value of “EWPG” is 4 + 22 + 15 + 6 = 47. Rotate each
character in “EWPG” 47 positions forward (wrapping from Z to A when necessary) to obtain the
new string “ZRKB”. Following the same process on “AJRB” results in “BKSC”.
Merge — The last step is to combine these new strings (“ZRKB” and “BKSC”) by rotating each character
in the first string by the value of the corresponding character in the second string. For the first
position, rotating ‘Z’ by ‘B’ means moving it forward 1 character, which wraps it around to ‘A’.
Continuing this process for every character results in the final decrypted message, “ABCD”.
Input
The input file contains several test cases, each of them as described below.
The input contains a single DRM message to be decrypted. All characters in the string are uppercase
letters and the string’s length is even and ≤ 15000.
Output
For each test case, display the decrypted DRM message.
Sample Input
EWPGAJRB
UEQBJPJCBUDGBNKCAHXCVERXUCVK
Sample Output
ABCD
ACMECNACONTEST

分析：按照题意模拟，另外使用取模别用减法 继续阅读【模拟/字符串】DRM Messages

【单调栈/dp】Max answer

Describe

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

Input

First line contains an integer n(1≤n≤5*10^5)

Second line contains n integers represent the array a(−10^5≤ai≤10^5)

Output

One line contains an integer represent the answer of the array.

样例输入

5

1 2 3 4 5

样例输出

36

题意
给你一个序列，对于每个连续子区间，有一个价值，等与这个区间和×区间最小值，
求所有子区间的最大价值是多少。

继续阅读【单调栈/dp】Max answer