루미 알고리즘

#1351브론즈Tågväxeln

PO 2014 학교 예선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Växelholm är en väldigt liten stad som ligger långt ute på landet. Den består faktiskt endast av en enda byggnad - Växelholms tågstation. Staden har också bara en invånare, nämligen tågstationens föreståndare, Lokas.

Lokas jobb går i huvudsak ut på att operera stationens manuella tågväxel, så att de två pendeltågen som passerar genom staden åker åt rätt håll. Tågen går periodiskt med n respektive m minuters mellanrum, med första avgång n och m minuter efter midnatt. Tågen åker alltså ut från stationen åt samma håll men åker sedan ut på två olika spår, som delas upp av en växel.

Nu har Lokas arbetsgivare JS, Järnvägarnas Stat, bestämt att Lokas ska få lön baserat på hur många gånger han måste ändra växeln på en dag. De undrar nu hur många gånger som Lokas måste ändra på växeln under ett helt dygn (dvs 1440 minuter). Tågen avgår alltså bara under minuterna 00:00 till 23:59.

Lokas ska ändra växeln enligt reglerna:

  1. Om ett tåg ska avgå, och växeln är fel inställd, måste Lokas ändra växeln till rätt spår.
  2. Om båda tåg ska avgå samma minut, så avgår först det tåg som växeln är inställd för, och sedan ska Lokas ändra växeln till det andra tågets spår.

I början är växeln inställd på spåret för det tåg som avgår först.

Skriv ett program som beräknar hur många gånger som Lokas måste ändra växeln under ett helt dygn.

Indata

På första raden står två heltal n och m (1 ≤ n, m ≤ 1399, n ≠ m), perioderna för tågens avgång angivna i minuter.

Utdata

Skriv ut ett heltal, minsta antalet gånger som Lokas måste ändra växeln.

GruppPoängvärdeGränser
130Två tåg kommer aldrig vid samma tidpunkt
270Inga ytterligare begränsingar.

예제

예제 1

입력
500 1000
출력
1

예제 2

입력
719 720
출력
2

출처 표기

출처: Programmeringsolympiaden 2014년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.