Pertanyaan Algoritma Toilet Seat


Mari kita mengambil beberapa rumah biasa dengan seorang pria, yang harus pergi ke toilet setiap n menit, membutuhkan kursi untuk berdiri, dan seorang wanita, yang harus melakukannya setiap saat m menit, membutuhkan tempat duduk untuk turun. Apakah ada kemungkinan untuk membuat O(1) Algoritma yang akan menghasilkan jumlah gerakan toilet duduk yang tepat untuk suatu periode tertentu X menit? Ada dua input tambahan yang berbeda:
1. Pria itu selalu meninggalkan kursi setelah berkunjung.
2. Pria itu selalu meletakkan tempat duduk setelah kunjungan.

Kesimpulan: dalam kehidupan nyata (yang melibatkan n menjadi jauh lebih dari m, dengan X-> tak terhingga), terbukti bahwa tidak ada perbedaan dalam sejumlah gerakan kursinya.
 Tetapi jika seorang pria melakukannya lebih sering, maka seorang wanita, itu akan memperpanjang hidup kursi jika dia hanya akan meninggalkan kursi, tetapi apakah ini salah satu dari mereka (atau keduanya) mungkin harus menemui dokter.
Sekarang saya tahu apa yang terbaik untuk kursi itu sendiri, tetapi orang yang membuat lebih banyak gerakan - adalah pertanyaan lain (yang seharusnya tidak diminta).


32
2018-01-22 00:20


asal


Jawaban:


Untuk 2, jawabannya adalah 2*floor(X/n). Pria itu akan selalu pergi ke kamar mandi dengan dudukan toilet turun dan meninggalkannya. Wanita itu tidak akan pernah meletakkannya, karena itu hanya ketika pria itu pergi ke kamar mandi.

1 sedikit lebih rumit.

EDIT: Duh. Untuk 1, jawabannya adalah 2*floor(X/m). Toilet duduk hanya transisi ketika wanita pergi ke kamar mandi.

EDIT2: Ditambah atau minus keadaan awal toilet.

EDIT3: Jawaban saya untuk 1 hanya benar jika m>=n. Saya akan mencari tahu sisanya nanti.

EDIT4: Jika n>=2m, maka itu 2*floor(X/n), karena kursi hanya akan bertransisi ketika pria itu buang air kecil. Jika n>mSaya percaya jawabannya juga 2*floor(X/n), tapi saya harus menghitung matematika.

EDIT5: Jadi, untuk 2m>n>m, tempat duduk transisi ketika pria pergi kencing setelah wanita dan sebaliknya. Urutan kunjungan pria / wanita berulang setiap least_common_multiple(m, n) menit, jadi kita hanya perlu memikirkan apa yang terjadi dalam periode waktu itu. Satu-satunya waktu duduk tidak transisi ketika pria menggunakannya adalah jika dia berhasil mengunjunginya dua kali berturut-turut. Mengingat bahwa wanita itu sedang berkunjung lebih lebih sering daripada pria itu, di antara setiap pria yang dikunjungi setidaknya ada satu kunjungan wanita. (Dua kali di awal atau akhir.)

Jawaban 1 kemudian menjadi: (n>m ? 2*floor(X/n) : 2*floor(X/m)) + (remainder(X/n) > remainder(X/m) ? 1 : 0). Atau semacam itu.


7
2018-01-22 02:26



Ya, ada algoritma O (1) dasar.

Saya mulai dengan asumsi kedua orang mulai "berdetak" pada t = 0. Saya percaya solusinya harus digeneralisasikan ke waktu mulai yang berbeda, tetapi tidak sulit untuk memperpanjang dari satu "ujung bebas" dari garis waktu ke dua ujung.

Asumsikan n <= m.

Maka garis waktu kami terlihat seperti ini (sebuah 'x' menandai 'langkah', bukan kunjungan)

  0     m    2m    ..              t-t%m  t
  +-----+-----+-----+-----+-----+-----+--o
W x     x     x     x     x     x     x 
M x  x    x    x       x     x    x     x?

Jadi, wanita itu pergi ke lantai (t / m) kali, dan di antara setiap kali wanita itu pergi - dalam interval setengah terbuka (a*m,*m+m] -  Pria itu setidaknya sekali, dengan demikian membalik kursi sekali. untuk setiap kali dia membalik tempat duduk dalam selang waktu tertentu, dia juga membukanya sekali. Namun, dia mungkin akan pergi sekali lagi setelahnya perjalanan terakhirnya, tergantung pada waktu relatif mereka, yang dapat Anda hitung berdasarkan t modulo masing-masing periode.

