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

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

Восстановить пароль Регистрация
 
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 18:16     Олимпиадная задача - память Ватсона #1
Условие
Память Ватсона достигла критического состояния. Это означает, что все ячейки его памяти заполнились единицами. Рыбка узнала, что если всю память Ватсона считать одним большим шестнадцатеричным числом, то это число будет делиться на 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 тесте, логов нет.

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

Олимпиадная задача C++
C++ Олимпиадная задача
Олимпиадная задача C++
Задача на дп (олимпиадная) C++
C++ Олимпиадная задача
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
20.04.2013, 19:24     Олимпиадная задача - память Ватсона #2
Признак Паскаля
http://ru.wikipedia.org/wiki/%D0%9F%...B0%D0%BB%D1%8F
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 19:30  [ТС]     Олимпиадная задача - память Ватсона #3
Цитата Сообщение от salam Посмотреть сообщение
Я знаю это.
Дело в том, что число может быть очень больше - 100 единиц в hex. Как я узнаю сумму его цифр в десятичном виде?
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
20.04.2013, 19:32     Олимпиадная задача - память Ватсона #4
Считывайте не число, а строку, и преобразуйте ее в число по мере необходимости.
A1exSun
C#
51 / 51 / 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 цифры этого числа в десятичной?
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
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))
                 **********
         }
         *********
     }
A1exSun
C#
51 / 51 / 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))
                 **********
         }
         *********
     }
Не очень понял код. Это что-то вроде длинной арифметики?
Напишите весь код своего варианта с комментариями пожалуйста, мне от него толку только разобраться, сдавать уже некуда.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
21.04.2013, 00:42     Олимпиадная задача - память Ватсона #8
Вы не поняли условия.
Цитата Сообщение от A1exSun Посмотреть сообщение
число содержит не более 100 цифр
На вход подается последовательность из не более чем 100 цифр.
Надо определить, делится ли число, представленное этой последовательностью, на 3.
Число делится на три, если сумма его цифр делится на три.

Итого.
Считываете строку из не более чем 100 символов, суммируете цифры, проверяете, делится ли на три.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2013, 02:45     Олимпиадная задача - память Ватсона
Еще ссылки по теме:

C++ Олимпиадная задача. Рыбаки
Олимпиадная задача. Деревни C++
C++ C++. Олимпиадная задача

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

Или воспользуйтесь поиском по форуму:
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
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 и впихнуть результат куды нужно а затем посчитать модуль.
Yandex
Объявления
21.04.2013, 02:45     Олимпиадная задача - память Ватсона
Ответ Создать тему
Опции темы

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