-
Notifications
You must be signed in to change notification settings - Fork 319
/
ch-2.rs
executable file
·60 lines (56 loc) · 1.5 KB
/
ch-2.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#! /bin/sh
//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x --nocapture; rm -f ${0}x ; exit
#[test]
fn test_ex1() {
assert_eq!(cutelist(2), 2);
}
#[test]
fn test_ex2() {
assert_eq!(cutelist(10), 700);
}
#[test]
fn test_ex3() {
assert_eq!(cutelist(15), 24679);
}
fn cutelist(n: usize) -> usize {
let mut tab: Vec<Vec<bool>> = Vec::new();
tab.push(Vec::new());
for _ in 1..=n {
tab.push(vec![false; n + 1]);
}
for x in 1..=n {
for y in 1..=x {
if x % y != 0 && y % x != 0 {
tab[x][y] = true;
tab[y][x] = true;
}
}
}
let mut count = 0;
let mut stackl: Vec<Vec<usize>> = vec![Vec::new()];
let mut stackc: Vec<Vec<usize>> = Vec::new();
stackc.push((1..=n).collect::<Vec<usize>>());
while stackl.len() > 0 {
let l = stackl.pop().unwrap();
let c = stackc.pop().unwrap();
if c.len() == 0 && l.len() == n {
count += 1;
} else {
let place = l.len() + 1;
for &candidate in &c {
if !tab[place][candidate] {
let mut q = l.clone();
q.push(candidate);
stackl.push(q);
stackc.push(
c.iter()
.filter(|i| **i != candidate)
.map(|i| *i)
.collect::<Vec<usize>>(),
);
}
}
}
}
count
}