- Nosaukums
- Cik četrstūru? (cikche)
- Laika limits
- 0.50s
- Atmiņas limits
- 128.0 MB
- Grūtība
-
52%
Definīcija
Gudrinieks Jānis aiz garlaicības lasa žurnālu "Sejas Grāmata". Tajā viņš atrada sekojošo vizuālu mīklu ar nosaukumu "Tikai 1% no gudrinieku ciema var atrisināt šo mīklu, uzzini vai esi ģēnijs!". Ir uzzīmēti n punkti, katrs no kuriem ir vai nu sarkans, vai nu zils. Daži no punktiem ir savienoti ar nogriežņiem, pie tam nav divu vienādas krāsas punktu, kas savienoti ar nogriezni. Uzdevumā tiek prasīts saskaitīt, cik bildē ir redzami četrstūri, pie tam ir zināms, ka nekādi trīs punkti neatrodas uz vienas taisnes. Kas atrisinās mīklu ātrāk – Jānis vai Jūs? (Jānim datora nav.)
Par četrstūri sauc četrus punktus a, b, c, d tādus, ka pāri a un b, b un c, c un d, d un a ir savienoti ar nogriežņiem. Nogriežņu krustojumus neuzskatām par punktiem.
Ievaddatu raksturojums
Pirmajā rindā doti divi naturāli skaitļi n un m, uzzīmēto punktu skaits un nogriežņu skaits (2 ≤ n ≤ 1 000, 1 ≤ m ≤ 250 000). Punkti ir sanumurēti ar veseliem skaitļiem no 1 līdz n. Tālāk seko m rindas, i-tā no kurām satur divus skaitļus ai un bi (1 ≤ ai , bi ≤ n, ai ≠ bi), punktu, kas savienoti ar i-to nogriezni, numuri. Garantēts, ka nekādi divi punkti nav savienoti ar vairāk kā vienu nogriezni. Garantēts, ka visus punktus var nokrāsot divās krāsās tā, ka nekādi divi vienādas krāsas punkti nav savienoti ar nogriezni.
Izvaddatu raksturojums
Jāizvada viens skaitlis – četrstūru skaits.
Paraugdati
Stdin
6 8 1 2 2 3 5 1 3 5 1 6 5 4 6 3 4 6
Stdout
5
Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.