Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_03_10 - Ciąg EKG |
Ciąg EKG
Ciąg EKG to ciąg liczb całkowitych dodatnich zdefiniowany następująco: pierwsze dwa wyrazy ciągu to 1, 2, a każdy następny wyraz jest najmniejszą liczbą całkowitą dodatnią, która do tej pory nie wystąpiła w ciągu i która nie jest względnie pierwsza z wyrazem bezpośrednio poprzedzającym. Poniżej kilka początkowych wyrazów ciągu:
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16
Ciąg ten nazywany jest ciągiem EKG, ponieważ jego wykres przypomina elektrokardiogram. Ciąg ten ma tę własność, że wszystkie liczby całkowite dodatnie prędzej czy później pojawią się w nim. Twoim zadaniem jest wyznaczyć pozycję w ciągu dla danej liczby całkowitej.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 1000) oznaczająca liczbę przypadków testowych. Każdy przypadek testowy to jedna liczba całkowita a (1 ≤ a ≤ 3 · 105).
Wyjście
Dla każdej liczby podanej na wejściu należy wyznaczyć jej pozycję porządkową w ciągu EKG.
Przykład
Wejście
5
1
2
3
10
15
Wyjście
1
2
5
9
11
Dodane przez: | Mariusz Śliwiński |
Data dodania: | 2015-03-08 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |