2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 48
1

Вывести либо одно число c – длину стороны квадрата, либо 0, если квадрат не существует...

06.12.2018, 15:02. Показов 6887. Ответов 24
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вот задача:
Кликните здесь для просмотра всего текста

Поля
(Время: 1 сек. Память: 16 Мб Сложность: 16%)

Геннадий учится в сельской школе и мечтает стать агрономом. На уроке геометрии Геннадий познакомился с новой фигурой – прямоугольником. Освоив вычисление площади прямоугольника, Гена подумал о том, что квадратные поля гораздо удобнее, нежели прямоугольные. Поразмыслив еще немного, Гена столкнулся с интересной задачей: существует ли такое квадратное поле, у которого площадь в точности равна площади заданного поля прямоугольной формы, чтобы при этом длины сторон обеих полей были бы целыми числами?

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

Входной файл INPUT.TXT содержит целые числа a и b – длины сторон прямоугольника (1 < = a*b ≤ 1014).

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

В выходной файл OUTPUT.TXT выведите либо одно целое число c – длину стороны квадрата, либо 0, если квадрата с целочисленной длиной стороны не существует.

Примеры
INPUT.TXTOUTPUT.TXT
11 42
22 84
315 420


Оригинал - acmp: http://********/index.asp?main=task&id_task=844

Вот мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cmath>
 
int main() {
    unsigned long long a, b;
    std::cin >> a >> b;
    double buf; // Она здесь не нужна, но без нее отказывается работать modf()
    if (modf(sqrt(a*b), &buf) == 0)
        std::cout << sqrt(a*b);
    else std::cout << 0;
}
Проваливаю 8-ой тест - "Wrong Answer". Я не представляю, что у меня не так. Помогите
1
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.12.2018, 15:02
Ответы с готовыми решениями:

Найти длину стороны квадрата, вписаного в квадрат
Дан радиус круга. Найти длину стороны квадрата, вписаного в квадрат.

Вывести ряд чисел, кратных либо 2, либо 3, либо 5
Ребят погоди решить такую задачу, а то что-то то что делаю выдаёт не то. Ряд может быть до 1500...

Можно ли передать в функцию либо вектор, либо список, если да, то как?
Можно ли передать в функцию либо вектор, либо список, если да, то как?

При изменении каких либо данных программа либо вылетает, либо просто не изменяет данные
Добрый вечер. Только недавно начал заниматься С++. И вот возникли проблемы. При изменении каких...

24
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
06.12.2018, 15:48 2
ELchemist, введите числа 2000000 8000000 и посмотрите, что выведет ваша программа.
0
1453 / 828 / 216
Регистрация: 10.02.2018
Сообщений: 3,433
06.12.2018, 15:48 3
Цитата Сообщение от ELchemist Посмотреть сообщение
Проваливаю 8-ой тест - "Wrong Answer".
Можете написать входные данные для 8-го теста ??, а то по ссылке не перейти
0
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
06.12.2018, 15:50 4
Цитата Сообщение от Серж762 Посмотреть сообщение
а то по ссылке не перейти
Замените звездочки на a c m p . r u и переходите, пожалуйста. Только входных данных там нет, это же ACM.
0
1453 / 828 / 216
Регистрация: 10.02.2018
Сообщений: 3,433
06.12.2018, 15:51 5
Цитата Сообщение от valen10 Посмотреть сообщение
введите числа 2000000 8000000
проверил код ТС у меня видало 4е+006
0
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
06.12.2018, 15:54 6
Цитата Сообщение от Серж762 Посмотреть сообщение
проверил код ТС у меня видало 4е+006
А должно быть 4000000, что в общем то одно и то же, но есть одно НО.
1
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.12.2018, 16:06 7
ELchemist, По-хорошему, вашему агроному надо раскладывать a,b на простые множители, причем, одновременно. И следить, чтобы этих простых множителей было четное число.

Добавлено через 7 минут
На всякий случай, разложение числа одного числа на простые множители делается так
C++
1
2
3
4
5
6
7
8
for(p=2; n>p; p++) {
  int k = 0;
  while (n%p==0) {
    k++;
    n /= p;
  }
   // тут k станет равным количеству множителей p в разложении n
}
Для 2-х чисел одновременно этот код надо слегка модифицировать
1
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
06.12.2018, 16:40 8
Думаю там такие тесты на которых проблемы из-за погрешности double. А ведь корень можно поискать в целых числах. Например бинарным поиском.
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.12.2018, 16:59 9
Новичок, зачем нам создавать на ровном месте проблемы из-за огромных чисел? Ведь применив факторизацию, можно оставаться в диапазоне заданных.

Добавлено через 7 минут
Цитата Сообщение от Байт Посмотреть сообщение
Для 2-х чисел одновременно этот код надо слегка модифицировать
Вот, как-то так...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int sk = 1;  // Сторона квадрата
for(int p=2; a>1 && b>1; p++) {
  int k = 0;
  while (a%p==0) {
    k++;
    a /= p;
  }
  while (b%p==0) {
    k++;
    b /= p;
  }
   // тут k станет равным количеству множителей p в разложении a*b
  if (k%2) break;
  for(int i=0; i<k/2; i+) sk *= p;
}
if (a==1 && b==1) cout << sk;
else cout << 0;
0
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
06.12.2018, 20:47 10
Цитата Сообщение от Новичок Посмотреть сообщение
тесты на которых проблемы из-за погрешности double
Что интересно, решение в лоб с double проходит все тесты, главное, чтобы на выходе получилось целое число. Однако решение, которое предложил Байт, выглядит наиболее правильным и нравится мне больше.
0
2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 48
07.12.2018, 15:20  [ТС] 11
Ваш способ ошибочный, Байт. При тесте, где одно из чисел - один, программа выводит 0. Пример:

