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

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

Войти
Регистрация
Восстановить пароль
 
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

Небольшой баг - C++

12.05.2012, 21:21. Просмотров 382. Ответов 3
Метки нет (Все метки)

Дана очень простая задачка:

Даны числа a0, X, Y, M. Рассмотрим бесконечную последовательность ai = (X * ai-1 + Y) mod M, где операция "a mod b" означает остаток от деления числа a на число b.
Очевидно, что начиная с некоторой позиции, эта последовательность зацикливается. Ваша задача -- найти длину цикла, и количество первых элементов этой последовательности, которые не входят в цикл.
Входные данные
Входные данные состоят из чисел a0, X, Y, M (0 ≤ a0, M, Y ≤ 1012, 0 ≤ X ≤ 106).
Выходные данные
Выведите два числа — длину цикла и количество первых элементов последовательности, которые не входят в цикл. Гарантируется, что оба этих числа не превосходят 800000.


Пример ввода: 0 2 3 4
Ответ на пример(вывод): 1 2
Комментарий
Последовательность выглядит следующим образом: 0, 3, 1, 1, 1,....


ограничение времени на тест: 5 seconds
ограничение памяти на тест: 256 megabytes
ввод: standard
вывод: standard


__________________________

На мой взгляд решение - тривиально.Просто необходимо узнать когда элемент попадётся 1-й 2-й 3-й раз, тогда на 3-й = выход , количество элементов попавшихся 2 раза = период 1 раз = числа до периода

Вот моё решение

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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <fstream>
#include <algorithm>
#include <utility>
#include <stdio.h>
#include <conio.h>
#include <cmath>
using namespace std;
int main(){
    map <int,int> mas;
    int a,x,y,m;
    cin>>a>>x>>y>>m;
    while (1){
        if (mas[a]==2) break;
        if (mas[a]==1) mas[a]=2;else mas[a]=1;
        a=((x*a)+y)%m;
    };
    int fl=0,cycle=0;
    for (map <int,int>::iterator i=mas.begin();i!=mas.end();i++){
        if (i->second==1) fl++;
        if (i->second==2) cycle++;
    };
    cout<<cycle<<" "<<fl;  
    return 0;
}
Проблема : Result - 8/25 Проходит 8 из 25 тестов и ошибка именно в ответе (числах) (WA)
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2012, 21:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Небольшой баг (C++):

std::regex : баг на сайте или баг компилятора? - C++
http://en.cppreference.com/w/cpp/regex/regex_match этот код выкидывает throw... Добавлено через 35 секунд компилятор gcc 4.8

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

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

небольшой вопрос..... - C++
подскажите,пожалуйста,что в этой записи обозначает &amp;(амперсант) перед переменными? int dd, mm, yy; fscanf(Query,&quot;%d.%d.%d&quot;, &amp;dd, &amp;mm,...

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

Разобраться в небольшой функции - C++
Здравствуйте, нужно разобраться в этой функции. Заранее спасибо. ifs &gt;&gt; big &gt;&gt; n; istream&amp; operator&gt;&gt;(istream&amp; ifs, BigInt&amp; big) { ...

3
grizlik78
Эксперт С++
1957 / 1450 / 116
Регистрация: 29.05.2011
Сообщений: 3,012
12.05.2012, 22:15 #2
x*a запросто может вызвать переполнение 32-битной переменной.

Добавлено через 1 минуту
Более того, сами числа 0 ≤ a0, M, Y ≤ 1012 не лезут в 32 бита
2
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
12.05.2012, 22:35  [ТС] #3
щас заценим long long, заранее благодарю

Добавлено через 3 минуты
Цитата Сообщение от grizlik78 Посмотреть сообщение
x*a запросто может вызвать переполнение 32-битной переменной.

Добавлено через 1 минуту
Более того, сами числа 0 ≤ a0, M, Y ≤ 1012 не лезут в 32 бита
Огроменное спасибо! =))))) полное решение
1
PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
13.05.2012, 20:12 #4
Спасибо, у меня тоже была эта проблема!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2012, 20:12
Привет! Вот еще темы с ответами:

Исправить небольшой код - C++
В общем никак не получается правильно написать небольшой кусок программы. Дана матрица nxn. Нужно сравнить между собой все строки...

небольшой вопрос по структурам - C++
Плиз, подскажите как присвоить значение переменной(index) элементу массива структуры(avto.chet). Вроде бы ерунда, а не получается.

Переделать небольшой код из С в С++ - C++
#include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;ctype.h&gt; int main() { char str, *p; printf (&quot;String: &quot;); gets(str); ...

Прошу небольшой помощи - C++
Добрый вечер господа. В Этой теме(Кликабельно), я определился с тем, что начну изучение C++ И у меня к Вас возникает вопрос....


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

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

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