Daş-Kağız-Qayçı müstəvisində#7322
Bu tapşırıqda, şahmat taxtasının bir küncündən digər küncünə mümkün qədər az addım ataraq keçməlisiniz.
Şahmat taxtası m sıra və n sütundan ibarətdir. Hər xanədə ya dağ, ya kağız, ya da qayçı var. Hərəkət (1, 1) xanəsindən başlayır və (m, n) istiqamətində davam edir. Hərəkət, cari mövqedən d məsafədən uzaq olmayan istənilən xanəyə keçməklə baş verir. Məsafə, xanələrin mərkəzləri arasında ölçülür: (x_1, y_1) və (x_2, y_2) xanələri arasındakı məsafə . Hər bir hərəkət, əvvəlki xanədəki əşyanı məğlub edən əşyanı ehtiva edən xanəyə edilməlidir. "Daş-Kağız-Qayçı" oyununda olduğu kimi, daş qayçını məğlub edir, qayçı kağızı məğlub edir, kağız isə daşı məğlub edir. Bir xanəyə daxil olduqda, oradakı əşyanı götürürük, beləliklə, eyni xanəni iki dəfə ziyarət etmək qadağandır.
Sahə olduqca böyükdür, buna görə də xanələrdəki əşyalar təsadüfi ədədlər generatoru ilə, daha dəqiq desək, xətti kongruent generatorla müəyyən edilir. Bu generatorun vəziyyəti 0 ilə 2^32 - 1 arasında tam ədəd olan s ilə təmsil olunur. 0 ilə r - 1 arasında növbəti təsadüfi ədədi əldə etmək üçün s := (s ∙ 1 664 525 + 1 013 904 223) mod 2^32 təyin edilir və s mod r qaytarılır. Başlanğıc vəziyyəti s girişdə verilir.
Xanələrdəki əşyalar aşağıdakı kimi müəyyən edilir. Hər bir xanə üçün {0, 1, 2} çoxluğundan təsadüfi ədəd yaradılır (yəni r = 3). Əgər bu ədəd sıfıra bərabərdirsə, xanədə daş var, əgər birə bərabərdirsə, kağız, iki halında isə qayçı var. Xanələr yuxarıdan aşağıya doğru sıra-sıra, bir sıradakı xanələr isə soldan sağa baxılır. Beləliklə, xanələrin baxış ardıcıllığı belədir: (1, 1), (1, 2), ... , (1, n), (2, 1), (2, 2), ... , (2, n), ... , (m, 1), (m, 2), ... , (m, n).
Səyahəti maksimum sürətin yarısına bərabər sürətlə düz xətt üzrə (1, 1) xanəsindən (m, n) xanəsinə keçmək üçün lazım olan vaxtdan çox olmayan müddətdə başa çatdırmaq çox vacibdir, üstəgəl üç əlavə hərəkət. Rəsmi olaraq, hərəkətlərin sayı həqiqi ədədi keçməməlidir.
Verilmiş sahə ölçüsünə, bir hərəkət üçün maksimum sıçrayış uzunluğuna və təsadüfi ədədlər generatorunun başlanğıc vəziyyətinə əsasən bütün verilmiş şərtlərə cavab verən yolu tapın.
Birinci sətir m, n, d və s ehtiva edir: sahənin hündürlüyü və eni, bir hərəkətin maksimum məsafəsi və ədədi generatorun başlanğıc vəziyyəti (100 ≤ m, n ≤ 2^16, 10 ≤ d ≤ 100, 0 ≤ s ≤ 2^32 - 1). Diqqət yetirin ki, m, n və d üçün aşağı sərhədlər kifayət qədər böyükdür.
Birinci sətirdə tapılmış yoldakı hərəkətlərin sayını k çap edin. Növbəti (k + 1) sətirdə ziyarət edilmiş xanələrin koordinatlarını baxış ardıcıllığı ilə çap edin. Əvvəlcə sıra nömrəsini, sonra sütunu çap edin.
Yolun ilk xanəsi (1, 1), sonuncusu isə (m, n) olmalıdır. Hər bir xanə bir dəfədən çox ziyarət edilməməlidir. Növbəti xanədəki əşya əvvəlki xanədəki əşyanı məğlub etməlidir. Yolun ardıcıl iki xanəsi arasındakı məsafə d-dən çox olmamalıdır və ümumi hərəkət sayı k həqiqi ədədi keçməməlidir.
Əgər bir neçə yol varsa, onlardan birini çap edin. Bütün testlərdə uzunluğu k-dən çox olmayan şərtlərə cavab verən bir yolun mövcudluğu təmin edilir.
Nümunə 1
Aşağıdakı cədvəl verilmiş nümunədə ziyarət edilən xanələrdəki s və əşyaların dəyərlərini ehtiva edir.
Kəsrin dəyəri 3.0959... bərabərdir, buna görə nümunədə doqquzdan çox olmayan hərəkət edilməlidir və hakimlər rəsmi olaraq yeddi və ya daha az hərəkətlə bir yolun mövcudluğunu təmin edirlər.