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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.60
Li_Carter
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 6
26.02.2012, 23:22     Название задачи: Коробки (Тема НОД, НОК) #1
Тестирующая система 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())
?
в этом случае, может по времени не пройти, но суть Неверных ответов явно не в лимите времени.
Помогите, пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
C++ Вычисление НОД и НОК
Разработать класс "Cmp", обеспечивающий нахождение НОД и НОК двух чисел C++

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

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

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

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

Текущее время: 21:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru