Problem Forge
Сделайте каждую переменную истинной или ложной так, чтобы в каждом дизъюнкте был хотя бы один истинный литерал. Ни в одном дизъюнкте нет больше трёх литералов.
(x₁ ∨ x₂ ∨ x₃)
∧ (¬x₁ ∨ ¬x₂ ∨ x₃)
∧ (x₁ ∨ ¬x₂ ∨ ¬x₃)
x₁ = 1, x₂ = 0, x₃ = 0
(x₁ ∨ x₂ ∨ x₃) ∧ (x₁ ∨ x₂ ∨ ¬x₃)
∧ (x₁ ∨ ¬x₂ ∨ x₃) ∧ (x₁ ∨ ¬x₂ ∨ ¬x₃)
∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃)
∧ (¬x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ ¬x₂ ∨ ¬x₃)
Ступени этого месяца
| ступень | решено, все участники | отправленные ответы, все участники | состояние |
|---|---|---|---|
| 2026-11-3SAT-12 | 0 | 0 | не решена |
| 2026-11-3SAT-11 | 0 | 0 | не решена |
| 2026-11-3SAT-10 | 0 | 0 | не решена |
| 2026-11-3SAT-09 | 0 | 0 | не решена |
| 2026-11-3SAT-08 | 1 | 1 | решена |
| 2026-11-3SAT-07 | 1 | 1 | решена |
| 2026-11-3SAT-06 | 1 | 1 | решена |
| 2026-11-3SAT-05 | 1 | 1 | решена |
| 2026-11-3SAT-04 | 1 | 1 | решена |
| 2026-11-3SAT-03 | 1 | 1 | решена |
| 2026-11-3SAT-02 | 1 | 1 | решена |
| 2026-11-3SAT-01 | 1 | 1 | решена |
| 2026-11-3SAT-00 | 1 | 1 | решена |
Войдите, чтобы видеть свой прогресс и открывать ступени.
Образцы
Пять файлов-образцов, к каждому прилагается ответ. Аккаунт не нужен. Чтобы проверить свой ответ, откройте файл на странице «Проверка».
- SAMPLE-3SAT-01.cnf · переменных: 51, дизъюнктов: 203 · ответ
- SAMPLE-3SAT-02.cnf · переменных: 69, дизъюнктов: 264 · ответ
- SAMPLE-3SAT-03.cnf · переменных: 41, дизъюнктов: 159 · ответ
- SAMPLE-3SAT-04.cnf · переменных: 58, дизъюнктов: 239 · ответ
- SAMPLE-3SAT-05.cnf · переменных: 45, дизъюнктов: 179 · ответ
Что почитать: литература по задаче 3-SAT.