Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.60
Li_Carter
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 6
#1

Название задачи: Коробки (Тема НОД, НОК) - C++

26.02.2012, 23:22. Просмотров 1338. Ответов 7
Метки нет (Все метки)

Тестирующая система e-olimp.com , ни один тест не проходит.
-------------------------------
Коробки
Есть две коробки. В первой находится a шаров, во второй b (0 < a + b < 2147483648). Шары разрешается перекладывать из одной коробки в другую. Причем перекладывать в любую из коробок можно только столько шаров, сколько в ней находится. Необходимо определить, можно ли все шары сложить в одну коробку.


Технические условия

Входные данные
Каждая строка содержит два целых числа a и b, разделенных пробелом.

Выходные данные
Для каждого теста в отдельной строке вывести количество перекладываний, необходимое для того чтобы все шары находились в одной коробке, или -1, если это сделать невозможно.


Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB

Т.е. на входе 2 6 на выходе дадут 2
8 12 >>>>>> -1
7 9 >>>>>> 4

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
#include <iostream>
 
using namespace std;
 
int NSD(int a, int b) {
  while(b) b^=a^=b^=a%=b;
  return a;
 }
 
int main ()
{
   int a,b,k,t;
   cin >> a >> b;
   k=0;
   t=NSD(a,b);
   if (((a>b) && (a-t!=b+t)) || ((a<b) && (a+t!=b-t))) k=-2; // т.е. допустим 7 и 9 НСД=1, 
//7+1==9-1 - перекладывание возможно, 
//для 8 и 12 НСД=4 8+4!=12-4 - невозможно
   else 
   while (a!=b)
   {
        if (a>b) 
        {
                 a-=b;
                 b*=2;
                 k+=1;
        }
        else
        {
                 b-=a;
                 a*=2;
                 k+=1;
        }
   }
   cout << k+1 << endl;
   return 0;
}
и еще вот из этого -
Входные данные
Каждая строка содержит два целых числа a и b, разделенных пробелом.

я так понимаю, перед cin >> a >> b;
должно быть while (!cin.eof())
?
в этом случае, может по времени не пройти, но суть Неверных ответов явно не в лимите времени.
Помогите, пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2012, 23:22     Название задачи: Коробки (Тема НОД, НОК)
Посмотрите здесь:

НОК и НОД - C++
Здоров Всем ! Вот условие : Определить функцию для нахождения наименьшего общего кратного (НОК) и наибольшего общего...

НОК НОД - C++
Можно ли использовать такой код для нахождения НОК НОД? #include &lt;iostream&gt; #include &lt;conio.h&gt; using std::cout; using std::cin; ...

Вычисление НОД и НОК - C++
Нужно написать программу по вычислению НОД и НОК. Мысли проскакивают, но не полное решение). Подскажите кто сможет, только не кидайте...

Функция НОД->НОК - C++
Пожлуйста помогите разобратьв функциях... Написать функцию поиска НОК двух целых чисел... Функцию НОК как я понимаю нужно сделать через...

Задача на НОД,НОК - C++
Вокруг звезды вращается n планет. Тангенциальная скорость планет постоянна. Направление вращений планет одинаково. Парадом планет...

Нахождение НОД и НОК двух чисел - C++
Вот код программы на Паскале нужно переделать на С++ { Рекурсивные алгоритмы: нахождения НОД и НОК двух чисел } var a,b:longint; ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
27.02.2012, 00:19     Название задачи: Коробки (Тема НОД, НОК) #2
По крайней мере контрпример для вашего алгоритма это 3 и 5
Li_Carter
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 6
27.02.2012, 01:05  [ТС]     Название задачи: Коробки (Тема НОД, НОК) #3
Почему?
3 5
6 2
4 4
8 0

программа выдает 3
все верно
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
27.02.2012, 01:51     Название задачи: Коробки (Тема НОД, НОК) #4
Хорошо, тогда 3 и 21
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.02.2012, 16:03     Название задачи: Коробки (Тема НОД, НОК) #5
Цитата Сообщение от Li_Carter Посмотреть сообщение
C++
1
if (((a>b) && (a-t!=b+t)) || ((a<b) && (a+t!=b-t))) k=-2; // т.е. допустим 7 и 9 НСД=1,
заменить на:
C++
1
   if (((a+b)/t)%2==1) k=-2; // ГІ.ГҐ. äîïóñòèì 7 ГЁ 9 ÍÑÄ=1,
Li_Carter
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 6
27.02.2012, 22:00  [ТС]     Название задачи: Коробки (Тема НОД, НОК) #6
Все равно с измененным кодом на

C++
1
 if (((a+b)/t)%2==1) k=-2;
Результат по тестам:
1. Неверный ответ
2. Неверный ответ
3. Неверный ответ
4. Неверный ответ
5. Неверный ответ
Li_Carter
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 6
28.02.2012, 23:12  [ТС]     Название задачи: Коробки (Тема НОД, НОК) #7
заработало только так

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
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
 
int NSD(int a, int b) {
   if (b == 0) return a;
   return NSD(b, a % b);
 }
 
int main ()
{
   int a,b,t;
   while (scanf("%d %d",&a, &b) == 2)
   {
     int k=0;
     t=(a+b)/NSD(a,b);
     while (t%2==0)
     {
           t/=2;
           k++;
     }
     if (t>1) k=-1;
     cout << k << endl;
   }
   return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.02.2012, 22:33     Название задачи: Коробки (Тема НОД, НОК)
Еще ссылки по теме:

Функция нахождения НОК, НОД и демонстрация вывода - C++
1)Написать функцию для нахождения НОК двух целых чисел. Написать фукнцию для нахождения НОД двух целых чисел. Написать программу...

Вычисление нок и нод переменных натуральных чисел - C++
Здравствуйте. Искал подобную тему по форуму, но там все либо на 2 числа либо на несколько, но с фиксированным числом после компиляции....

Коробки - C++
На столе лежат коробка размера A1 × B1 × C1 и коробка размера A2 × B2 × C2. Выясните можно ли одну из этих коробок положить в другую, если...

Шары и коробки - C++
Шары и коробки (Время: 1 сек. Память: 16 Мб Сложность: 52%) У вас имеется N выстроенных в ряд коробок, A красных и B синих шаров....


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

Или воспользуйтесь поиском по форуму:
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
29.02.2012, 22:33     Название задачи: Коробки (Тема НОД, НОК) #8
А объяснить решение можете?

Мне самому интересно, думаю, автору тоже (как я понял он не понял сам как решил), потому что решать задачи рандомом нет смысла

Добавлено через 11 часов 13 минут
Ну что тут олимпиадников или студентов, профессоров умных нет?
Yandex
Объявления
29.02.2012, 22:33     Название задачи: Коробки (Тема НОД, НОК)
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru