| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12219 | Uncle Huang Points Tutor |
|
| 12220 | McDonald's fries |
|
Description
Disclaimer: If something described below happened or happens in real world, which is just a coincidence. We will not take any responsibility of any coincidence.
Uncle: I'm an employee of the library and dating master, nickname "Uncle Huang", who are you?
Shiao: Two years tutor experience, straying book boy of second-hand section, "Shiao Tsing".
Uncle: Well, well. Let me test you!
Uncle: In the painting, dragons won't roar, tigers won't howl, little book boy, funny funny!
Shiao: In the article, man is allowed, woman is forbidden, seeking tutor, urgent urgent!
Uncle: Warbler, swallow, emerald, red, prosperous, harmonious, everywhere.
Shiao: Tutor, Shu-shu, urgent, critial, anxious, serious, swimming pool.
Wang Ye: Another distich!
Uncle: See a jerk standing over there.
Shiao: Seek a tutor swimming over the pool.
Uncle: I am hero in the battle field.
Shiao: You are topic master booming the post.
Uncle: Ahhhhh........!
(Inspired by the post 靠北清大7754)
Although uncle Huang loses the distich competition, he is still seeking for a male tutor. He would choose one of those who left comments below his post as his tutor ( and one cannot refuse! ). Because too many people left comments below ( just like Shiao said, he's truly a topic master ), he would pick two numbers "x" and "y", and choose the (xy)-th person that left a comment as his tutor.
Because xy might be too big, so the answer would mod(取模) a number "m", which is the total number of comments of his post.
Uncle Huang is too busy seeking for his true love tutor, he asks you for help, could you help him find out his true love tutor?
- You are given three numbers "x", "y", and "m", you have to calculate the answer of ((xy)%m) .
Hint: Use "Fast Power" method to solve this problem!
Input
The input contains only one line.
The first line contains exactly three numbers "x", "y", and "m", which are described above.
1 <= x <= 1018,, 0 <= y <= 1018, 1 <= m <= 109.
Output
Output one number: (xy)%m .
Remember th print a '\n' at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
I worked at McDonald. My principle of selling fries is:
"ガンニニヤサイバウ ( gan ni nya sai bau )"
Yeah... "ガンニニヤサイバウ". I don't care if deficit of McDonald occurs or not. The fries sold each time are extremely large. Small size to large size, medium size to giant size, large size to another free one, just like give all the fries in the French fries station away.
I still remember, that month, I worked 25 days. The manager came to ask me, they got 26 boxes of French fries of deficit, do you have any clue?
How the hell could I know.
── Unknown McDonald's ex-employee
Every time that employee thinks of that, he/she always wonders why couldn't he/she stuff more fries, which makes him/her feel bad.
The employee finds an old record about importing fries each day. The amount of the imported fries increases day by day.
The employee wonders that whether he/she could left shift the record by a number, and he/she could stuff more and more fries in the first few days. What about the last few days? Who cares.
The employee couldn't wait to imagine how happy he/she would be if getting the chance! He/She would stuff all the fries out! The employee will give you some numbers and ask you how he/she could stuff this much fries.
- You are given a non-decreasing sequence named a and a number k.
- The sequence will left shift (左移) k slots and the first k elements will shift to the end of the sequence. For example: a={1,3,6,8,9}, k=2. After left shifting, new a will be {6,8,9,1,3}.
- Each query has one number f, and you're going to find out the index i such that f <= ai and |f - ai| is the smallest. If there's no such i, output "gan ni nya sai bau". If there are multiple i you could pick, choose the i with the smallest index. Note that this is katakana(片假名), not Chinese or something else.
Input
The first line contains three integers n, k, q.
The second line contains n integers, which indicate the elements of sequence a.
There are q lines below. Each line contains one integer f.
1 <= n, q <= 106, 1 <= ai, f <= 1015, 0 <= k < n.
Output
For each query, output the index i that f <= ai and | f - ai| is the smallest. If there are multiple answers i being the smallest, choose the i with smallest index. If there's no such i, output "gan ni nya sai bau".
Remember to output a '\n' at the end of the output.