Zasada włączeń i wyłączeń

02.12.2009 - Krzysztof Piecuch
TrudnośćTrudność


Podzielność

Limit czasowy: 1s; Limit pamieciowy: 32MB;

Zadanie polega na obliczeniu ile jest liczb w danym przedziale, które są podzielne przez którąś z określonych liczb.

Wejście

Pierwsza linia wejścia określa trzy liczby całkowity A, B oraz N. Ostatnie dwie określają przedział w którym będziemy szukali liczb ($ 0 \leq A \leq B \leq 1000000000 $). W kolejnych N ($ 1 \leq N \leq 10 $) wierszach znajdują się liczby $ Q_1, \ldots, Q_n $.

Wyjście

Na standardowe wyjście należy wypisać ile liczb naturalnych z przedziału  $ [A, B] $ jest podzielnych przez którąś z liczb $ Q_i $.

Przykład

Dla danych wejściowych:

3 1 10000
6
15
20

Poprawną odpowiedzią jest:

2333
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

 

 


Prostopadłościany


Limit czasowy: 5s; Limit pamięciowy: 32MB;

Dla danych N prostopadłościanów policzyć objętość powstałą po sklejeniu ich razem.

Dane wejściowe

W pierwszym wierszu znajduje się liczba N, określająca ilość prostopadłościanów ($ 1 \leq N \leq 20 $). W kolejnych N wierszach znajduje się 6 liczb całkowitych x1, y1, z1, x2, y2, z2 określające przeciwległe wierzchołki prostopadłościanu przy czym: $ x_1 \leq x_2, y_1 \leq, y_2, z_1 \leq z_2 $ oraz $ -1000000000 \leq x_1, y_1, z_1, x_2, y_2, z_2\leq 1000000000 $.

Dane wyjściowe

Objętość bryły.

Przykład

Dla danych wejściowych

2
1 1 1 3 3 3
2 2 2 4 4 4

Poprawną odpowiedzią jest:

15

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

 


Dla osób bardzo ambitnych cytuję zadanie z potyczek algorytmicznych:

Podróż

Limit czasowy: 5s; Limit pamięciowy: 32MB;

Potyczki algorytmiczne 2008

W Bajtocji znajduje sie n miast ponumerowanych od 1 do n. Miasta te są połączone siecią m dróg dwukierunkowych. Wiadomo, że każda para miast jest połączona za pomocą co najwyżej jednej drogi.

Bajtazar wyznał ostatnio, że nie wszystkie miasta są mu równie bliskie. Dokładniej, w miastach od 1 do k szczególnie miło spędza czas i podczas każdej podróży odwiedza każde z nich conajmniej raz.

Podróż Bajtazara stanowi ciąg d miast, takich że pomiędzy każdą parą kolejnych miast prowadzi droga. Podróż może zaczynać sie i kończyć w dowolnym mieście. Twoim zadaniem jest policzenie liczby różnych podróży po Bajtocji, w jakie Bajtazar może wyruszyć. Jako że lista ta może być duża, wystarczy, że znajdziesz resztę z dzielenia jej przez $ 10^9+9 $.

Wejście

Pierwszy wiersz wejścia zawiera cztery liczby całkowite n, m, k oraz d ($ 1 \leq n \leq 20 $, $ 1 \leq k \leq min(7, n) $, $ 1 \leq d \leq 1 000 000 000 $) pooddzielane pojedynczymi odstępami. Kolejne m wierszy zawiera opisy połączeń między miastami Bajtocji. Opis drogi składa się z dwóch liczb $ a_i $, $ b_i $ ($ 1 \leq a_i, b_i \leq n $, $ a_i \neq b_i $), oddzielonych pojedynczym odstępem i oznaczających numery miastpołączonych za pomocą i-tej drogi.

Wyjście

Wyjście powinno zawierać jedną liczbę całkowitą, oznaczającą liczbę różnych podróży, jakie może odbyć Bajtazar, modulo $ 10^9+9 $.

Przykład

4 4 2 3
1 2
2 3
3 1
2 4

Poprawną odpowiedzią jest

10

Wszystkie możliwe podróże:

1 -> 2 -> 1
1 -> 2 -> 3
1 -> 2 -> 4
1 -> 3 -> 2
2 -> 1 -> 2
2 -> 1 -> 3
2 -> 3 -> 1
3 -> 1 -> 2
3 -> 2 -> 1
4 -> 2 -> 1

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
3.25
Twoja ocena: Brak Ocena: 3.3 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com