1 Востаннє редагувалося ykozolup (10.03.2018 16:29:10)

Тема: Допоможіть розв'язати задачу

Готуємося до олімпіади, учні десь роздобули задачу. Сидимо кафедрою і не можемо розв'язати бозна скільки діб(((
Задача така:
Є аналоговий годинник з трьома стрілками (секундна стрілка, хвилинна стрілка, годинникова стрілка). Ви вмієте вимірювати два кута між секундною стрілкою і двома іншими.
Напишіть програму, яка знайде якомога менший час, в який "Ніякі дві стрілки не накривають одна одну" і "Обидва кута між секундною стрілкою і двома іншими стрілками рівні".
Кількість годин на цьому годиннику не обмежується 12 годинами. Годинникова стрілка робить одне коло навколо циферблата за H годин. Хвилинна стрілка робить один повний оберт кожну годину, а секундна робить оборот кожну хвилину. О 00:00:00 усі стрілки дивляться вгору.
Вхідні дані
В одному рядку чотири цілих числа H, h, m і s. Hвказує на те, що годинник розраховано на H-годин. h, m і s задають годину, хвилину і секунду поточного часу.
Відомо, що
2 ≤ H ≤ 100,
0 ≤ h < H,
0 ≤ m < 60,
0 ≤ s < 60.
Вихідні дані
Виведіть час T, для якого якомога раніше після заданого часу виконуються умови "Ніякі дві стрілки не накривають одна одну" і "Обидва кути між секундною стрілкою і двома іншими стрілками рівні".
Для часу T рівного h0:m0:s0 (s0 секунд, m0 хвилин і h0 годин) вивести чотири невід’ємних цілих числа h0, m0, n і d в одному рядку, де n/d – нескоротний дріб, що задає s0. Для s0 рівного 0 вважати d рівним 1.
Час слід обчислювати за модулем H годин. Тобто через секунду після (H − 1): 59: 59 йде 00: 00: 00, а не H: 00: 00.

Допоможіть будь ласка, адже така задача може попастися на олімпіаді))) Заздалегідь спасибі!!!!

2

Re: Допоможіть розв'язати задачу

А яка кафедра якого вишу?

3 Востаннє редагувалося koala (10.03.2018 16:37:42)

Re: Допоможіть розв'язати задачу

Тут взагалі комп'ютер не потрібен. Рівняння діофантові, але оскільки все зациклено, а питають про найменший час, то тупим перебором до 22 значень все знаходиться через кутові швидкості.

4

Re: Допоможіть розв'язати задачу

Обидва кути між секундною стрілкою і двома іншими стрілками рівні

Мається на увазі, що кут між секундною стрілкою і годинною стрілкою рівний куту між секундною стрілкою і хвилинною стрілкою?

5

Re: Допоможіть розв'язати задачу

evgen.gizila написав:

Обидва кути між секундною стрілкою і двома іншими стрілками рівні

Мається на увазі, що кут між секундною стрілкою і годинною стрілкою рівний куту між секундною стрілкою і хвилинною стрілкою?

Так, і вони не накладаються - тобто виходить емблема Мерседеса.

6

Re: Допоможіть розв'язати задачу

