Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

26.02.2012, 23:22. Просмотров 1399. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Название задачи: Коробки (Тема НОД, НОК) (C++):

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

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

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

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

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

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

7
AncinetHero
49 / 49 / 3
Регистрация: 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 / 3
Регистрация: 22.05.2011
Сообщений: 326
27.02.2012, 01:51 #4
Хорошо, тогда 3 и 21
0
valeriikozlov
Эксперт С++
4672 / 2498 / 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,
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 / 3
Регистрация: 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
Привет! Вот еще темы с ответами:

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

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

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

Найти НОК и НОД , и что бы можно было ввести до 10 чисел , как это сделать на с++? - C++
Здравствуйте , мне нужно найти НОК и НОД , и что бы можно было ввести до 10 чисел , как это можно реализовать на языке С++?


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

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

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