| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12138 | too many treasures |
|
| 12674 | Eat candies |
|
| 12678 | Count 1s |
|
Description
Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas accidentally found an undiscovered tomb. He successfully sneaked in without triggering any traps. When he finally got into the treasure room, he found a note that warns tomb raiders about the trap in the treasure room. Osas arranged the note and concluded some rules:
- The treasure room has n treasure crates, each crate has its value. The values are sorted in descending order.
- There are several intervals [l,r] on the note.
- Tomb raiders must loot less than or equal to m treasure crates in the correct interval, where m is a number that Osas have to guess.
- If any tomb raider loot more than m treasure crates or loot any crate that not in the interval, the trap would trigger and kill that tomb raider! Osas doesn't want to die here.
Osas wants these treasures, but he doesn't want to die. Osas wants to know if he pick one interval and guess a number as "m", what is the maximum value he could loot? Osas asks you for help!
Osas will give you the value of every treasure crate and the number he would like to guess, you need to write a program to help him.
Input
The input contains exactly one testcase.
The first line contains two integers n, q. q indicates the amount of queries of (l,r,m).
The next line is the sequence of values of n treasure crates, each seperated by a space.
The next q lines, each line contains exactly three integers l, r, m.
1<=m<=n<=106, 1<=q<=106, 1<=l<=r<=n, m<=r-l+1, the value of every treasure crate won't larger than 105 or smaller than -105. All of the values are integers. Notice that the value could be negative, and Osas can choose nothing.
Note that the sequence index starts from 1. For example: for a sequence "a": "3 4 5 6 7", a[4]=6, a[1]=3.
Output
For each query, output the maximum value Osas could get. Each query holds exactly one line.
Remember to print a '\n' at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You have three different kinds of candies: color red, color green, color blue.
You got three number r, g, b which means the number of candies for each color.
You need to eat exactly two candies each day.
The candies you eat have to be different colors.
Your goal is to find out what's the maximum days that you can eat the candies that qualified for the rules above.
Example:
if r = 7, g = 4, b = 10
You can eat green and blue for 4 days, then you got r = 7, g = 0, b = 6.
Then you can eat red and blue for 6 days, then you got r = 1, g = 0, b = 0.
There's only one red left, you can't have two candies anymore.
The answer will be 10 days.
Input
The input first contains one integer t( 1 <= t <= 10^6) which means the number of testcases.
The following t lines each line contains three integer r, g, b(0 <= r, g, b <= 10^8)
Output
For each testcase print a integer which means the maximum days that you can eat the candies.
Remember to print \n at the end of each output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two number a,b.
You need to calculate how many 1 appear in range a~b(decimal representation).
Example:
Given a = 1, b = 11.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
There're four 1 appear in range 1~11(1, 10, 11).
The answer is 4.
Input
First line contains one integer t(1 <= t <= 10^6) which means the number of testcases.
The following t lines, each line contains two integer a, b( 1 <= a <= b <= 10^6)
Output
For each testcase print only one number which means the number of 1 appear in range a~b.
Remember to print \n at the end of output.