Сумма последовательности

@Temchik16 · Регистрация: 15.10.2019

Студворк — интернет-сервис помощи студентам

Гертруда имеет n тарелок. И хочет разбить их все. По одной. Но тарелки бьются очень звонко. Она опасается, что повредит слух.

Известно, что сила звона первой разбитой тарелки будет равна a1. Сила звона каждой последующей разбитой тарелки будет в b раз больше силы звона предыдущей. То есть сила звона i-ой (i>1) разбитой тарелки будет равна ai=ai−1⋅b.

Гертруда знает максимальное суммарное значение сил звона MAX, которое могут выдержать её уши, и желает максимально насладиться звуками бьющейся посуды.

Помогите Гертруде, найдите максимальное количество тарелок, которые она может разбить, не повредив слух. И побыстрее.

Формат входных данных

В первой строке вводятся четыре целых числа n, a1, b, MAX (1≤n,MAX≤10^1000,1≤a1,b≤10).

Формат выходных данных

Выведите максимальное количество тарелок.

Пояснение к примеру

Если Гертруда разобьёт одну тарелку, то суммарное значение сил звона будет равно a1=1.

Если разобьёт две тарелки, то суммарное значение будет равно a1+a2=1+2=3.

Если разобьёт три, то – a1+a2+a3=1+2+4=7.

Sample Input:
10 1 2 4

Sample Output:
2

Напишите программу. Тестируется через stdin → stdout
Time Limit: 3 секунды

@zayycev22 · 16.10.2019, 13:06

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <math.h>
using namespace std;
 
int main() {
int a, b;
long long n, m, k;
cin >> n >> a >> b >> m;
 
if(b==1)
k=m/a;
else
k = (long long)(log(m*(b-1)/a + 1)/log(b));
if (n<k) k=n;
cout << k;
 
return 0;
}

Добавлено через 2 минуты

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
strr = input()
strr = strr.split(' ')
n = int(strr[0])
a1 = int(strr[1])
b = int(strr[2])
maxx = int(strr[3])
 
k = 0 #макс, кол-во тарелок
 
while maxx > 0:
    if maxx - a1 >= 0:
        k+= 1
    maxx -= a1
    a1 *= b
 
if k > n:
    k = n
 
print(k)

@lawers1 · 17.10.2019, 12:21

Никто случайно не сможет подсказать как можно ускорить выполнение этого кода?

@Alli_Lupin · 17.10.2019, 12:36

lawers1, переписать на c++

@lawers1 · 17.10.2019, 12:42

Alli_Lupin, Вы не совсем поняли вопрос, это задача с олимпиады и там для python ограничения по времени выполнения 3 секунды; С++ 1 секунда

@Alli_Lupin · 17.10.2019, 14:06

lawers1, и эта задача не выполняется за 3 секунды? А за сколько выполняется?

@lawers1 · 17.10.2019, 14:17

точное время не знаю, знаю только что больше 3, но в программе для тестирование
Формат входных данных

В первой строке вводятся четыре целых числа n, a1, b, MAX (1≤n,MAX≤101000,1≤a1,b≤10).
а так я уже сделал свой код

