Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.51/88: Рейтинг темы: голосов - 88, средняя оценка - 4.51
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256

Найти минимальное время, необходимое для получения N копий одного документа на двух ксероксах

30.08.2015, 14:16. Показов 18420. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый день, нашёл задачку, нужно решить её методом бинарного поиска ( если будут другие варианты, то тоже спасибо ). Вот сама задачка:

Кликните здесь для просмотра всего текста
Секретарша Ирочка сегодня опоздала на работу и ей срочно нужно успеть к обеду сделать N копий одного документа. В ее распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y секунд. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ей выяснить, какое минимальное время для этого потребуется.

Входные данные

Во входном файле INPUT.TXT записаны три натуральных числа N, x и y, разделенные пробелом (1 ≤ N ≤ 2∙10^8, 1 ≤ x, y ≤ 10).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – минимальное время в секундах, необходимое для получения N копий.


Пробовал методом бинарного поиска и вот к чему пришёл:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
int validNumber();
int BinarySearch(int x, int y, int N);
int main()
{
    int N, x, y;
    cin >> N >> x >> y;
    cout << BinarySearch(x, y, N) << endl;
}
int BinarySearch(int x, int y, int N)
{
    int mid, right, left;
    left = 1;
    right = (x*N) + (y*N);
    while (right - left > 1)
    {
        mid = left + (right - left) / 2;
        if ( validNumber() == 1)
            right = mid;
        else
            left = mid;
    }
    return mid;
    int validNumber()
    {
        if () // Не знаю какое условие взять.
            
 
 
    }
 
}
Не знаю, какое условие взять для бинарного поиска, подскажите, спасибо!
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
30.08.2015, 14:16
Ответы с готовыми решениями:

Графы, найти минимальное время, необходимое для выполнения всех задач
Граф представлен в виде списка смежных. Есть множество задач T1, T2, …, Tn, для выполнения которых необходимо время t1, t2, …, tn...

Найти минимальное время копирования на 2-х ксероксах
Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее...

Как определить минимальное необходимое время для отработки запускаемого bat файла функцией ShellExecute()?
Всем привет! Столкнулся недавно с интересной проблемой. Есть код на Delphi7: // запускаем bat файл из каталога с программой ...

7
196 / 197 / 120
Регистрация: 27.05.2011
Сообщений: 545
30.08.2015, 19:36
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <algorithm>
#include <iostream>
 
int main() {
    using namespace std;
    int N, x, y;
    cin >> N >> x >> y;
    int t = 0;
 
    // бежим к самому быстрому ксероксу и делаем первую копию
    t += min(x, y);
 
    // запустили медленный ксерокс
    int slower = max(x, y);
 
    // имитурем течение времени, t идёт шагами по min(x, y)
    for (int i = 1; i < N; i++) {
        // медленный ксерокс уже напечатал какую-то часть документа
        slower -= min(x, y);
 
        // если медленный ксерокс уже напечатал документ
        if (slower <= 0) {
            // то засчитываем его
            i++;
            // и отправляем ещё один на печать
            slower = max(x, y);
        }
 
        t += min(x, y);
    }
 
    cout << t << endl;
}
0
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256
30.08.2015, 20:41  [ТС]
mymedia, Где-то ошибка
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
30.08.2015, 20:45
Лучший ответ Сообщение было отмечено Melvil как решение

Решение

