Waktu yang Baik untuk Menolak

16

Pengaturan

Misalkan Anda diberi n sekering, dengan 1 ≤ n ≤ 5, yang masing-masing panjangnya satu meter, dan di mana masing-masing sekering memiliki laju pembakaran terkait N meter per D jam.

Sekering dapat dinyalakan di satu atau kedua ujungnya, kemudian padam di salah satu atau kedua ujungnya, relit, padam kembali, dll, sebanyak yang diperlukan sampai sekering dikonsumsi sepenuhnya. Anda dapat menyalakan dan memadamkan sekering secara instan, dan Anda dapat mengamati saat yang tepat sekering dikonsumsi sepenuhnya (terbakar).

Sekring tidak dapat dipotong atau dinyalakan di mana pun kecuali di ujungnya.

Pengaturan seperti itu memungkinkan sistem pengaturan waktu yang akurat tak terhingga, dengan mengukur waktu antara dua peristiwa pencahayaan / konsumsi sekering. Misalnya, mengingat dua sekering dengan laju pembakaran 1 meter per jam, Anda dapat mengukur tepat 45 menit (3/4 jam) dengan

  1. secara bersamaan: menyalakan sekering pertama di kedua ujungnya, menyalakan sekering kedua di satu ujung, dan menandai dimulainya interval waktu Anda
  2. menyalakan ujung kedua sekering kedua saat sekering pertama dikonsumsi (30 menit kemudian)
  3. menandai akhir interval waktu Anda pada saat sekering kedua dikonsumsi (15 menit kemudian)

Tantangan

Dengan jumlah fraksional jam t , dan satu set n fraksi yang mewakili laju pembakaran tepat dari n sekering, tulislah sebuah program atau fungsi yang menghasilkan / mengembalikan nilai yang sebenarnya jika t jam dapat diukur secara tepat melalui pembakaran sistematis sekering, atau nilai falsy sebaliknya.

Input ke program dapat berupa:

  • argumen baris perintah dari formulir TN/TD N1/D1 N2/D2 N3/D3 ...
  • string bentuk TN/TD N1/D1 N2/D2 N3/D3 ...dibaca dari stdinatau setara
  • string bentuk TN/TD N1/D1 N2/D2 N3/D3 ...dilewatkan sebagai argumen fungsi
  • array string yang ["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...]dilewatkan sebagai argumen fungsi

Dalam semua kasus t = TN/ TD, di mana TN, TD∈ [1.10000].

Demikian juga, dalam semua kasus: laju pembakaran untuk sekering i = N i / D i = N<i>/ D<i>, di mana N<i>, D<i>∈ [1,10] ∀ i .

Anda dapat mengasumsikan akan selalu ada antara 1 dan 5 sekering (inklusif), dan bahwa semua input valid dan dalam kisaran. Anda juga dapat mengasumsikan bahwa semua fraksi input diberikan dalam istilah terendah.

Anda tidak boleh menggunakan angka floating point dengan komponen fraksional untuk tantangan ini. Artinya, jika Anda menggunakan angka floating point di mana saja dalam aplikasi Anda, mereka hanya dapat mengambil nilai integral dengan komponen nol fraksional.

Mencetak gol

Ini adalah tantangan , oleh karena itu pengajuan kepatuhan terpendek dalam byte akan diberikan kemenangan.


Contoh Input / Output

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)

Selamat bergabung! :)

COTO
sumber
@ MartinBüttner Saya kira itu akan menjadi batasan nomor floating point.
hmatt1
2
@ MartinBüttner Saya setuju ini bukan pembatasan pada kode sumber. Saya tidak berpikir [sumber terbatas] cocok dengan pertanyaan ini karena masih berlaku.
hmatt1
@ chememagic: Saya ingin menarik perhatian pada kenyataan bahwa logika floating point tidak dapat digunakan, tetapi jika konsensusnya adalah bahwa itu bukan penggunaan tag yang tepat, saya akan menghapusnya.
COTO
Kasing
5
Lol, saya menggunakan algoritma O ((n!) ^ 3) untuk tujuan golf.
feersum

Jawaban:

8

Python 2, 305

Ini adalah versi golf. Secara praktis tidak dapat digunakan untuk n> 3 , karena kompleksitas waktu (dan ruang) seperti 3 n 2 ... sebenarnya itu mungkin terlalu rendah untuk saat itu. Lagi pula, fungsi menerima daftar string.

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

Versi yang sedikit dioptimalkan dapat menyelesaikan kasus uji dalam beberapa menit. Mungkin masih lambat untuk kasus n = 5 yang mustahil .

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())
feersum
sumber
1
Bagus, 8 upvotes untuk kode buggy: memanggil fungsi dengan contoh dalam deskripsi: print f ('3/4 1/1 1 / 1'.split ()) mengembalikan 0, meskipun seperti deskripsi mengatakan, ia dapat dipecahkan .
Jakube
@ Jakube Terima kasih telah menguji ... sangat jarang di situs ini! Sudah diperbaiki sekarang; Saya lupa di satu tempat untuk membagi dengan faktor 1 atau 2 tergantung pada berapa banyak ujung tali menyala.
feersum
3

Python 2, 331

Ini sedikit lebih lama dari versi feersum, tetapi jauh lebih cepat. Semua testcas bersama memakan waktu sekitar 3 detik di laptop saya. Pencarian lengkap untuk n = 5 membutuhkan sekitar 10 menit. Beberapa kode mirip dengan versi feersum, tetapi saya tidak sengaja menyalin kode apa pun.

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

Pemakaian:

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())

Penjelasan:

Ekspresi lambda g melakukan beberapa preprocessing input, seperti mengubah string menjadi fraksi, memisahkan waktu sasaran dari laju pembakaran dan menghitung waktu pembakaran (= 1 / laju pembakaran).

Fungsi h membagi semua waktu pembakaran x menjadi 3 set n, b dan w (n berarti non_burning, b untuk one_end_burning, dan w untuk both_ends_burning). Ia beralih ke semua pengaturan tersebut (kecuali pengaturan n = x, b = [], w = []), menentukan sekering dengan laju pembakaran terpendek (menghemat waktu dalam m), dan secara rekursif memanggil h dengan waktu pembakaran yang diperbarui. Dalam y saya menyimpan semua waktu yang memungkinkan seseorang dapat mengukur dengan menggunakan sekering. Dalam panggilan rekursif, nilai-nilai ini juga diperbarui.

Segera setelah saya menemukan nilainya, ini mengakhiri semua panggilan dengan True.

Jakube
sumber
4
Anda programmer muda Python dimanjakan dengan semua fraksi bawaan Anda dan bilangan bulat besar. Kembali ketika saya masih muda, semua yang kami miliki adalah 1dan 0itu, yang kami harus ketik satu per satu di konsol tanpa monitor. Terkadang kami tidak punya 1.
COTO