Ні, шкільна кафедра інформатиків. Просто звик вже так називати. Чесно кажути не зовсім розумію, про які рівняння ви говорите(

7

Re: Допоможіть розв'язати задачу

Можете навести конкретний приклад, яке рівняння тут застосовувати?

8

Re: Допоможіть розв'язати задачу

А, шкільна і інформатиків.
Тоді добре. Бо задача насправді добре б виглядала як олімпіадна десь на 9 клас з математики.

Отже, очевидно, що ситуація, коли всі стрілки РІВНО під однаковими кутами по 120°, дещо специфічна. Для неї необхідно, щоб годинна стрілка (яка за годину робить 1/12 оберта) відставала від хвилинної (1 оберт на годину) рівно на 1/3 оберта, або щоб на стільки ж випереджала; такі ситуації, очевидно, трапляються 12*2=24 рази на добу: два рази між 0:0 та 1:0, два між 1:0 та 2:0 і т.д. Але при цьому треба, щоб секундна (60 обертів на годину) опинялася у чітко визначеному місці, на біссектрисі кута між ними. Все. що треба - розв'язати рівняння по годинній та хвилинній стрілкам і перевірити, чи буде в цей момент секундна там, де треба.
Ну, так, 2018 рік. Нікому вже не цікаво табличку на 24 рядки розписувати руками. Може, так дійсно краще.

9

Re: Допоможіть розв'язати задачу

Найтупіше рівняння зі шкільної математики: є два об'єкти, що рухаються з лінійними швидкостями, коли вони зустрінуться?

Прихований текст

X1+V1*t = X2+V2*t

Фокус у тому, що порівнняня має враховувати також те, що у нас рух зі сталими швидкостями по колу, і нас влаштує будь-яка зустріч - а отже, треба брати частини після коми від обох боків. Якщо відраховувати від годинної стрілки, то вона починає рух з точки 0, а незалежний член для інших двох стрілок - це ±1/3. Ну, і бажано це все обчислювати на Fraction... хоча точності в 1e-6, загалом, має бути цілком достатньо, навряд чи там буде така проблемна точка, де секундна пройде так близько, але точно не потрапить.

10

Re: Допоможіть розв'язати задачу

Вибачте, але я все одно зрозумів не до кінця. Чому ви берете 12, адже у нас H-годинний годинник (вибачте за тавтологію), можете показати як будуть виглядати ці рівняння для годинної та хвилинної стрілки?

11

Re: Допоможіть розв'язати задачу

Так, вибачте. Тоді, звісно, без комп'ютера не обійтися. Просто підставте швидкість годинникової стрілки в 1/H.

12

Re: Допоможіть розв'язати задачу

На жаль зараз шкільний курс математики дуже обмежений, і більшість з того, що ви написали відноситься до фізики. Я давно вже займаюся виключно інформатикою, і щоб зрозуміти все написане вище мені знадобиться багато часу) Чи не могли б ви написати сам алгоритм підрахунку. а вже від нього я буду розбиратися?
Без введення та виведення даних, а сам алгоритм, будь ласка.

13

Re: Допоможіть розв'язати задачу

У вигляді коду)))

14

Re: Допоможіть розв'язати задачу

Так, щось я сьогодні зовсім неуважний.
Там же не треба, щоб "мерседес" утворювався, а тільки найперший час, коли секундна буде на біссектрисі між іншими, а це взагалі відбудеться протягом першої ж хвилини: годинна і хвилинна трохи розійдуться, а секундна буде на ~30 секунді з дрібницями.
Отже, нам потрібен час t (в годинах)
Годинна за цей час пройде t/H обертів (оберт - це кутова одиниця, 2П чи 360°), хвилинна - t обертів, секундна - 60*t.
При цьому кут між секундною і годинною, виміряний вперед, тобто 1+t/H - 60*t, буде дорівнювати куту між хвилинною і секундною, тобто 60*t - t.
Ви зможете знайти з рівняння

1 + t/H - 60*t = 60*t - t 

значення t?
А потім треба лише представити цей час в секундах (хвилини і години там нульові).
Звісно, можливо, що "ніякі дві стрілки не накривають одна одну" - мається на увазі певний сектор, шириною, скажімо, в одну 1/60 оберту. Тоді доведеться зачекати ще одну хвилину, доки хвилинна вийде з зони годинної стрілки. Рівняння те саме, тільки на початку "2" буде.

Подякували: ykozolup1

15

Re: Допоможіть розв'язати задачу

Ой, дякую нарешті зрозумів!!! Щось у мене також день дивний видався,довго думаю. Рівняння тепер повністю зрозуміле, але от питання там просять вивести n і d. Де n/d - нескоротній дріб, який позначає секунди. Як знайти ці параметри. ДО речі пропоную декілька тестів для розуміння:

Вхідні дані:
12 0 0 0
Вихідні:
0 0 43200 1427

Вхідні дані:
2 0 39 30
Вихідні дані:
0 40 0 1

16

Re: Допоможіть розв'язати задачу

Вибачте, але з тестами щось взагалі не сходиться, в будь-якому випадку чомусь t близьке до 0.

17

Re: Допоможіть розв'язати задачу

У вас дійсно настільки не вистачає фантазії?

Прихований текст
from fractions import Fraction as Frac
from math import *

def frac_part(x):
    return x - floor(x)