Ввод : 1 4
Вывод : 0

А должно быть 2
1
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
07.12.2018, 16:51 12
ELchemist, Да, вы правы. Моя небрежность. Спасибо за бдительность. Опять же, смотрите подпись.
По дороге нашел еще описку и неточность. Теперь так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int sk = 1;  // Сторона квадрата
int k;  // Обязательно вне цикла
for(int p=2; a>1 || b>1; p++) {  // Вот тут была главная ошибка
  k = 0;
  while (a%p==0) {
    k++;
    a /= p;
  }
  while (b%p==0) {
    k++;
    b /= p;
  }
   // тут k станет равным количеству множителей p в разложении a*b
  if (k%2) break;
  for(int i=0; i<k/2; i++) sk *= p;  // Тут была описка
}
if (k%2) cout << 0;  // Ну и тут условие было неверно ..
else cout << sk;
Ну вот так, совместными усилиями...
0
2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 48
12.12.2018, 14:23  [ТС] 13
Дальше уже какой-то маразм: на 48 тесте пишет "Time limit exceeded". Ограничение 1 сек., а программа выполняет за 1.5 сек.
P.S. Задача по сложности уже явно не 16%
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
12.12.2018, 15:56 14
Цитата Сообщение от ELchemist Посмотреть сообщение
а программа выполняет за 1.5 сек.
Давайте подумаем и поищем другой алгоритм.
Дырка может там, где у сторон мало (или вообще нет) общих делителей. Тогда цикл работает действительно долго.
Может быть пойти другим путем...
Пусть n = NOD(a,b). Тогда a = x*n, b = y*n, где x, y - взаимно просты.
Площадь S = a*b = n2*x*y - является полным квадратом тогда и только тогда, когда полными квадратами являются x и y.
Алгоритм сводится к двум шагам.
1. Нахождение n = NOD(a, b) - улучшенный алгоритм Эвклида решает эту задачу очень быстро.
2. Выяснение, являются ли x, y полными квадратами. Тут на форуме я недавно видел весьма симпатичные и быстрые алгоритмы.

Добавлено через 9 минут
Разработать функцию, определяющую, является ли натуральное число квадратом какого-либо другого целого числа
Мой алгоритм там не очень хорош в смысле эффективности. Но ниже есть весьма приличные
Можно пойти совсем другим простым путем. С помощью функции sqrt найти приближенное значение корня. И проверить несколько целых значений около него.
В этом случае должно хватить одной секунды за глаза. И даже 0.001 сек
1
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
12.12.2018, 17:42 15
Цитата Сообщение от Байт Посмотреть сообщение
n2*x*y - является полным квадратом тогда и только тогда, когда полными квадратами являются x и y
x = 2, y = 8
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
12.12.2018, 18:41 16
Цитата Сообщение от Новичок Посмотреть сообщение
x = 2, y = 8
Этого быть не может, потому что этого не может быть никогда.
x, y - частные от деления на НОД И они непременно взаимно просты. Иначе двойка уйдет в НОД. А пара x=1, y=4 всему удовлетворяет.
0
2456 / 1061 / 481
Регистрация: 17.11.2018
Сообщений: 2,740
13.12.2018, 01:57 17
Лучший ответ Сообщение было отмечено ELchemist как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    unsigned long long a, b, c, k, ab;
    
    cin >> a >> b;
    ab = a * b;
    
    for ( c = 1, k = c; k < ab ; c++, k = c * c );
    cout << ( k == ab ? c : 0 );
 
    return 0;
}
2
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
13.12.2018, 12:33 18
analogov net, Ваш код теоретически должен делать то, что нужно. Но есть пара недостатков.
1. Произведение a*b может вылезти за разрядную сетку. Именно из-за этого весь сыр-бор. И на этом рубятся тесты.
2. Конечно, время
0
2456 / 1061 / 481
Регистрация: 17.11.2018
Сообщений: 2,740
13.12.2018, 14:04 19
Ну, пусть протестирует и скажет, что к чему. Кстати, у него в задании есть какие-то ограничения на допустимый диапазон данных. он может ограничить, если что. Про время ничего сказать не могу, не проверял...
0
2 / 2 / 0
Регистрация: 14.03.2018
Сообщений: 48
13.12.2018, 14:44  [ТС] 20
Спасибо, analogov net! Ваш код прошел все тесты. И по коду видно, что задача имеет сложность 16%

Вам, Байт, тоже спасибо. Хотя я так и не проверил ваш последний совет, но благодарю за сужение круга поиска решения.
0
13.12.2018, 14:44
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.12.2018, 14:44
Помогаю со студенческими работами здесь

Вычислить длину диогонали квадрата, если известна длине его стороны a
Вычислить длину диогонали квадрата, если известна длине его стороны a Входные данные: Во входном...

Ввести с клави атуры знак арифметической операции(либо+,либо-,либо/)и два числа
Ввести с клавиатуры знак арифметической операции(либо+,либо-,либо/)и два числа.Вывести на экран...

Во время загрузки логотипа виндовс изображение либо переодически пропадает, либо тормозит, либо нет сигнала
Здравствуйте!Помогите решить проблему.Вчера видеокарта работала исправно,а сегодня жена...

Программа, которая сортирует список либо по среднему баллу, либо по алфавиту, либо по оценкам по заданному предмету
Список студенческой группы указан в виде файла записей. Каждая строка записи содержит фамилию...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru