Ustawić

Załóżmy, że masz n bezpieczników, z 1 ≤ n ≤ 5, z których każdy ma metr długości, a każdy bezpiecznik ma powiązaną szybkość spalania N metrów na D godzin.

Bezpiecznik można zapalić na jednym lub obu końcach, a następnie zgasić na jednym lub obu końcach, ponownie zapalić, ponownie zgasić itp. Tyle razy, ile potrzeba, aż do pełnego zużycia bezpiecznika. Jesteś w stanie natychmiast zapalić i zgasić bezpieczniki, i możesz obserwować dokładnie moment, w którym bezpiecznik jest całkowicie zużyty (spalony).

Bezpiecznik nie mogą być cięte ani nie może się świecić wszędzie z wyjątkiem na jego końcach.

Taka konfiguracja pozwala na nieskończenie dokładny system pomiaru czasu, mierząc czas między dowolnymi dwoma zapaleniami / zużyciem bezpiecznika. Na przykład, biorąc pod uwagę dwa bezpieczniki o szybkości spalania 1 metr na godzinę, możesz zmierzyć dokładnie 45 minut (3/4 godziny) przez

1. jednocześnie: zapalając pierwszy bezpiecznik na obu końcach, zapalając drugi bezpiecznik na jednym końcu i zaznaczając początek przedziału czasowego
2. zapalanie drugiego końca drugiego bezpiecznika w momencie, gdy pierwszy bezpiecznik zostanie zużyty (30 minut później)
3. oznaczenie końca przedziału czasowego w momencie, gdy drugi bezpiecznik zostanie zużyty (15 minut później)

Wyzwanie

Biorąc pod uwagę ułamkową liczbę godzin t oraz zbiór n ułamków reprezentujących dokładne prędkości spalania n bezpieczników, napisz program lub funkcję, która generuje / zwraca prawdziwą wartość, jeśli t godziny można dokładnie zmierzyć poprzez systematyczne spalanie bezpieczników lub inaczej wartość fałsz.

Dane wejściowe do programu mogą być dowolne z poniższych:

• argumenty wiersza polecenia formularza TN/TD N1/D1 N2/D2 N3/D3 ...
• ciąg formularza TN/TD N1/D1 N2/D2 N3/D3 ...odczytany z stdinlub równoważny
• ciąg formularza TN/TD N1/D1 N2/D2 N3/D3 ...przekazany jako argument funkcji
• tablica ciągów ["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...]przekazywanych jako argument funkcji

We wszystkich przypadkach , T = TN/ TD, w którym TN, TD∈ [1,10000].

Podobnie we wszystkich przypadkach: szybkość spalania bezpiecznika i = N _i / D _i = N<i>/ D<i>, gdzie N<i>, D<i>[1,10] ∀ i .

Możesz założyć, że zawsze będzie od 1 do 5 bezpieczników (włącznie) i że wszystkie dane wejściowe są prawidłowe i znajdują się w zasięgu. Możesz również założyć, że wszystkie ułamki wejściowe podano w najniższych kategoriach.

Nie można używać liczb zmiennoprzecinkowych z elementami ułamkowymi dla tego wyzwania. Oznacza to, że jeśli użyjesz liczb zmiennoprzecinkowych w dowolnym miejscu aplikacji, mogą one przyjmować tylko wartości całkowite z zerowym składnikiem ułamkowym.

Punktacja

Jest to wyzwanie polegające na grze w golfa , dlatego wygrana zostanie przyznana za najkrótszą zgodność w bajtach.

Przykładowe wejścia / wyjścia

input:  29/6 3/2 2/3 3/5 3/7 7/5
output: true

One solution:
  - light both ends of fuse 1, mark start of interval
  - on fuse 1 consumption: light both ends of fuse 2, light one end of fuse 5
  - on fuse 5 consumption: extinguish one end of fuse 2, light both ends of fuse 3,
    light both ends of fuse 4
  - on fuse 2 consumption: extinguish one end of fuse 3, extinguish both ends of
    fuse 4
  - on fuse 3 consumption: relight one end of fuse 4
  - on consumption of fuse 4: mark end of interval (29/6 hours)

input:  2/1 3/1 5/1 7/1
output: false

input:  5/1 6/1 1/6 9/1 1/9
output: true

One solution:
  - light fuse 1 at one end, light fuse 2 at both ends, light fuse 4 at both ends
  - on fuse 1 consumption: extinguish one end of fuse 2, mark start of interval
  - on fuse 4 consumption: relight one end of fuse 2
  - on fuse 2 consumption: mark end of interval (5 hours)

Miłego łączenia! :)

Python 2, 305

To jest wersja golfowa. Jest praktycznie bezużyteczne dla n> 3 , ponieważ złożoność czasu (i przestrzeni) jest jak 3 ^{n 2} ... w rzeczywistości może to być zbyt niska jak na ten czas. W każdym razie funkcja akceptuje listę ciągów znaków.

def f(i):
 Z=range;r=map(__import__('fractions').Fraction,i);R=r[1:];n=len(R);L=[[[1]*n,[0]]];g=0
 for m,p in L: 
  for d in([v/3**i%3for i in Z(n)]for v in Z(3**n)):
    try:x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]>0);L+=[[[m[i]-x*R[i]*d[i]for i in Z(n)],[p[0]+x]+p]]
    except:g|=p[0]-r[0]in p
 return g

Nieco zoptymalizowana wersja może zakończyć testy w ciągu kilku minut. Może to jednak nadal być powolne w przypadku niemożliwego przypadku n = 5 .

def fLessslow(i):
 Z=range
 r=map(__import__('fractions').Fraction,i)
 R=r[1:]
 n=len(R)
 L=[((1,)*n,(0,))]
 ls = set(L)
 for m,p in L: 
  if p[0]-r[0]in p: return 1
  for d in([v/3**i%3 for i in Z(n)]for v in Z(3**n)):
   if any(d[i] and m[i]<=0 for i in Z(n)):continue
   try:
    x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]>0)
    thing = (tuple(m[i]-x*R[i]*d[i]for i in Z(n)),(p[0]+x,)+p)
    if thing not in ls:L+=[thing];ls.add(thing)
   except:5
 return 0

print fLessslow('5/1 6/1 1/6 9/1 1/9'.split())
print fLessslow('29/6 3/2 2/3 3/5 3/7 7/5'.split())

Python 2, 331

Jest to nieco dłużej niż wersja Feersum, ale jest znacznie szybsza. Wszystkie testy trwają razem na moim laptopie około 3 sekund. Pełne poszukiwanie n = 5 zajmuje jednak około 10 minut. Część kodu jest podobna do wersji feersum, ale nie celowo skopiowałem żadnego kodu.

from fractions import*
f=Fraction
r=range
g=lambda x:h(f(x[0]),[1/f(i)for i in x[1:]],[])
def h(t,x,y):
 for i in r(1,3**len(x)):
  c=[[],[],[]]
  for j in r(len(x)):c[i/3**j%3]+=[x[j]]
  n,b,w=c
  m=min(b+[i/2 for i in w])
  if h(t,[i for i in n+[j-m for j in b]+[j-2*m for j in w]if i],[i+m for i in y]+[m]):return True
 return t in y

Stosowanie:

print g('3/4 1/1 1/1'.split())
print g('29/6 3/2 2/3 3/5 3/7 7/5'.split())
print g('2/1 3/1 5/1 7/1'.split())
print g('5/1 6/1 1/6 9/1 1/9'.split())

Wyjaśnienie:

Wyrażenie lambda g wykonuje pewne wstępne przetwarzanie danych wejściowych, na przykład konwertuje ciągi na ułamki, oddzielając czas celu od szybkości spalania i obliczając czasy spalania (= 1 / szybkość spalania).

Funkcja h dzieli wszystkie czasy wypalania x na 3 zestawy n, b i w (n oznacza non-burning, b oznacza one_end_burning i w dla oba_ends_burning). Powtarza iterację we wszystkich tych układach (z wyjątkiem układu n = x, b = [], w = []), określa bezpiecznik o najkrótszym czasie spalania (oszczędność czasu wm) i rekurencyjnie wywołuje h ze zaktualizowanymi czasami spalania. W y oszczędzam wszystkie możliwe czasy, gdy ktoś może mierzyć za pomocą bezpieczników. W wywołaniu rekurencyjnym wartości te również zostaną zaktualizowane.

Jak tylko znajdę wartość, kończy wszystkie połączenia za pomocą True.