apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

polauto Policijas auto 1 sek.


 Uzdevums

Kādā pilsētā ir N ielas Ziemeļu-Dienvidu virzienā un N ielas Austrumu-Rietumu virzienā. Ielas katrā no virzieniem ir numurētas pēc kārtas ar skaitļiem no 1 līdz N - Ziemeļu-Dienvidu virziena ielas ir numurētas virzienā no Rietumiem uz Austrumiem, bet Austrumu-Rietumu virziena ielas ir numurētas virzienā no Ziemeļiem uz Dienvidiem. Attālums starp divām blakus esošām viena virziena ielām ir 1. Katru ielu krustojumu apzīmē ielu numuru pāris (Austrumu-Rietumu ielas numurs, Ziemeļu-Dienvidu ielas numurs). Ja N=6, ielu novietojums redzams zīmējumā:

Pilsētā ir divi policijas auto - policijas auto 1 un policijas auto 2. Darba dienas sākumā policijas auto 1 atrodas krustojumā (N,N), bet policijas auto 2 - krustojumā (1,1).

Ielu krustojumos mēdz notikt satiksmes negadījumi. Kad policijas centrāle saņem ziņu par satiksmes negadījumu, tā nosūta vienu policijas auto uz krustojumu, kurā noticis negadījums, protokola sastādīšanai. Nekad uz vienu negadījumu netiek sūtīti vienlaicīgi abi policijas auto. Pēc protokola sastādīšanas policijas auto paliek tajā krustojumā, kurā bija noticis negadījums un gaida informāciju par nākošo negadījumu.

Izbraukšana uz negadījumu vietām notiek tieši tādā secībā, kādā tie ienākuši. Policijas priekšniecību interesē noskaidrot, kāds bija mazākais kopējais ceļa garums, ko izbraucot uz negadījumiem kopā varēja veikt abi policijas auto.

Iepriekš dotajā piemērā negadījumi ir notikuši secībā (3,5), (5,5) un (2,3). Īsākais kopējais ceļa garums (9) šajā gadījumā ir tad, ja uz pirmo un otro negadījumu izbrauc policijas auto 1, bet uz trešo policijas auto 2.

Uzrakstiet programmu, kas dotām negadījumu koordinātām atrod mazāko iespējamo nobrauktā ceļa garumu!

 
 Ievaddati

Teksta faila polauto.dat pirmajā rindā dots naturāls skaitlis N(5≤N≤1000) - katrā virzienā esošo ceļu skaits. Faila otrajā rindā dots naturāls skaitlis W(1≤W≤1000) - negadījumu skaits. Katrā no nākošajām W faila rindām dotas viena negadījuma krustojuma koordinātas - Austrumu-Rietumu ielas numurs, kam seko Ziemeļu-Dienvidu ielas numurs. Starp abiem skaitļiem ir viens tukšumsimbols. Negadījumi ir doti to notikšanas secībā.

 
 Izvaddati

Teksta faila polauto.rez vienīgajā rindā jāizvada mazākais iespējamais nobrauktā ceļa garums.

 
 Piemērs

polauto.datpolauto.rez
6
3
3 5
5 5
2 3
9

 
 Atsauces
Uzdevums izmantots Korejas informātikas olimpiādē 2003.gadā

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS