| Problem description | | Progress |
|
Темы:
Remains
Write a program that, in some sequence of integers, finds the subsequence of the smallest length whose sum of elements is a number ending in 6 or more zeros (divisible without remainder by 1000000).
The first input line contains one integer N (2 ≤ N ≤ 100000). The second input line contains N integers in the range from 1 to 109 separated by spaces.
Output two integers – the number of elements in the subsequence and the number of its first element. If there are several variants of such a subsequence with the smallest length, print the subsequence with the smallest number of the first element. If no such subsequence exists – print one number –1.
|
Enter |
Output |
|
6
1 2 701000 299000 1000 999000
|
2 3
|
3
1 2 3
|
-1 |
| |
![]()
|
|
Темы:
Remains
Into how many fives and triples can a number be expanded so that the number of expansions is minimal.
Input
The input is a single natural number N (\(7 < N < 1000\)).
Imprint
Print two space-separated integers: the number of fives and the number of threes.
Examples
| # |
Input |
Output |
| 1 |
8 |
1 1 |
| 2 |
11 |
1 2 |
| 3 |
15 |
3 0 |
| |
![]()
|
|
Темы:
Remains
Fifth grader Lenya recently read an article about Fibonacci numbers.
The Fibonacci numbers are the numerical sequence F1 , F2 , ..., Fn , ... , which is arranged as follows thus: F1 = 1 , F2 = 2 , and each next number is calculated as the sum of the previous two: if i ≥ 3 , then F i = Fi - 1 + Fi - 2 . The Fibonacci sequence thus begins with the numbers 1, 2, 3, 5, 8, 13, 21, ... .
Today Lenya is studying Fibonacci numbers with numbers from L to R, inclusive. Since Lenya loves the number 3 very much, he wondered how many Fibonacci numbers among those that he studies today are divisible by 3. For example, if L = 3 and R = 7 , then Lenya will study the numbers F3 = 3 , F4 = 5 , F5 = 8 , F6 =&thinsp ;13 and F7 = 21 . Among them, two numbers are divisible by 3: F3 = 3 and F7 = 21 .
Write a program that will help Lena find the answer to his question.
Input
The first line of the input contains the number L , and the second — number R ( 1 ≤ L ≤ R ≤ 105 ).
Imprint
Print a single number — the number of Fibonacci numbers with numbers from L to R , inclusive, that are divisible by 3.
| |
![]()
|
|
Темы:
Remains
Arithmetic Algorithms
At the children's holiday, the children led round dances. Once the music had finished playing, the children were still standing in the circle. Then Lena remembered that her parents had given her a box of k Wilky May sweets. Lena is not greedy, so she decided to give all her sweets to friends from the round dance. Lena knows that some of her friends have a sweet tooth and some don't. Those with a sweet tooth take two candies from the box if there are at least two candies in the box, otherwise they take one. Lena's other friends always take exactly one candy from the box.
To start handing out sweets, Lena left the round dance, after which n of her friends remained in the round dance. To make it easier to hand out sweets, Lena assigned a number to each friend in the round dance, in clockwise order, starting with her best friend Roma, who received number 1.
Lena gave the box to a friend who received number l, after which each friend of Lena, starting with friend number l, took sweets from the box and passed the box to the next friend in clockwise order. After the friend with the number r took the candies, there were no candies left in the box. Please note that it is possible that some of Lena's friends took candies from the box several times, that is, the box could go several full circles in a round dance.
Lena does not know which of her friends have a sweet tooth, but she is interested in how many of her friends can have a sweet tooth. If such a situation could not happen, and Lena made a mistake in her observations, tell her about it.
Input
A single line contains four integers n, l, r, k (1 ≤ n, k ≤ 1011 , 1 ≤ l, r ≤ n ) — the number of children in the round dance, the number of the friend to whom Lena gave the box of chocolates, the number of the friend who took the last candy, and the number of candies in the box, respectively.
Imprint
Print a single integer — the maximum possible number of sweet teeth among Lena's friends or « -1 " (without quotes) if Lena made a mistake in her observations.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4 1 4 12 |
2 |
Any two friends can have a sweet tooth, in which case each friend will receive a box of chocolates twice and the last person to take the candy will be the fourth person. |
| 2 |
5 3 4 10 |
3 |
Any three friends can be Sweet Tooth, except for the friend in third place. |
| 3 |
10 5 5 1 |
10 |
Only one friend will take one candy, but he can have a sweet tooth, he just can't take two candies. Everyone else in the circle can also have a sweet tooth, but they can't take a single piece of candy. |
| 4 |
5 4 5 6 |
-1 |
Lena made a mistake and this situation could not have happened. |
| |
![]()
|
|
Темы:
Remains
USE - computational tasks
Anna Nikolaevna has N boxes of sweets. The i-th box contains Ai the number of sweets. Anna Nikolaevna takes sweets from several consecutive boxes and evenly distributes them < code>M children. Find the number of pairs (l, r) that satisfy the following conditions:
- l and r are integers and satisfy the condition 1<=l<=r<=N;
- Al + Al+1 +< /code> ... + Ar is divisible by M.
Input
The program receives two lines as input. The first line contains two integers N (1<=N<=105) and M (2<=M<=109). The second line contains N numbers Ai (1<=Ai<=109< /sup>, 1<=i<=N).
Imprint
Print the number of pairs (l, r) that satisfy the conditions. Note that the number may not correspond to a 32-bit integer type.
Examples
| # |
Input |
Output |
| 1 |
3 2
4 1 5
| 3 |
| 2 |
13 17
29 7 5 7 9 51 7 13 8 55 42 9 81
| 6 |
| |
![]()
|
|
Темы:
Prefix sums(minimums, ...)
Fermat's Little Theorem
Remains
Fast exponentiation
Fomin's gang consists of n groups, each of which has ai people. q raids are planned. The i-th raid will include exactly one robber from each group whose number lies in the segment \([l_i, r_i]\).
Melekhov is sad, so for each raid he decided to calculate the number of possible units modulo \(10^9 + 7\). However, Gregory is constantly thinking about the meaning of life and searching for the truth, so he cannot concentrate on calculations and asks you for help.
Input
The first line contains the number n (\(1 <= n <= 10^5\)) – the number of groups in Fomin's gang.
The second line contains n natural numbers ai (\(1 <= a_i < = 10^6\)) – the number of people in the i-th group.
The third line contains the number q – number of raids.
The following are q lines, each containing two numbers – li and ri (\(1 <= l_i <= r_i <= n\)) – numbers of groups participating in i-th raid.
Imprint
Print q numbers, each on a separate line – response to the task.
Examples
| # |
Input |
Output |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |
| |
![]()
|