Python
1
2
3
4
5
6
7
8
9
10
11
12
n, a ,b,mx =map(int, input().split())
if b==1:
    print(min(n,mx//a))
else:
    cnt = 0
    for ans in range (n + 1):
        cnt+=a
        a=a*b
        if cnt>mx:
            print(ans)
            exit()
    print(n)

@Alli_Lupin · 17.10.2019, 14:57

lawers1, вообще, в python скорость сильно зависит от интерпретатора. Одно дело запускать код через python, другое - через pypy.

@ioprst · 17.10.2019, 14:57

lawers1, почему exit(), а не break?

@lawers1 · 17.10.2019, 15:14

Потому что если будет break то в ответ пойдет значение из цикла и значения n (в двух разных строчках), а если exit, то программа закрывается и последняя строчка(print(n)) выполняться не будет(в результате одна строчка ответа), а так как на олимпиаде проверку кода выполняет программа то можно не обращать внимания как с этим кодом работать человеку, именно по-этому exit

@ioprst · 17.10.2019, 15:31

lawers1, а если написать n=ans перед break?

@Arsegg · 17.10.2019, 16:57

Сообщение от Temchik16

1≤n,MAX≤10^1000

Тут чистая математика, перебором не отделаешься.

Добавлено через 20 минут
Обычный бинарный поиск по ответу:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n, a1, b, MAX = map(int, input().split())
 
 
def s(k):
    return a1 * (1 - b ** k) // (1 - b)
 
 
l, r = -1, n
while l + 1 < r:
    m = (l + r) // 2
    if s(m) <= MAX:
        l = m
    else:
        r = m
print(l)

@lawers1 · 17.10.2019, 22:13

ioprst, как по мне это лишнее усложнение, а также повторюсь еще раз эта задача, которую мы сейчас обсуждаем была на олимпиаде НТИ которая только сегодня закончилась и в вашем варианте мы все равно получим два ответа, только уже одинаковых и именно благодаря этому второму ответу получим 0 баллов за правильно решенную задачу

Добавлено через 2 минуты
Arsegg, А вы смотрели среднее время выполнения алгоритма?

@Arsegg · 17.10.2019, 22:16

lawers1, логарифм

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@Temchik16 0 / 0 / 0 Регистрация: 15.10.2019 Сообщений: 7

	Сумма последовательности 15.10.2019, 16:12. Показов 5571. Ответов 13 Метки python 3, задача (Все метки) Гертруда имеет n тарелок. И хочет разбить их все. По одной. Но тарелки бьются очень звонко. Она опасается, что повредит слух. Известно, что сила звона первой разбитой тарелки будет равна a1. Сила звона каждой последующей разбитой тарелки будет в b раз больше силы звона предыдущей. То есть сила звона i-ой (i>1) разбитой тарелки будет равна ai=ai−1⋅b. Гертруда знает максимальное суммарное значение сил звона MAX, которое могут выдержать её уши, и желает максимально насладиться звуками бьющейся посуды. Помогите Гертруде, найдите максимальное количество тарелок, которые она может разбить, не повредив слух. И побыстрее. Формат входных данных В первой строке вводятся четыре целых числа n, a1, b, MAX (1≤n,MAX≤10^1000,1≤a1,b≤10). Формат выходных данных Выведите максимальное количество тарелок. Пояснение к примеру Если Гертруда разобьёт одну тарелку, то суммарное значение сил звона будет равно a1=1. Если разобьёт две тарелки, то суммарное значение будет равно a1+a2=1+2=3. Если разобьёт три, то – a1+a2+a3=1+2+4=7. Sample Input: 10 1 2 4 Sample Output: 2 Напишите программу. Тестируется через stdin → stdout Time Limit: 3 секунды 0

@lawers1 0 / 0 / 0 Регистрация: 17.10.2019 Сообщений: 21
	17.10.2019, 12:21
	Никто случайно не сможет подсказать как можно ускорить выполнение этого кода? 0

@Alli_Lupin 5037 / 1064 / 149 Регистрация: 29.01.2013 Сообщений: 6,232
	17.10.2019, 12:36
	lawers1, переписать на c++ 0

@lawers1 0 / 0 / 0 Регистрация: 17.10.2019 Сообщений: 21
	17.10.2019, 12:42
	Alli_Lupin, Вы не совсем поняли вопрос, это задача с олимпиады и там для python ограничения по времени выполнения 3 секунды; С++ 1 секунда 0

@Alli_Lupin 5037 / 1064 / 149 Регистрация: 29.01.2013 Сообщений: 6,232
	17.10.2019, 14:06
	lawers1, и эта задача не выполняется за 3 секунды? А за сколько выполняется? 0

@Alli_Lupin 5037 / 1064 / 149 Регистрация: 29.01.2013 Сообщений: 6,232
	17.10.2019, 14:57
	lawers1, вообще, в python скорость сильно зависит от интерпретатора. Одно дело запускать код через python, другое - через pypy. 0

@ioprst 1303 / 843 / 409 Регистрация: 12.03.2018 Сообщений: 2,305
	17.10.2019, 14:57
	lawers1, почему exit(), а не break? 0

@lawers1 0 / 0 / 0 Регистрация: 17.10.2019 Сообщений: 21
	17.10.2019, 15:14
	Потому что если будет break то в ответ пойдет значение из цикла и значения n (в двух разных строчках), а если exit, то программа закрывается и последняя строчка(print(n)) выполняться не будет(в результате одна строчка ответа), а так как на олимпиаде проверку кода выполняет программа то можно не обращать внимания как с этим кодом работать человеку, именно по-этому exit 0

@ioprst 1303 / 843 / 409 Регистрация: 12.03.2018 Сообщений: 2,305
	17.10.2019, 15:31
	lawers1, а если написать n=ans перед break? 0

@lawers1 0 / 0 / 0 Регистрация: 17.10.2019 Сообщений: 21
	17.10.2019, 22:13
	ioprst, как по мне это лишнее усложнение, а также повторюсь еще раз эта задача, которую мы сейчас обсуждаем была на олимпиаде НТИ которая только сегодня закончилась и в вашем варианте мы все равно получим два ответа, только уже одинаковых и именно благодаря этому второму ответу получим 0 баллов за правильно решенную задачу Добавлено через 2 минуты Arsegg, А вы смотрели среднее время выполнения алгоритма? 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	17.10.2019, 22:16
	lawers1, логарифм 0

Опции темы

Сумма последовательности

Решение