Rashmistrz Temat założony przez niniejszego użytkownika |
[C++] Zadanie "Wesoła małpka" » 2014-11-30 17:38:04 Rozwiązuję zadanie z MAIN2 pt."Wesoła małpka". Treść zadania: Wesoła małpka znalazła sobie nową zabawę. Ustawiła n klatek
ze zwierzątkami (w jednej klatce jest dokładnie jedno zwierzątko)
w kółeczko i skacze po nich. Małpka zawsze skacze od kolejnych
klatek i zawsze otwiera tę, na której stoi. Małpka zatrzyma się,
gdy skoczy na wcześniej otwartą klatkę. Twoim zadaniem jest
stwierdzić, ile zwierzątek ucieknie. Wiadomo, że wszystkie
klatki są początkowo zamknięte oraz każde zwierzątko (poza
wesołą małpką) korzysta z okazji ucieka jeśli może.
WejściePierwszy wiersz wejścia zawiera jedną liczbę całkowitą z (1 ≤ z ≤ 1000000), oznaczającą liczbę zestawów danych. W następnych z wierszach opisywane są kolejne zestawy. Każdy wiersz zestawu zawiera po dwie liczby całkowite n i d(1 ≤ n, d ≤ 10^9) oddzielone spacją, oznaczające odpowiednio liczbę klatek oraz długość skoku małpki
(d = 1 oznacza, że małpka przeskoczy na następnąw kolejności klatkę).
WyjścieDla każdego zestawu danych powinna się znaleźć w nowym wierszu jedna liczba całkowita,
równa liczbie zwierzątek, które uciekną. |
Mój kod: #include <iostream>
using namespace std;
int main() {
int z, n, d;
register int wypuszczone, krok;
cin >> z;
while( z-- > 0 ) {
cin >> n >> d;
bool przesuniecia[ d ];
for( register int i = 0; i < d; ++i )
przesuniecia[ i ] = true;
wypuszczone = 0;
krok = 0;
do {
wypuszczone +=( n + krok ) / d;
przesuniecia[ krok ] = false;
krok =( n + krok ) % d;
} while( przesuniecia[ krok ] == true );
cout << wypuszczone << '\n';
}
return 0;
} Program działa bez zarzutu przy małych liczbach, jednak przy dużych "zestawach danych" za długo pracuje, tzn. przy sprawdzaniu przez system sprawdzający wyrzuca: "Przekroczenie limitu czasu"... (o 50ms) Jak ten program można zoptymalizować lub zmienić? Zastanawiałem się czy można jakoś połączyć modulo i dzielenie, lecz nic nie znalazłem... |
|
Rashmistrz Temat założony przez niniejszego użytkownika |
» 2014-11-30 20:25:31 Pomożecie? :C |
|
mati1995g |
» 2014-11-30 20:35:55 Wklej to do int main i powiedz czy pomogło ios_base::sync_with_stdio( 0 );
|
|
darko202 |
» 2014-11-30 20:38:53 czy mógłbyś wyjasnić użyte pojecie
* "dużych zestawów danych"
jeśli bowiem rezerwujesz zbyt wielką ilość pamieci na zmienne tzn. więcej niż jest dostępnych zasobów sustemu
* zawiesza się - zwraca komunikat
bool przesuniecia[ d ]; po tej operacji czy na petli while
* jak rozumiesz optymalizację programu ?
|
|
Rashmistrz Temat założony przez niniejszego użytkownika |
» 2014-11-30 21:38:45 | Wklej to do int main i powiedz czy pomogło |
W niektórych przypadkach lepiej, a w niektórych gorzej. :/ Jednak nadal jest przekroczony limit czasu: 1d) 7.01s/7.00s(max) 1e) 7.07s/7.00s(max) 1f) 7.03s/7.00s(max) jeśli bowiem rezerwujesz zbyt
wielką ilość pamieci na zmienne |
Ten program ma przyjąć "z" zestawów danych. Rozwiązałem to tak: cin >> z;
while( z-- > 0 ) {
cin >> n >> d;
Błędnie to opisałem, bo chodzi mi o wielkość liczb w zestawach. Głównym problemem jest to że im większe będzie "d" od "n" tym dłużej będzie pracować przy danym zestawie, co nie idzie na moją korzyść. zawiesza się - zwraca komunikat
bool przesuniecia[ d ]; po tej operacji czy na petli while |
"Program działa bez zarzutu"... Wiem, że ten działanie jest złe, ale nie znam się jeszcze na dynamicznej alokacji, więc tak zostało z mojej "zieloności". | jak rozumiesz optymalizację programu ? |
Zrobienie coś z nim by zwrócił on prawidłowy wynik w krótszym czasie. |
|
Monika90 |
» 2014-12-01 00:04:23 #include <iostream>
#include <boost/math/common_factor.hpp>
int main()
{
int z;
std::cin >> z;
while( z > 0 )
{
int n, d;
std::cin >> n >> d;
std::cout << n / boost::math::gcd( n, d ) << '\n';
--z;
}
}
I to wcale nie jest gotowiec, bo MAIN nie ma boosta. |
|
Rashmistrz Temat założony przez niniejszego użytkownika |
» 2014-12-01 15:44:52 n / boost::math::gcd( n, d ) , Nie rozumiem tego. Co to robi? |
|
Monika90 |
» 2014-12-01 16:03:00 po angielsku GCD znaczy to samo co NWD po polsku |
|
| « 1 » 2 |