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

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

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

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

20.04.2013, 18:16. Просмотров 731. Ответов 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 тесте, логов нет.

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

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

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

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

Сладкая олимпиадная задача - C++
Дан торт который порезан на m*n равных кусков и вы хотите иметь точно один фрукт на каждом куске. Давайте обозначим f(m,n) количество...

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

Олимпиадная задача. Алгоритм - C++
Всем привет. Помогите понять алгоритм решения задачи. 1. Как найти перекресток, с которого начинается движение робота (и...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
20.04.2013, 19:24     Олимпиадная задача - память Ватсона #2
Признак Паскаля
http://ru.wikipedia.org/wiki/%D0%9F%...B0%D0%BB%D1%8F
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
20.04.2013, 19:30  [ТС]     Олимпиадная задача - память Ватсона #3
Цитата Сообщение от salam Посмотреть сообщение
Я знаю это.
Дело в том, что число может быть очень больше - 100 единиц в hex. Как я узнаю сумму его цифр в десятичном виде?
stima
455 / 304 / 23
Регистрация: 22.03.2011
Сообщений: 990
Завершенные тесты: 2
20.04.2013, 19:32     Олимпиадная задача - память Ватсона #4
Считывайте не число, а строку, и преобразуйте ее в число по мере необходимости.
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 цифры этого числа в десятичной?
stima
455 / 304 / 23
Регистрация: 22.03.2011
Сообщений: 990
Завершенные тесты: 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))
                 **********
         }
         *********
     }
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))
                 **********
         }
         *********
     }
Не очень понял код. Это что-то вроде длинной арифметики?
Напишите весь код своего варианта с комментариями пожалуйста, мне от него толку только разобраться, сдавать уже некуда.
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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++
Условие задачи: Задано 121 натуральне число : 1...121 .Разбить числа в 11 групп так,чтобы каждая группа вмещала 11 чисел,каждое число...

Анаграммы(олимпиадная задача) - C++
Cтрока S1 называется анаграммой строки S2, если она получается из S2 перестановкой символов. Даны строки S1 и S2. Напишите программу,...

Олимпиадная задача - движение фишки - C++
Есть вот такая задача: /*Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей,...

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


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

Или воспользуйтесь поиском по форуму:
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
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     Олимпиадная задача - память Ватсона
Ответ Создать тему
Опции темы

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