Как ускорить алгоритм - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Листинг программы
  1. #include<stdio.h>
  2. min(int x,int y)
  3. {
  4. if(x<y) return x;
  5. else return y;
  6. }
  7. main()
  8. {
  9. int N,x,y,time,l,r,mid;
  10. scanf("%d%d%d",&N,&x,&y);
  11. N--;
  12. time=min(x,y);
  13. if(N>0)
  14. {
  15. l=x;
  16. r=min(x,y)*N;
  17. while(l+1<r)
  18. {
  19. mid=(l+r)/2;
  20. if(N<= mid/x + mid/y) r=mid;
  21. else l=mid;
  22. }
  23. printf("%d",time+r);
  24. }
  25. else printf("%d",time);
  26. }
Как можно ускорить ? на одном тесте чуть выпадает по времени.

Решение задачи: «Как ускорить алгоритм»

textual
Листинг программы
  1. #include<stdio.h>
  2. int main()
  3. {
  4.     int N, x, y,time,l,r,mid;
  5.     scanf("%d%d%d",&N,&x,&y);
  6.     N--;
  7.     time= x < y ? x : y;
  8.     if(N>0){
  9.         l=x;
  10.         r = time * N;
  11.         while(l+1<r){
  12.             mid=(l+r)/2;
  13.             if(N<= mid/x + mid/y)
  14.                 r=mid;
  15.             else
  16.                 l=mid;
  17.         }
  18.         printf("%d",time+r);
  19.     }
  20.     else printf("%d",time);
  21. }

Объяснение кода листинга программы

В этом коде:

  1. Сначала объявляются переменные: N, x, y, time, l, r, mid.
  2. Затем с помощью функции scanf() вводятся значения для переменных N, x, y.
  3. Переменная N уменьшается на единицу, поскольку ввод начинается с 1.
  4. Переменная time приводится к типу int и присваивается значение x или y, в зависимости от того, что меньше.
  5. Если N больше нуля, то выполняются следующие действия: 5.1. Переменная l присваивается значение x. 5.2. Переменная r вычисляется как произведение time и N. 5.3. В цикле while(l+1<r) выполняются следующие действия: 5.3.1. Вычисляется значение mid как средний элемент между l и r. 5.3.2. Если N меньше или равно (mid/x + mid/y), то значение r присваивается mid. 5.3.3. Если N больше (mid/x + mid/y), то значение l присваивается mid. 5.3.4. Цикл while выполняется до тех пор, пока l+1 меньше r. 5.4. После цикла while выводится значение time, увеличенное на r.
  6. Если N равно или меньше нуля, то выводится только значение time. Список действий в коде:
  7. Объявление переменных.
  8. Ввод значений для переменных N, x, y.
  9. Уменьшение значения N на единицу.
  10. Присваивание переменной time значения x или y.
  11. Проверка условия N больше нуля.
  12. Присваивание переменной l значения x.
  13. Вычисление значения переменной r как произведение time и N.
  14. Цикл while для вычисления значения l и r.
  15. Вычисление значения переменной mid как средний элемент между l и r.
  16. Проверка условия N меньше или равно (mid/x + mid/y).
  17. Присваивание переменной r значения mid, если условие в п.10 выполняется.
  18. Присваивание переменной l значения mid, если условие в п.10 не выполняется.
  19. Повторение шагов 8-12 до тех пор, пока l+1 меньше r.
  20. Вывод значения time, увеличенного на r.
  21. Проверка условия N меньше или равно нулю.
  22. Вывод значения time.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 3.417 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы