x nod 1000 != 3 ostatnie cyfry x (?!)
-
- Użytkownik
- Posty: 87
- Rejestracja: 21 lis 2006, o 23:22
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 21 razy
- Pomógł: 3 razy
x nod 1000 != 3 ostatnie cyfry x (?!)
<-- pracuje nad tym zadaniem, programuję w c++. Mój program działający na zasadzie licz wynik ze schematu Hornera, po drodze wszystko moduluj przez 1000, dostaje tylko 80/100 pkt, czyli nie przechodzi 2och testow. Jako ze sa to duze testy, to nie moge ich recznie zbadac... W zwiazku z tym nasuwa mi sie pytanie: czy jest mozliwe, by reszta z dzielenia wartosci wielomianu przez 1000 byla czyms innym niz 3ma ostatnimi cyframi tejże wartosci? Jesli tak, to jak sobie z tym poradzic, zeby w programie bylo wszystko OK?
x nod 1000 != 3 ostatnie cyfry x (?!)
To może zrób tak:
\(\displaystyle{ W(x)=a_0+x\left( a_1 + x\left( a_2 + x \left( \ldots a_{n-1}+a_n x \right) \ldots \right) \right)}\)
Czyli masz liniową złożoność od stopnia wielomianu.
Zaznaczam, że moja wiedza informatyczna jest nikła, więc ten pomysł może być nieefektywny...-- 6 sierpnia 2009, 17:58 --Oczywiście wszytko \(\displaystyle{ \pmod{1000}}\)
\(\displaystyle{ W(x)=a_0+x\left( a_1 + x\left( a_2 + x \left( \ldots a_{n-1}+a_n x \right) \ldots \right) \right)}\)
Czyli masz liniową złożoność od stopnia wielomianu.
Zaznaczam, że moja wiedza informatyczna jest nikła, więc ten pomysł może być nieefektywny...-- 6 sierpnia 2009, 17:58 --Oczywiście wszytko \(\displaystyle{ \pmod{1000}}\)
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
x nod 1000 != 3 ostatnie cyfry x (?!)
przypuszczam, ze może być kłopot z ujemnymi wartościami, np. jeśli W(x)=-1, to ty zwracasz 999.
albo zle dopelniasz zerami. A wyskakuje zla odpowiedz, czy czas?
albo zle dopelniasz zerami. A wyskakuje zla odpowiedz, czy czas?
-
- Użytkownik
- Posty: 87
- Rejestracja: 21 lis 2006, o 23:22
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 21 razy
- Pomógł: 3 razy
x nod 1000 != 3 ostatnie cyfry x (?!)
@frej:
Tak własnie robie, to jest schemat Hornera, i wszystko mod 1000
@Zordon:
C++ dla ujemnych daje ujemny mod, tzn np. (-7)%10 = -7. Zerami wszystko na glanc dopelniam, czasy mam super, tylko dla 2och testow mam zle odp, a ze to jest na mainie to widze jaki ja mam wynik, a jaki jest wzorcowy. Z tymze jak mowilem, te 2 testy sa duze wiec recznie ich ni przeanalizuje... A kod programu wyglada tak:
Tak własnie robie, to jest schemat Hornera, i wszystko mod 1000
@Zordon:
C++ dla ujemnych daje ujemny mod, tzn np. (-7)%10 = -7. Zerami wszystko na glanc dopelniam, czasy mam super, tylko dla 2och testow mam zle odp, a ze to jest na mainie to widze jaki ja mam wynik, a jaki jest wzorcowy. Z tymze jak mowilem, te 2 testy sa duze wiec recznie ich ni przeanalizuje... A kod programu wyglada tak:
Kod: Zaznacz cały
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
#define VAR(a,b) __typeof (b) a = b
#define REP(i,n) for (int _n=(n), i=0; i<_n; ++i)
#define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i)
#define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i)
#define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i)
#define abs(a) ((a)<0 ? -(a) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef long long int ll;
typedef long double ld;
int s;
ll x, a[20010], wyn;
int main()
{
scanf("%d %lld", &s, &x);
x %= 1000;
REP(i, s) scanf("%lld", &a[i]); ;
wyn = a[0]%1000;
FOR(i, 1, s-1) wyn = (a[i]%1000 + (wyn*x)%1000)%1000;
printf("%0*lld
", 3, abs(wyn%1000));
system("pause");
return 0;
}
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
x nod 1000 != 3 ostatnie cyfry x (?!)
nikt Ci nie będzi kodu naprawiał, tymbardziej z makrami. Sprawdź np. co wyskakuje dla wielomianu \(\displaystyle{ -999x^2-3x+10}\), \(\displaystyle{ x=1}\)
i przede wszystkim wywal system("pause");
i przede wszystkim wywal system("pause");
-
- Użytkownik
- Posty: 87
- Rejestracja: 21 lis 2006, o 23:22
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 21 razy
- Pomógł: 3 razy
x nod 1000 != 3 ostatnie cyfry x (?!)
Heh to modulo jakies wredne jest przez te ujemne liczby :/ Juz widze co sie dzieje (najpierw mam -3-999=-1002 -1002 mod 1000 = -2, no a z tego raczej 992 (ktore ma wyjsc) nie zrobie :/). Wie ktos moze co tu powinienem zrobic zeby modulo dobre bylo?