Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Li_Carter
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 6
#1

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

26.02.2012, 23:22. Просмотров 1489. Ответов 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())
?
в этом случае, может по времени не пройти, но суть Неверных ответов явно не в лимите времени.
Помогите, пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2012, 23:22
Ответы с готовыми решениями:

НОК НОД
Можно ли использовать такой код для нахождения НОК НОД? #include &lt;iostream&gt;...

НОК и НОД
Здоров Всем ! Вот условие : Определить функцию для нахождения...

НОД и НОК
Дан НОД и НОК надо найти каким числом они (НОД и НОК) принадлежат

НОД и НОК
Вводятся два натуральных числа. Вывести их наибольший общий делитель (НОД) и...

Вычисление НОД и НОК
Нужно написать программу по вычислению НОД и НОК. Мысли проскакивают, но не...

7
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
27.02.2012, 00:19 #2
По крайней мере контрпример для вашего алгоритма это 3 и 5
0
Li_Carter
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 6
27.02.2012, 01:05  [ТС] #3
Почему?
3 5
6 2
4 4
8 0

программа выдает 3
все верно
0
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
27.02.2012, 01:51 #4
Хорошо, тогда 3 и 21
0
valeriikozlov
Эксперт С++
4684 / 2510 / 751
Регистрация: 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,
0
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. Неверный ответ
0
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;
}
0
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
29.02.2012, 22:33 #8
А объяснить решение можете?

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

Добавлено через 11 часов 13 минут
Ну что тут олимпиадников или студентов, профессоров умных нет?
0
29.02.2012, 22:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.02.2012, 22:33

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

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

Нахождение НОД и НОК двух чисел
Вот код программы на Паскале нужно переделать на С++ { Рекурсивные алгоритмы:...


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

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

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