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

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

Восстановить пароль Регистрация
 
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
12.05.2012, 21:21     Небольшой баг #1
Дана очень простая задачка:

Даны числа 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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2012, 21:21     Небольшой баг
Посмотрите здесь:

C++ Небольшой вопросик
небольшой вопрос..... C++
Прошу небольшой помощи C++
Небольшой цикл C++
Небольшой трабл с функциями C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
12.05.2012, 22:15     Небольшой баг #2
x*a запросто может вызвать переполнение 32-битной переменной.

Добавлено через 1 минуту
Более того, сами числа 0 ≤ a0, M, Y ≤ 1012 не лезут в 32 бита
Ternsip
 Аватар для 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 бита
Огроменное спасибо! =))))) полное решение
PhotonDT
 Аватар для PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
13.05.2012, 20:12     Небольшой баг #4
Спасибо, у меня тоже была эта проблема!
Yandex
Объявления
13.05.2012, 20:12     Небольшой баг
Ответ Создать тему
Опции темы

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