accepted
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/////////////////////////////////////////////////////////////////////////////////////////
/*
 Секретарша Ирочка сегодня опоздала на работу и ей срочно нужно успеть к обеду сделать 
 N копий одного документа. В ее распоряжении имеются два ксерокса, один из которых копирует 
 лист за х секунд, а другой – за y секунд. (Разрешается использовать как один ксерокс, так 
 и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ей 
 выяснить, какое минимальное время для этого потребуется.
Входные данные
 
Во входном файле INPUT.TXT записаны три натуральных числа N, x и y, разделенные пробелом 
(1 ≤ N ≤ 2∙108, 1 ≤ x, y ≤ 10).
Выходные данные
 
В выходной файл OUTPUT.TXT выведите одно число – минимальное время в секундах, 
необходимое для получения N копий.
Примеры
№ INPUT.TXT   OUTPUT.TXT
1   4 1 1   3
2   5 1 2   4
*/
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
typedef long long   T_int;
/////////////////////////////////////////////////////////////////////////////////////////
bool    time_is_valid
    (
        T_int   t,
        T_int   N,
        T_int   x,
        T_int   y
    )
{
    return  t / x + (t - x) / y     >=   N;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_int   f
    (
        T_int   N,
        T_int   x,
        T_int   y
    )
{
    T_int   R   =   1;
 
    while   (
                !time_is_valid
                    (
                        R,
                        N,
                        x,
                        y
                    )
            )
    {
        R   *=  2;
    }
    
    T_int   L   =   R / 2;
 
    while( R - L > 1 )
    {
        T_int   M   =   (L + R) / 2;
 
        if  (
                !time_is_valid
                    (
                        M,
                        N,
                        x,
                        y
                    )
            )
        {
            L   =   M;
        }
        else
        {
            R   =   M;
        }
    }//while
 
    return  R;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_int   N   =   0;
    T_int   x   =   0;
    T_int   y   =   0;
 
    std::cin    >>  N
                >>  x
                >>  y;
 
    if( x > y )
    {
        std::swap( x, y );
    }
 
    std::cout   <<  f( N, x, y )
                <<  std::endl;
 
    system("pause");
}
0
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256
30.08.2015, 23:21  [ТС]
Mr.X, Я всё сделал также, но вот не могу понять одного, как вы выводите подобные формулы?:

C++
1
return  (t / x) + ( (t - x) / y) >= N;
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
30.08.2015, 23:28
Цитата Сообщение от Melvil Посмотреть сообщение
не могу понять одного, как вы выводите подобные формулы?:
C++
1
return (t / x) + ( (t - x) / y) >= N;
Ну, x у нас время печати более быстрого ксерокса, первую копию на нем печатаем. Это означает, что он работает весь отрезок времени t, а второй - (t - x). В результате первый ксерокс напечатает (t / x) копий, а второй - (t - x) / y.
1
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256
30.08.2015, 23:56  [ТС]
Mr.X, Спасибо, теперь всё ясно.
0
0 / 0 / 0
Регистрация: 28.02.2019
Сообщений: 6
20.04.2019, 21:07
XML
1
[XML][XML][XML][XML][XML][XML][CSS][CSS][CSS][CSS][CSS][CSS][CSS][PYTHON][PYTHON][PYTHON][CPPQT][CPPQT][CPPQT]:-|[/CPPQT][/CPPQT][/CPPQT][/PYTHON][/PYTHON][/PYTHON][/CSS][/CSS][/CSS][/CSS][/CSS][/CSS][/CSS]
[/XML][/XML][/XML][/XML][/XML][/XML][/PLSQL]
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
20.04.2019, 21:07
Помогаю со студенческими работами здесь

Разное время получения сообщения на двух компьютерах в оутлук 2010 с одного адреса
В двух разных кабинетах настроен оутлук 2010 на одинаковый адрес электронной почты. Письма на оба приходят одинаково, но вот время...

Найти минимальное число монет достоинством в 50, 10, 5, и 1 копейку, необходимое для представения некоторой суммы
Найти минимальное число монет достоинством в 50, 10, 5, и 1 копейку, необходимое для представения некоторой суммы, меньшей 1-го рубля. ...

HP 1320 - при отправки несколько копий одного документа на печать печатается только одна копия
Тема следующая: есть принтер HP 1320, подключенный к компу напрямую и расшаренный на 3 ПК. Со всех ПК все отлично печатает, отсылает на...

Определить число членов ряда, необходимое для получения приближенного значения
Задание:Составить программу, которая для каждого значения аргумента х от начального хн до конечного хк с шагом х выполняет следующие...

Определить минимальное количество купюр, необходимое для покупки
Часто граждане пытаются выяснить, насколько богатыми являются депутаты. Некоторые верят, что материальное положение отдельных депутатов...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru