<Wyślij rozwiązanie> [
0/100]
Statystyki zadaniaLiczba osob: 10
Liczba osob na 100 punktow: 5
Sredni wynik: 56
Formuły
Dostępna pamięć: 32 MB
Jak mawiają górale, są trzy rodzaje prawdy:
święta prawda, tyż prawda i ... prawda.
Najnowsze badania bajtockich logików potwierdzają to.
Badają oni wyrażenia logiczne (formuły zdaniowe)
o uproszczonej postaci nazywanej klauzulową.
Postać klauzulowa wygląda następująco:
- Formuły budujemy używając zmiennych logicznych
x1, x2,..., xn.
Zmienne te mogą przyjmować wartości prawda lub fałsz.
- Literał, to zmienna logiczna lub jej negacja,
xi lub xi (dla
1in).
- Klauzula, to koniunkcja literałów, np.
x4 x2 x3.
- Formuła, to alternatywa klauzul, np.
(x1 x2) (x1 x3) (x3).
Wartość formuły zależy od konkretnych wartości zmiennych.
Wartości zmiennych określa się za pomocą funkcji nazywanej
wartościowaniem, postaci
f : {1, 2,..., n}{prawda,fałsz},
gdzie
f (i) jest wartością nadawaną zmiennej
xi.
Wszystkich możliwych wartościowań jest
2n.
Dla konkretnego wartościowania, wartością danej formuły
jest albo prawda albo fałsz.
Mówimy, że formuła jest prawdziwa,
jeśli dla każdego wartościowania jej wartością jest prawda.
Powiemy, że formuła jest fałszywa, jeżeli dla każdego
wartościowania jej wartością jest fałsz.
Często formuła nie jest ani prawdziwa, ani fałszywa, ale jej
wartość zależy faktycznie od danego wartościowania.
Prawdziwość formuły możemy określić jako ułamek
(z zakresu od 0 do 1):
Liczba 1 odpowiada formułom prawdziwym, a 0 fałszywym.
Przykład
Formuła:
jest prawdziwa dla czterech spośród ośmiu możliwych wartościowań.
Tak więc jest ona prawdziwa w połowie.
Zadanie
Dysponujesz 11 zestawami danych umieszczonymi w
tym archiwum.
Każdy zestaw jest zapisany w osobnym pliku:
fork.in,
gdzie
k jest numerem zestawu (
0k10).
Plik
for0.in zawiera dane zgodne z powyższym przykładem.
Napisz program, który na wejściu otrzymuje dokładnie jedną
liczbę całkowitą
k (
0k10) i wypisuje dokładnie
jeden wiersz wyjścia, zawierający przybliżoną prawdziwość
formuły podanej w
k-tym zestawie danych.
Prawdziwość powinna być wypisana w postaci
ułamka dziesiętnego, obliczonego ze względną dokładnością
3%. To znaczy, jeśli prawdziwość formuły to
p, a jej obliczone
przybliżenie to
p', to musi zachodzić
| p' - p|0.03p.
Opis pojedynczego pliku wejściowego
W pierwszym wierszu wejścia znajdują się dwie dodatnie
liczby całkowite
n i
m,
1n100,
1m100,
oddzielone pojedynczym odstępem.
Zmienne logiczne, które mogą pojawiać się w formule to
x1, x2,..., xn.
Formuła składa się z
m klauzul, opisanych w kolejnych
m wierszach,
po jednej w wierszu.
Każdy z tych wierszy zawiera liczby całkowite pooddzielane pojedynczymi
odstępami.
Pierwsza z tych liczb,
l,
1ln, to liczba literałów
tworzących klauzulę.
Dalej w wierszu znajduje się
l liczb całkowitych reprezentujących
kolejne literały klauzuli.
Są to liczby różne od zera, z zakresu od
- n do
n.
Liczba
i (dla
1in) reprezentuje
xi, a
liczba
- i reprezentuje
xi.
Przykład
Dla danych wejściowych:
0
poprawną odpowiedzią jest:
0.5
Uwaga
Akceptowanymi odpowiedziami do przykładowego testu są również:
0.485, 0.498, 0.51, 0.515.
Autor zadania: Marcin Stefaniak.
<Wyślij rozwiązanie> [
0/100]