def get_bissectrice_time(hours_in_day,h,m,s):
    minutes_in_hour = 60
    seconds_in_minute = 60
    seconds_in_day = hours_in_day*minutes_in_hour*seconds_in_minute
    seconds_in_hour = minutes_in_hour*seconds_in_minute
    h_speed = Frac(1,seconds_in_day)
    m_speed = Frac(1,seconds_in_hour)
    s_speed = Frac(1,seconds_in_minute)

    time = h*seconds_in_hour + m*seconds_in_minute + s

    #positions in means of rotations
    hours   = frac_part( time * h_speed ) #frac_part here is unnecessary
    minutes = frac_part( time * m_speed )
    seconds = frac_part( time * s_speed )

    # after t seconds, we'll have (in rotations)
    # hour arrow at frac_part(hours   + t * h_speed)
    # minute -||-   frac_part(minutes + t * m_speed)
    # seconds -||-  frac_part(seconds + t * s_speed)

    bissectrice = (hours+minutes)/2

    if seconds<=bissectrice:
        #s-arrow will catch position as it reaches middle between h- and m-
        #but we should check what arrow is first
        #if hour<=minutes:
            #answer will be (hours, seconds, minutes)
            #seconds+t*s_speed-hours-t*h_speed=minutes+t*m_speed-seconds-t*s_speed
            #t*(2*s_speed-h_speed-m_speed)=minutes+hours-2*seconds
            #t = (minutes+hours-2*seconds)/(2*s_speed-h_speed-m_speed)
        #else:
            #answer will be (minutes, seconds, hour)
            #seconds+t*s_speed-minutes-t*m_speed = hours-t*h_speed-seconds-t*s_speed
            #just the same formula
        t = (minutes+hours-2*seconds)/(2*s_speed-h_speed-m_speed)
    else:
        #s-arrow will catch position while being last (first next rotation) on the clockface
        #if hour<=minutes:
            #answer will be (hours, minutes, seconds) (seconds may be>1)
            #seconds+t*s_speed-minutes-t*m_speed=1+hours+t*h_speed-seconds-t*s_speed
            #t*(2*s_speed-h_speed-m_speed)=1+minutes+hours-2*seconds
            #t = (1+minutes+hours-2*seconds)/(2*s_speed-h_speed-m_speed)
        #else:
            #answer will be (minutes, hours, seconds) (seconds may be>1)
            #seconds+t*s_speed-hours-t*h_speed=1+minutes+t*m_speed-seconds-t*s_speed
            #the same again
        t = (1+minutes+hours-2*seconds)/(2*s_speed-h_speed-m_speed)

    answer_seconds = s+t
    answer_minutes = floor(m+t/seconds_in_minute)
    answer_hours   = floor(h+t/seconds_in_hour)
    #here i'd use modulus, but with fractions I'm not sure how it works, so
    while answer_seconds>=seconds_in_minute:
        answer_minutes += 1
        answer_seconds -= seconds_in_minute
    while answer_minutes>=minutes_in_hour:
        answer_hours += 1
        answer_minutes -= minutes_in_hour
    while answer_hours>=hours_in_day:
        answer_hours -= hours_in_day

    hours_position = frac_part(hours + t * h_speed)
    seconds_position = frac_part(seconds + t * s_speed)
    if hours_position == seconds_position:
        #positions overlap, get the next second answer
        answer_seconds += 1
        while answer_seconds>=seconds_in_minute:
            answer_minutes += 1
            answer_seconds -= seconds_in_minute
        while answer_minutes>=minutes_in_hour:
            answer_hours += 1
            answer_minutes -= minutes_in_hour
        while answer_hours>=hours_in_day:
            answer_hours -= hours_in_day
        return get_bissectrice_time(hours_in_day,answer_hours,answer_minutes,answer_seconds)
    return (answer_hours,answer_minutes,answer_seconds)

H, h, m, s = [int(i) for i in input().split()]
print(get_bissectrice_time(H,h,m,s)) 

Код неприбраний, місцями (де формули) спеціально щоб ви бачили, як я виводив це, місцями (де час нормалізується) - просто ліньки.
Формат виводу поправите до необхідного, там очевидно, як.

Подякували: ykozolup1

18

Re: Допоможіть розв'язати задачу

Дякую! Будемо розбиратися)))

19

Re: Допоможіть розв'язати задачу

Ще маю до вас невеличке повідомлення.
Серед тестів, я знайшов такі, що не виконуються для даного алгоритму.
Це такі як:

Вхідні      !       Вихідні
11 0 55 0 --> 0 55 0 1
5 1 7 41 --> 1 8 120 11
3 2 15 0 --> 2 15 0 1

Але при виконанні цих тестів виводяться зовсім інші значення. Цікаво, чому так?

20

Re: Допоможіть розв'язати задачу

Вибачте, ви ніби все ж таки кафедра інформатики. Вас ще й відлагодженню треба вчити? Намалюйте ці ситуації, пройдіться по алгоритму і знайдіть, що я пропустив. Схоже, треба замінити алгоритм знаходження біссектриси.