Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

PCBARM - էլեկտրոնային սխեմաներ

Էլեկտրոնային սխեմաներում, հաղորդիչ լարերը անց են կացվում ոչ հաղորդիչ հիմքի վրա, որոնք, սովորաբար, պատրաստում են մի քանի շերտից, որպեսզի լարերը չհատվեն և կարճ միացում չառաջանա։ Սակայն, որքան շերտերը շատ են, այնքան էլեկտրոնային սխեման ավելի թանկ է։ Դրա համար արտադրողները լարանցումները շերտերում ձգտում են այնպես կազմակերպել, որ շերտերի քանակը մինիմալ լինի։

Այս խնդրում կդիտարկենք այնպիսի հիմքեր, որոնցում յուրաքանչյուր հաղորդալար պետք է միացնի հիմքի երկու հակառակ եզրերում գտնվող երկու պորտեր։ Միացումները պետք է այնպես անել, որ ընդհանուր սխեմայի արժեքը մինիմալ լինի։

Դիտարկենք, օրինակ, ձախ կողմի նկարում պատկերված հիմքը։ Եթե մի հաղորդալարով միացվեն A և B պորտերը, և մեկ այլ հաղորդալարով D և C պորտերը, ապա դա կարելի է անել մի շերտի վրա, ինչպես ցույց է տրված մեջտեղի նկարում։ Բայց, եթե պետք է միացնել A-ն C-ին, իսկ D-ն B-ին, ապա դա հնարավոր չէ անել մի շերտում, ինչպես ցույց է տրված աջ կողմի նկարում։

Պահանջվում է գրել ծրագիր, որը հաշվի, թե  W × H  չափի հիմքի վրա տրված ծայրակետերով N լարանցումներ կազմակերպելու համար առնվազն քանի շերտ է անհրաժեշտ։

 Կարող եք ենթադրել, որ հաղորդալարերի լայնությունը անհամեմատ փոքր է պորտերի միջև հեռավորությունների նկատմամբ։ Այնպես որ, ցանկացած երկու հաղորդալարերի միջև միշտ երրորդի համար տեղ կա։

Մուտքը

Առաջին տողում տրված է միացումների N (1 ≤ N ≤ 105) քանակը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են, իրարից մեկ բացակով անջատված, երկու ամբողջ Xi1 և Xi2 (0 ≤ Xij ≤ 106) թվեր, նշանակում է i-րդ հաղորդալարը պետք է միացնի (Xi1, 0) և (Xi2,H) կետերը։ Համարել, որ մուտքում տրված բոլոր  2 · N ծայրակետերը տարբեր են։

Ելքը

Ելքում պետք է արտածել մի ամբողջ թիվ՝ պահանջվող լարանցումները կազմակերպելու համար մինիմալ շերտերի քանակը։

Օրինակներ

Մուտքը.
2
1 1
3 3 Ելքը. 1
Մուտքը.
2
1 3
3 1 Ելքը. 2

Ավելացրեց.Andreasyan
Ամսաթիվ.2013-06-09
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.Բալթյան 2010

թաքցնել մեկնաբանությունները
2013-07-16 08:56:06 albertg
che
"Համարել, որ մուտքում տրված բոլոր 2 · N ծայրակետերը տարբեր են։"

Վերջին խմբագրածը. 2013-07-17 11:54:51
2013-06-16 18:34:15 Mushegh
Xi1-y karox e havasar linel Xj1-i?
(i!=j)


Վերջին խմբագրածը. 2013-06-26 13:59:04
2013-06-13 18:05:17 Andreasyan
Ուղղել եմ։
2013-06-13 01:22:08 Spar!k
erkrord testi patasxan@ vonca 1?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.