total_moves = floor(t/m) * 2 + (t%m < t%n ? 1 : 0)

Sekarang untuk kasus n> m.

Peran wanita dan pria dibalik ... interval setengah terbuka [an, an+n) akan selalu melibatkan dua langkah. Pengingat dari garis adalah [t-t% n, t), di mana pria itu pergi sekali di awal, (yang +1 bergerak, tapi kami menghitung +2 untuk gerakan kedua orang pada t = 0, yang mungkin harus dibuang) dan wanita itu pergi jika dia memiliki waktu yang sama atau kurang dari yang dia lakukan

total_moves = floor(t/n) * 2 - 1 + (t%m >= t%n ? 1 : 0)

14
2018-01-21 23:14



Ya, setidaknya ketika implementasi dapat mengasumsikan bahwa siklus untuk seorang pria dan seorang wanita sudah diketahui sebelumnya dan bahwa itu tidak berubah:

Mulailah dengan kelipatan paling umum dari siklus waktu pria / wanita (lcm). Precalculate gerakan untuk periode waktu ini (lcm_movements). Sekarang Anda hanya perlu berurusan dengan masukan Anda time modulo lcm. Untuk ini, Anda cukup menyusun tabel panjang tetap yang berisi jumlah gerakan untuk setiap menit.

Mengingat bahwa time dan lcm adalah bilangan bulat dalam Java / C / C ++ / C # perhitungan sebenarnya mungkin ini:

return ( time / lcm ) * lcm_movements + movements[ time % lcm ];

4
2018-01-25 10:30



Asumsi:

  • kita mulai di t = 0 dengan dudukan toilet turun
  • jika pria dan wanita tiba pada saat yang sama, maka wanita pertama.

Biarkan LastLadyTime: = floor (X / m) * m dan lastManTime: = floor (X / n) * n. Mereka mewakili waktu terakhir penggunaan toilet. Ekspresi (lastLadyTime> lastManTime) sama dengan (X% m <X% n) karena dengan definisi X% m = X - lastLadyTime dan X% n = X - lastManTime.

Kasus: pria meninggalkan kursi ke bawah
Wanita itu tidak pernah harus pindah tempat duduk tetapi dia selalu perlu mengangkatnya. Karenanya floor(X/n).

Kasus: Pria meninggalkan kursi, n == m
Dia akan selalu perlu mengangkatnya dan dia akan selalu perlu menekannya kecuali pada penggunaan toilet pertama ketika dia tidak harus melakukan apa-apa. Karenanya 2*floor(X/n) - (X < n ? 0 : 1)

Kasus: Pria meninggalkan kursi, n> m
Setiap kali dia menggunakannya, dia perlu mengangkatnya. Dia hanya perlu menekannya sekali setelah dia menggunakannya. Ini terjadi sepanjang waktu kecuali di akhir jika waktu habis sebelum dia menggunakan toilet setelahnya. Oleh karena itu kita harus minus 1 jika lastManTime> = lastLadyTime (ingat, wanita pertama). Oleh karena itu 2 * lantai (X / n) - (lastManTime> = lastLadyTime? 1: 0) = 2*floor(X/n) - (X%n <= X%m ? 1 : 0)

Kasus: laki-laki meninggalkan tempat duduk, n <m
Mirip dengan n> m. Setiap kali dia menggunakannya, dia perlu menekannya. Dia hanya perlu mengangkatnya sekali setelah dia menggunakannya. Ini terjadi sepanjang waktu kecuali pada akhirnya jika waktu habis sebelum dia harus menggunakan toilet setelahnya. Oleh karena itu kita harus minus 1 jika lastManTime <lastLadyTime. Juga satu perbedaan adalah dia harus mengangkat kursi pertama kali. Maka 2 * floor (X / m) - (lastManTime <lastLadyTime? 1: 0) + (X <n? 0: 1) = 2*floor(X/m) - (X%n > X%m ? 1 : 0) + (X < n ? 0 : 1)


2
2018-01-21 23:19



Jika semua variabel menit adalah bilangan bulat maka Anda dapat melakukannya seperti ini:

int toilet_seat_movements = 0;
bool seat_up = false;

for (i = 0; i <= total_minutes; i++)
{
    if (seat_up)
    {
        if (i % woman_minutes == 0)
            toilet_seat_movements++;
    }
    else
    {
        if (i % man_minutes == 0)
            toilet_seat_movements++;
    }
}

return toilet_seat_movements;

0