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

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

Войти
Регистрация
Восстановить пароль
 
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
#1

Олимпиадная задача - память Ватсона - C++

20.04.2013, 18:16. Просмотров 735. Ответов 8
Метки нет (Все метки)

Условие
Память Ватсона достигла критического состояния. Это означает, что все ячейки его памяти заполнились единицами. Рыбка узнала, что если всю память Ватсона считать одним большим шестнадцатеричным числом, то это число будет делиться на 7. Но не поверила и захотела проверить этот факт. Для этого Рыбка узнала у Ватсона, сколько ячеек в его памяти. Оказалось, что их очень много - таких больших чисел Рыбка еще не видела. Помогите ей проверить факт делимости памяти Ватсона.

Входные данные
Одно целое неотрицательное число, представленное в десятичном виде - количество ячеек памяти Ватсона. Это число содержит не более 100 цифр.

Выходные данные
Вывести результат проверки в виде одного слова (без кавычек): «yes»-если память Ватсона делится на 7, «по» - память Ватсона не делится на 7.

Пример
Вход: 9
Вывод: yes

Пояснение
Память Ватсона 111111111 в шестнадцатеричном виде. Это 4581298449 в десятичном виде, и это число делится на 7.

Мое решение просто:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n;
    cin>>n;
    cout<<((n % 3 == 0) ? "yes" : "no");
    return 0;
}
Неправильный ответ на 21 тесте, логов нет.

Как правильно решить?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2013, 18:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Олимпиадная задача - память Ватсона (C++):

Задача на дп (олимпиадная) - C++
Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через...

Олимпиадная задача - C++
Был в прошлом году на олимпиаде по программированию и там была такая задача: После запуска программы пользователь должен начать...

Олимпиадная задача - C++
#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;iostream&gt; using namespace std; int main() { unsigned int N; cout&lt;&lt;&quot;N=&quot;;...

Олимпиадная задача - C++
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ... Необходимо по номеру N определить...

Олимпиадная задача - C++
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с помощью матриц, либо с помощью графов, но какого-то...

C++. Олимпиадная задача - C++
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
20.04.2013, 19:24 #2
Признак Паскаля
http://ru.wikipedia.org/wiki/%D0%9F%...B0%D0%BB%D1%8F
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 19:30  [ТС] #3
Цитата Сообщение от salam Посмотреть сообщение
Я знаю это.
Дело в том, что число может быть очень больше - 100 единиц в hex. Как я узнаю сумму его цифр в десятичном виде?
0
stima
474 / 323 / 31
Регистрация: 22.03.2011
Сообщений: 1,047
Завершенные тесты: 2
20.04.2013, 19:32 #4
Считывайте не число, а строку, и преобразуйте ее в число по мере необходимости.
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 19:40  [ТС] #5
Цитата Сообщение от stima Посмотреть сообщение
Считывайте не число, а строку, и преобразуйте ее в число по мере необходимости.
Читайте условие! Вводиться не число, а количество единиц.
Как по мере необходимости? Для чего?

Добавлено через 6 минут
Число делится на 7 тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7 (например, 343 делится на 7, так как 34-(2·3)=34-6=28 делится на 7; 259 делится на 7, так как 25-(2·9)=7 делится на 7).
Как из множества единиц в шестнадцатеричной системе получить последние 3 цифры этого числа в десятичной?
0
stima
474 / 323 / 31
Регистрация: 22.03.2011
Сообщений: 1,047
Завершенные тесты: 2
20.04.2013, 19:56 #6
Вводиться не количество единиц, а число). При этом количество ячеек определяеться этим числом.
Я дам идею, на псевдо коде.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    typedef unsigned char byte;
 
     byte memory_map[100];
     for (int i = strlen(memory_map); i; --i)
     {
         byte bit_map = atoi(memory_map[i]);
         if (bit_map  ==  0)
             ************
 
         unsigned long long digital = 1;
         for (int j = 1; j < bit_map; ++j)
         {
               digital += 16;
               if (is_mult_of_7(digit))
                 **********
         }
         *********
     }
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 20:05  [ТС] #7
Цитата Сообщение от stima Посмотреть сообщение
Вводиться не количество единиц, а число). При этом количество ячеек определяеться этим числом.
А, я не так понял
Цитата Сообщение от stima Посмотреть сообщение
Я дам идею, на псевдо коде.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    typedef unsigned char byte;
 
     byte memory_map[100];
     for (int i = strlen(memory_map); i; --i)
     {
         byte bit_map = atoi(memory_map[i]);
         if (bit_map  ==  0)
             ************
 
         unsigned long long digital = 1;
         for (int j = 1; j < bit_map; ++j)
         {
               digital += 16;
               if (is_mult_of_7(digit))
                 **********
         }
         *********
     }
Не очень понял код. Это что-то вроде длинной арифметики?
Напишите весь код своего варианта с комментариями пожалуйста, мне от него толку только разобраться, сдавать уже некуда.
0
lemegeton
2924 / 1353 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
21.04.2013, 00:42 #8
Вы не поняли условия.
Цитата Сообщение от A1exSun Посмотреть сообщение
число содержит не более 100 цифр
На вход подается последовательность из не более чем 100 цифр.
Надо определить, делится ли число, представленное этой последовательностью, на 3.
Число делится на три, если сумма его цифр делится на три.

Итого.
Считываете строку из не более чем 100 символов, суммируете цифры, проверяете, делится ли на три.
0
nonedark2008
909 / 648 / 134
Регистрация: 28.07.2012
Сообщений: 1,760
21.04.2013, 02:45 #9
Все вроде просто. 1=1mod7, 16=2mod7, 16^k=2^k mod7. Наше число имеет вид sum 1*16^i. Следует:
sum 16^i=sum 2^i mod7. Сумму можно перефигачить через сумму геометрической прогрессии. Основной проблемой осталось переполнение целого типа, т. к. 2 в сотой степени явно не влезет. Но тут помогает нам mod7. Т. е. все операции можно проводить по модулю числа 7. 2^3=1mod7. Значит 2^i=2^(i mod 3) mod 7. Получаем уже мелкое число, а не два в сотой. Подставляем в формулу суммы геом прогрессии и смотрим значение остатка от деления на 7. Готово.

Добавлено через 4 минуты
Все что надо, это посчитать остаток от деления входного числа на 3 и впихнуть результат куды нужно а затем посчитать модуль.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2013, 02:45
Привет! Вот еще темы с ответами:

Олимпиадная задача - C++
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда...

Олимпиадная задача - C++
Алфавит мурмарианской системы счисления включает три цифры - 1, 2 и 3. Одна из популярных социальных сетей &quot;НаМурмаре&quot; при регистрации...

Олимпиадная задача. Рыбаки - C++
Подскажите пожалуйста, как решается эта задача. Однажды N рыбаков отправились на рыбалку, где поймали X рыб. После этого рыбаки легли...

Олимпиадная задача. Деревни - C++
Всем привет.. задача такая: Деревни В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
21.04.2013, 02:45
Ответ Создать тему
Опции темы

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