| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
MARZER - Մարզեր |
Երկրում կա n քաղաք, որոնք համարակալված են 1-ից n թվերով։ Որոշ քաղաքներ իրար միացված են միկողմանի ճանապարհներով։ Կա n-1 հատ հիմնական ճանապարհ. նրանք i քաղաքը միացնում են i+1 քաղաքին, որտեղ i-ն փոխվում է 1-ից մինչև n-1։ Բայցի այդ կան նաև լրացուցիչ ճանապարհներ։
Երկրի թագավորը որոշեց երկիրը բաժանել մարզերի։ Նա ցանկանում է ստեղծել որքան հնարավոր է շատ մարզեր։ Բոլոր մարզերում պետք է լինեն հավասար թվով քաղաքներ։ Յուրաքանչյուր քաղաք պետք է պատկանի միայն մեկ մարզի։ Երկու A և B մարզերի համար պետք է տեղի ունենա հետևյալ պայմանը. եթե A մարզի որևէ քաղաքից B մարզի որևէ քաղաք տանող ճանապարհ կա, ապա B մարզից A մարզ տանող ճանապարհ չպիտի լինի։
Տրված է n քաղաքների թիվը, m լրացուցիչ ճանապարհները, հարկավոր է գտնել թագավորի ցանկություններին բավարարող մաքսիմալ հնարավոր մարզերի թիվը։
Մուտքը
Առաջին տողում տրված է n քաղաքների թիվը (2 ≤ n ≤ 3000)։ Հաջորդ տողերից յուրաքանչյուրում տրված է մի (x, y) թվազույգ, որը նկարագրում է հերթական ճանապարհը։
Ելքը
Ելքում հարկավոր է արտածել մի ամբողջ թիվ՝ մաքսիմալ հնարավոր մարզերի թիվը։
Օրինակ
Մուտքը. 6 3
2 1
3 2
6 4 Ելքը. 2
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2014-01-18 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Ընտրական 2007 |
թաքցնել մեկնաբանությունները
|
2019-03-11 19:19:41 Hamlet
Թեստերում քաղաք կա, որի համարը 3000-ից մեծ է։ |
|
|
2018-01-30 19:54:02
Bayc orinakum m-y tvac e 3. |
|
|
2014-02-23 08:28:20 albertg
Բայց այս օրինակում կա լրացուցիչ ճանապարհների քանակը: |
|
|
2014-01-27 18:16:27 Andreasyan
Սխալ թեստ կար, ուղղել եմ։ |
|
|
2014-01-27 16:47:19 Andreasyan
Մուտքում լրացուցիչ ճանապարհների քանակը տրված չէ։ Ներածումը պետք է անել մինչև մուտքային տվյալների ավարտը։ |
RSS