Hej,
mógłby mi ktoś precyzyjnie wytłumaczyć zasady działania SPOJ'u? Każdy program, który tam wstawię ma jakiś błąd (NZEC, błąd kompilacji itd.). U mnie wszystko działa jak należy (patrząc według danych z zadania) oraz mieszczę się w wymaganym przedziale czasowym (patrząc według http://ideone.com/). Więc w czym problem?! Przyznam, że jest to już powoli frustrujące...
0
0
SPOJ kompiluje program i odpala go kilka razy używając różnych zestawów danych zgodnych ze specyfikacją - tajnych zestawów danych.
O ile Twój program dla krótkich i ładnych danych wejściowych może działać szybko i bezbłędnie, o tyle w tych końcowych testach na SPOJu zazwyczaj są przykłady na granicy górnego limitu określonego w zadaniu.
NZEC - non-zero exit code - program wyłożył się z jakiegoś powodu
błąd kompilacji - cóż, zapewne nie masz takiego samego kompilatora w tej samej wersji, co oni, mogą się zdarzać różne odchylenia
0
A w przypadku NZEC'u da radę sprawdzić jakoś co konkretnie poszło nie tak?
0
Jak pokażesz jakiś kod, który wysyłałeś to prawdopodobnie będzie wiadomo co robisz źle.
0
Pierwsze z brzegu: Czy umiesz potęgować (link).
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace CzyUmieszPotegowac
{
class Program
{
static void Main(string[] args)
{
short przypadki = short.Parse(Console.ReadLine());
Int32[] podstawa = new Int32[przypadki];
Int32[] wykladnik = new Int32[przypadki];
Int32[] wynik = new Int32[przypadki];
for (int i = 0; i < przypadki; i++)
{
var ab = Console.ReadLine().Split(null);
podstawa[i] = int.Parse(ab[0]);
wykladnik[i] = int.Parse(ab[1]);
}
for (int j = 0; j < przypadki; j++)
{
wynik[j] = Convert.ToInt32(Math.Pow(podstawa[j], wykladnik[j]));
Console.Write(("\n" + wynik[j] % 10));
}
}
}
}
2
Nie umiesz potegowac po prostu :P
0
oraz mieszczę się w wymaganym przedziale czasowym (patrząc według http://ideone.com/)
nie porównuj czasów z ideone z czasami na SPOJ-u.
Jeden serwer może być szybszy od drugiego.
0
Azarien napisał(a):
oraz mieszczę się w wymaganym przedziale czasowym (patrząc według http://ideone.com/)
nie porównuj czasów z ideone z czasami na SPOJ-u.
Jeden serwer może być szybszy od drugiego.
Prawda, o ile pamiętam to podstawowe maszyny SPOJa są dość słabe.
0
Na tym mam NZEC, na innym "przekroczono limit czasu"... Ehhh, jaki ten SPOJ jest skomplikowany :P
0
@Czech0wiec zdajesz sobie sprawę z tego że typy liczbowe w komputerze maja pewne ograniczenia? o_O W zadaniu jest napisane że możesz ty mieć miliard do potęgi miliardowej. Powodzenia w liczeniu tego za pomocą Math.Pow() ;]
Największa zmienna liczbowa -> unsigned int64 ma 64 bity czyli może przechować nie więcej niż 264 różnych liczb, czyli maksymalna liczba to 264. A ty tu masz miliard do miliardowej potęgi...
Zadania na SPOJU wymagają myślenia a nie klepania.
0
jeśli spoj nie przyjmuje twojego programu na 99.9% to ty popełniłeś błąd(ten 0.1 % bo czasem w zadaniach jest błąd, albo coś innego). Tzn masz błędny algorytm który nie działa na wszystkich możliwych przypadkach. Najlepiej wejsć na forum spoja i znaleźć jakieś podchwytliwe dane testowe i jeśli output będzie inny niż pownien toi na tych danych debugować program linijka po linijce aż znajdziesz błąd
0
Trochę pogrzebałem w kodzie i nie mam już problemu z NZEC'em tylko nie mieszczę się w czasie...
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace CzyUmieszPotegowac
{
class Program
{
static long Potegowanie(int a, int b)
{
long x;
if (b == 0)
return 1;
else if ((b % 2) != 0)
return a * Potegowanie(a, b - 1);
else
x = Potegowanie(a, b / 2);
return x * x;
}
static void Main(string[] args)
{
short przypadki = short.Parse(Console.ReadLine());
short i = 0;
while (i < przypadki)
{
var ab = Console.ReadLine().Split(null);
if (int.Parse(ab[1]) == 1)
Console.WriteLine(Potegowanie(int.Parse(ab[0]), int.Parse(ab[1])) % 10);
else
{
int d = 2;
while (d <= int.Parse(ab[1]))
{
if (int.Parse(ab[1]) == d)
{
Console.WriteLine(Potegowanie(int.Parse(ab[0]), 2) % 10);
d = d + 4;
}
d++;
if (int.Parse(ab[1]) == d)
{
Console.WriteLine(Potegowanie(int.Parse(ab[0]), 3) % 10);
d = d + 4;
}
d++;
if (int.Parse(ab[1]) == d)
{
Console.WriteLine(Potegowanie(int.Parse(ab[0]), 4) % 10);
d = d + 4;
}
d++;
if (int.Parse(ab[1]) == d)
{
Console.WriteLine(Potegowanie(int.Parse(ab[0]), 5) % 10);
d = d + 4;
}
d++;
}
}
i++;
}
}
}
}
Jest opcja jakoś to naprawić czy szukać innego algorytmu na potęgowanie?
0
Przeczytaj post @Shaloma ponownie, ze zrozumieniem:
Shalom napisał(a)
Największa zmienna liczbowa -> unsigned int64 ma 64 bity czyli może przechować nie więcej niż 264 różnych liczb, czyli maksymalna liczba to 264. A ty tu masz miliard do miliardowej potęgi...
Jak wykonałbyś potęgowanie na kartce? Zapewne pisemnie.
No to teraz coś podobnego musisz zaimplementować w swoim programie: 'pisemne' potęgowanie na (bliżej) nieskończenie wielkich liczbach. Jak dodasz dodatkowo dzielenie, liczenie modulo oraz odejmowanie do tych swoich bignumów, to wtedy będziesz mógł skorzystać z algorytmu szybkiego potęgowania i porównać wyniki.
Innymi słowy: musisz napisać program, który będzie w stanie wykonywać obliczenia na liczbach przekraczających domyślne typy liczbowe w komputerze. Dopóki tego nie wykonasz, nie mamy o czym tutaj mówić w kwestii czasu wykonywania.
Nevermind, nie doczytałem treści zadania.
0
@Czech0wiec żal mi cię trochę z tymi twoimi pomysłami i będę łaskawy. Jak na kartce policzylbyś na przykład ostatnią cyfrę 21234567 ? Otóż mógłbyś zauważyć, że możliwe wyniki to 2,4,6,8 i że cyklicznie się powtarzają. W ogóle tak na prawdę interesuje cię tylko ostatnia cyfra więc nie ma potrzeby potęgować całej liczby. Jeśli wiem że ostatnia cyfra 25 to 2 to wiem że ostatnia cyfra 26 to 2*2 czyli 4. Nie muszę wiedzeć że to było 32 i 64, bo to bez znaczenia.
To już rozwiązuje problem nie mieszczących się liczb, bo skoro maksymalnie mnożysz przez miliard a możliwe mnożniki to 0-9 to potrzebujesz typ liczbowy na 9 miliardów a tu spokojnie 64 bitowy int starczy (34 bitowy dałby już radę ;])
0
Niepotrzebnie tak kombinujecie. Chodzi przecież tylko o ostatnią cyfrę. Przy mnożeniu tylko ostatnia cyfra może zmieniać ostatnią, więc wystarczyłaby nawet zmienna char do obliczeń
Tutaj wrzucam kod w C++. Wiem, że chodzi o C#, ale nie ma tu nic zbyt skomplikowanego
#include <iostream>
int foo(unsigned long long int a, unsigned long long int b)
{
int lastADigitOnStart = a%10;
int lastADigitNow = lastADigitOnStart;
int i = 1;
int lastADigits[10] = {0};
while(true)
{
lastADigitNow = (lastADigitOnStart*lastADigitNow)%10;
lastADigits[i] = lastADigitNow;
++i;
if(i>=b) return lastADigitNow;
if(lastADigitOnStart==lastADigitNow)
{
return lastADigits[b%i];
}
}
}
int main()
{
std::cout << foo(12,9);
return 0;
}
Wykorzystana tu jest zasada, że co jakiś czas (maksymalnie po 10 razach) końcowa cyfra się powtarza. Dzięki temu możemy już po kilku przejściach pętli określić wynik.
@Edit. poprawiłem kod