fn main() {
input! {
mut m: usize,
}
let mut ans = vec![];
let mut i = 10;
while m != 0 {
if 3usize.pow(i) <= m {
ans.push(i);
m -= 3usize.pow(i);
} else {
i -= 1;
}
}
println!("{}", ans.len());
println!("{}", ans.iter().join(" "));
}
fn main() {
input! {
n: usize,
q: usize,
mut s: Chars,
qs: [(usize, char); q],
}
let mut ans = 0;
for i in 2..n {
if s[i - 2] == 'A' && s[i - 1] == 'B' && s[i] == 'C' {
ans += 1;
}
}
for (p, c) in qs {
let p = p - 1;
if 2 <= p && is_ABC(&s, p - 2) {
ans -= 1;
} else if 1 <= p && is_ABC(&s, p - 1) {
ans -= 1;
} else if is_ABC(&s, p) {
ans -= 1;
}
s[p] = c;
if 2 <= p && is_ABC(&s, p - 2) {
ans += 1;
} else if 1 <= p && is_ABC(&s, p - 1) {
ans += 1;
} else if is_ABC(&s, p) {
ans += 1;
}
println!("{}", ans);
}
}
fn main() {
input! {
n: usize,
hs: [usize; n],
}
let mut highers = vec![n; n];
// highers[i]: iより左にありかつiより大きいもののうち最も右のindex, nならばhs[..i] < hs[i]
for i in 1..n {
let mut j = i - 1;
while j > 0 && hs[j] < hs[i] && highers[j] != n {
j = highers[j];
}
if hs[j] > hs[i] {
highers[i] = j;
}
}
lprintln!("{:?}", highers);
let mut ans = vec![0; n + 1];
for i in 0..n {
ans[highers[i]] += 1;
}
lprintln!("{:?}", ans);
let mut sum = ans[n];
for i in 0..n {
ans[highers[i]] -= 1;
sum += ans[i];
if highers[i] == n || highers[i] < i {
sum -= 1;
}
lprint!("{:?} ", ans);
println!("{}", sum);
}
}
fn insert_to_array<S>(array: &mut [S], index: usize, value: S) {
#[cold]
#[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
#[track_caller]
fn assert_failed(index: usize, len: usize) -> ! {
panic!("insertion index (is {index}) should be <= len (is {len})");
}
let len = 3;
if index > len {
assert_failed(index, len);
}
unsafe {
// infallible
// The spot to put the new value
let p = array.as_mut_ptr().add(index);
// Shift everything over to make space. (Duplicating the
// `index`th element into two consecutive places.)
ptr::copy(p, p.add(1), len - index);
// Write it in, overwriting the first copy of the `index`th
// element.
ptr::write(p, value);
}
}
fn delete_from_array<S>(array: &mut [S], index: usize) -> S {
#[cold]
#[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
#[track_caller]
fn assert_failed(index: usize, len: usize) -> ! {
panic!("insertion index (is {index}) should be <= len (is {len})");
}
let len = 3;
if index > len {
assert_failed(index, len);
}
unsafe {
// infallible
// The spot to put the new value
let p = array.as_mut_ptr().add(index);
let ret = ptr::read(p);
// Shift everything over to make space. (Duplicating the
// `index`th element into two consecutive places.)
ptr::copy(p.add(1), p, len - index);
return ret;
}
}
self.delete_balance(pos); // 根についてはここで回転やマージが行われる.
// 内部ノードである場合, 通り道全体にrotateとかしてから左側最大と交換して削除する
let mut current = self.children[pos].as_mut().unwrap();
while !current.is_leaf() {
current.delete_balance(current.size);
current = current.children[current.size].as_mut().unwrap();
}
fn main() {
input! {
n: usize,
a: [(usize, char); n],
}
let ls = a.iter().filter(|&x| x.1 == 'L').map(|x| x.0).collect::<Vec<_>>();
let rs = a.iter().filter(|&x| x.1 == 'R').map(|x| x.0).collect::<Vec<_>>();
let mut ans = 0;
for i in 1..ls.len() {
ans += ls[i].abs_diff(ls[i - 1]);
}
for i in 1..rs.len() {
ans += rs[i].abs_diff(rs[i - 1]);
}
println!("{}", ans);
}
fn main() {
input! {
n: usize,
m: usize,
edges: [(usize, usize, usize); m],
q: usize,
}
let edges = edges
.into_iter()
.map(|(a, b, c)| (a - 1, b - 1, c))
.collect::<Vec<_>>();
let mut graph = vec![vec![usize::MAX; n]; n];
for (u, v, c) in edges.iter() {
graph[*u][*v] = graph[*u][*v].min(*c);
graph[*v][*u] = graph[*v][*u].min(*c);
}
for i in 0..n {
graph[i][i] = 0;
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
if graph[i][k] == usize::MAX || graph[k][j] == usize::MAX {
continue;
}
graph[i][j] = graph[i][j].min(graph[i][k] + graph[k][j]);
}
}
}
for i in 0..n {
lprintln!("{:?}", graph[i]);
}
for _ in 0..q {
input! {
k: usize,
mut b: [usize; k],
}
let mut mi = usize::MAX;
b.sort();
for p in b.iter().map(|x| x - 1).permutations(k) {
for bits in 0..(1 << k) {
mi = mi.min(solve(&graph, &edges, &p, bits));
}
}
println!("{}", mi);
}
}
fn solve(
graph: &Vec<Vec>,
edges: &Vec<(usize, usize, usize)>,
p: &Vec,
mut bits: usize,
) -> usize {
let mut ans = 0;
let mut start = 0;
let n = graph.len();
for i in 0..p.len() {
let (from, to, cost) = edges[p[i]];
if bits % 2 == 0 {
ans += graph[start][from] + cost;
start = to;
} else {
ans += graph[start][to] + cost;
start = from;
}
bits /= 2;
}
ans += graph[start][n - 1];
ans
}
