AOJ 2828: Matryoshka Doll

問題

Matryoshka Doll | Aizu Online Judge

解法

取り込まれた人形のコストを 0 として、取り込まれていない人形のコストはそのまま結果に加えるように、最小費用流のグラフを作る。

コード

import java.util.Scanner

import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer

object Main extends App {
  val in = new Scanner(System.in)

  def solve(n: Int): Long = {
    val xyz = (for (_ <- 0 until n) yield {
      Array(in.nextInt(), in.nextInt(), in.nextInt()).sorted
    }).toArray


    val source = n * 2
    val sink = source + 1
    val minimumCostFlow = new MinimumCostFlow(sink + 1)
    for {
      i <- 0 until n
      j <- 0 until n
      if i != j
      if xyz(i)(0) < xyz(j)(0)
      if xyz(i)(1) < xyz(j)(1)
      if xyz(i)(2) < xyz(j)(2)
    } {
      minimumCostFlow.addEdge(i, n + j, 1, 0)
    }
    for (i <- 0 until n) {
      minimumCostFlow.addEdge(source, i, 1, 0)
      minimumCostFlow.addEdge(i, sink, 1, xyz(i)(0) * xyz(i)(1) * xyz(i)(2))
      minimumCostFlow.addEdge(i + n, sink, 1, 0)
    }
    minimumCostFlow.calculateCost(source, sink, n)
  }

  def loop(): Unit = {
    while (true) {
      val n = in.nextInt()
      if (n == 0) {
        return
      }
      val ans = solve(n)
      println(ans)
    }
  }

  loop()

}

class Edge(val to: Int, var cap: Long, val cost: Long, val rev: Int)

class MinimumCostFlow(V: Int) {
  val graph: Array[ArrayBuffer[Edge]] = (for (_ <- 0 until V) yield new ArrayBuffer[Edge]()).toArray
  val prevV = new Array[Int](V)
  val prevE = new Array[Int](V)

  def addEdge(from: Int, to: Int, cap: Long, cost: Long): Unit = {
    graph(from).append(new Edge(to, cap, cost, graph(to).size))
    graph(to).append(new Edge(from, 0, -cost, graph(from).size - 1))
  }

  def calculateCost(source: Int, sink: Int, flow: Long): Long = {
    val INF = Long.MaxValue / 2
    var cost = 0L
    var residue = flow
    val potential = new Array[Long](V)
    while (residue > 0) {
      val dist = Array.fill[Long](V)(INF)
      dist(source) = 0
      val queue = mutable.PriorityQueue.empty[(Long, Int)](implicitly[Ordering[(Long, Int)]].reverse)
      queue.enqueue((0, source))
      while (queue.nonEmpty) {
        val p = queue.dequeue()
        val v = p._2
        if (dist(v) >= p._1) {
          for (i <- graph(v).indices) {
            val e = graph(v)(i)
            val u = e.to
            if (e.cap > 0 && dist(u) > dist(v) + e.cost + potential(v) - potential(u)) {
              dist(u) = dist(v) + e.cost + potential(v) - potential(u)
              prevV(u) = v
              prevE(u) = i
              queue.enqueue((dist(u), u))
            }
          }
        }
      }
      if (dist(sink) == INF) {
        return -1
      }

      for (v <- 0 until V) {
        potential(v) += dist(v)
      }
      var d = residue
      var v = sink
      while (v != source) {
        d = math.min(d, graph(prevV(v))(prevE(v)).cap)
        v = prevV(v)
      }
      residue -= d
      cost += d * potential(sink)

      v = sink
      while (v != source) {
        val e = graph(prevV(v))(prevE(v))
        e.cap -= d
        graph(v)(e.rev).cap += d
        v = prevV(v)
      }
    }
    return cost
  }
}

ARC082 F - Sandglass

問題

https://beta.atcoder.jp/contests/arc082/tasks/arc082_d

解法

解説動画の通りにやった。

最初に a 入っている時の t 秒後の砂の量は以下のように書ける。

この をシミュレーションしていけば良い。

コード

use std::io;
use std::str;
use std::usize;
use std::cmp;


static INF: i32 = 2000000000;

fn main() {
    let x = read_values::<i32>()[0];
    let k = read_values::<usize>()[0];
    let r = {
        let mut r = read_values::<i32>();
        r.push(INF);
        r
    };
    let q = read_values::<usize>()[0];
    let (t, a) = {
        let mut t = vec![INF; q + 1];
        let mut a = vec![INF; q + 1];
        for i in 0..q {
            let v = read_values::<i32>();
            t[i] = v[0];
            a[i] = v[1];
        }
        (t, a)
    };

    let mut y = 0;
    let mut x1 = 0;
    let mut x2 = x;
    let mut upper = true;

    let mut flat = false;
    let mut flat_height = 0;

    let mut r_head = 0;
    let mut t_head = 0;
    let mut prev_time = 0;
    while r_head < k || t_head < q {
        if r[r_head] < t[t_head] {
            // turn
            let time = r[r_head] - prev_time;
            if upper {
                y -= time;
                if y < 0 && x1 < -y {
                    x1 = -y;
                }
            } else {
                y += time;
                if y > 0 && x2 > x - y {
                    x2 = x - y;
                }
            }

            if flat {
                if upper {
                    flat_height -= time;
                } else {
                    flat_height += time;
                }
                flat_height = cmp::max(flat_height, 0);
                flat_height = cmp::min(flat_height, x);
            } else if x1 >= x2 {
                flat = true;
                if upper {
                    flat_height = 0;
                } else {
                    flat_height = x;
                }
            }

            prev_time = r[r_head];
            upper = !upper;
            r_head += 1;
        } else {
            // query
            let time = t[t_head] - prev_time;

            let mut ans = if a[t_head] < x1 {
                x1 + y
            } else if x2 < a[t_head] {
                x2 + y
            } else {
                a[t_head] + y
            };

            if upper {
                ans -= time;
            } else {
                ans += time;
            }

            if flat {
                ans = flat_height;
                if upper {
                    ans -= time;
                } else {
                    ans += time;
                }
            }

            ans = cmp::max(0, ans);
            ans = cmp::min(x, ans);
            println!("{}", ans);

            t_head += 1;
        }
    }
}

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T>
    where T: std::str::FromStr,
          T::Err: std::fmt::Debug
{
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

ARC082 E - ConvexScore

問題

https://beta.atcoder.jp/contests/arc082/tasks/arc082_c

解法

解説の通りにやった。

の意味するところを考える。これは凸包が S となるような部分集合の数である。

よって求める答えは各凸包について部分集合の数を数えていけば良いが、それは難しいので、全ての部分集合から、凸包が正の面積とならない部分集合を除けば良い。

コード

use std::io;
use std::str;
use std::usize;
use std::cmp;

fn mod_pow(x: i64, mut exp: i64, modulo: i64) -> i64 {
    let mut result = 1;
    let mut cur = x;
    while exp > 0 {
        if exp & 1 == 1 {
            result = (result * cur) % modulo;
        }
        cur = (cur * cur) % modulo;
        exp >>= 1;
    }
    result
}

fn main() {
    let modulo = 998244353;
    let n = read_values::<usize>()[0];
    let (x, y) = {
        let mut x = vec![0; n];
        let mut y = vec![0; n];
        for i in 0..n {
            let v = read_values::<i64>();
            x[i] = v[0];
            y[i] = v[1];
        }
        (x, y)
    };

    let mut ans = mod_pow(2, n as i64, modulo);
    ans -= 1;
    ans -= n as i64;
    ans = (ans + modulo) % modulo;

    // 両端がそれぞれ i, j となるような線分に乗っている点の数を数える
    for i in 0..n {
        for j in (i + 1)..n {
            let dx = x[i] - x[j];
            let dy = y[i] - y[j];

            let mut count = 0;
            let mut left = i;
            let mut right = j;
            for k in 0..n {
                let kx = x[i] - x[k];
                let ky = y[i] - y[k];
                if dx * ky - kx * dy == 0 {
                    left = cmp::min(left, k);
                    right = cmp::max(right, k);
                    count += 1;
                }
            }

            // 両端が i, j でない時はスルー
            if left != i || right != j {
                continue;
            }

            // 凸包の面積が 0 であるような部分集合のサイズ
            let subset = mod_pow(2, count, modulo) - count - 1;
            ans = (ans + modulo - subset) % modulo;
        }
    }

    println!("{}", ans);
}

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T>
    where T: std::str::FromStr,
          T::Err: std::fmt::Debug
{
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

ARC080 E - Young Maids

Rust の練習

問題

http://arc080.contest.atcoder.jp/tasks/arc080_c

解法

逆から考えて、最後に先頭に追加される 2 つの数を考える。これらを前から順番に とすると、i は偶数、j は奇数であり、かつ、 が成り立つことがわかる。よって、この条件を満たす i, j の中で が最小になり、かつ、その中で が最小になるような i, j を決めることで、先頭の 2 つは決まる。

このような が最後に残るためには、 のいずれかを満たす が全て取り除かれている必要があるが、隣り合っている数を取り除くため、これらの各区間の中で独立に取り除くことになる。

よって、解法としては、

• キューの中の区間の中で、最後まで残る が辞書順最小となるような区間を取り出す。
• の区間をキューに入れる。
• キューが空になるまで繰り返す。

コード

use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;
use std::fmt::Debug;
use std::i64::MAX;
use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
struct Candidate {
    minimum: i64,
    from: usize,
    until: usize,
}

impl Ord for Candidate {
    fn cmp(&self, other: &Candidate) -> Ordering {
        other.minimum.cmp(&self.minimum)
    }
}

impl PartialOrd for Candidate {
    fn partial_cmp(&self, other: &Candidate) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse::<usize>();
    let arr = (0..n).map(|_| { sc.parse::<i64>() - 1 }).collect::<Vec<_>>();
    let mut rev = vec![0; n];
    for i in 0..n {
        rev[arr[i] as usize] = i;
    }

    let mut even_rmq = RangeMinimumQuery::new(n);
    let mut odd_rmq = RangeMinimumQuery::new(n);
    for i in 0..n {
        if i % 2 == 0 {
            even_rmq.update(i, arr[i]);
        } else {
            odd_rmq.update(i, arr[i]);
        }
    }

    let mut ans = Vec::new();
    let mut heap = BinaryHeap::new();
    heap.push(Candidate { minimum: 0, from: 0, until: n });
    while !heap.is_empty() {
        let s: Candidate = heap.pop().unwrap();
        let from = s.from;
        let until = s.until;

        let (head, tail) = {
            let (ref rmq1, ref rmq2) = if from % 2 == 0 { (&even_rmq, &odd_rmq) } else { (&odd_rmq, &even_rmq) };
            let minimum_value = rmq1.query(from, until);
            let minimum_index = rev[minimum_value as usize];
            let pair = rmq2.query(minimum_index + 1, until);
            let pair_index = rev[pair as usize];
            (minimum_index, pair_index)
        };
        ans.push(arr[head]);
        ans.push(arr[tail]);

        for &(left, right) in &[(from, head), (head + 1, tail), (tail + 1, until)] {
            if left >= right { continue; }
            let minimum = if left % 2 == 0 { even_rmq.query(left, right) } else { odd_rmq.query(left, right) };
            heap.push(Candidate { minimum: minimum, from: left, until: right });
        }
    }

    for t in &ans { print!("{} ", t + 1); }
    println!();
}

pub struct RangeMinimumQuery {
    seg: Vec<i64>,
    n: usize,
}

impl RangeMinimumQuery {
    pub fn new(size: usize) -> RangeMinimumQuery {
        let mut m = 1;
        while m <= size {
            m *= 2;
        }
        RangeMinimumQuery {
            seg: vec![MAX; m * 2],
            n: m,
        }
    }

    pub fn update(&mut self, mut k: usize, value: i64) {
        k += self.n - 1;
        self.seg[k] = value;
        while k > 0 {
            k = (k - 1) / 2;
            self.seg[k] = cmp::min(self.seg[k * 2 + 1], self.seg[k * 2 + 2]);
        }
    }

    /// Get the minimum value in the array in the range [a, b)
    ///
    /// # Panics
    ///
    /// Panics if `a >= b`.
    pub fn query(&self, a: usize, b: usize) -> i64 {
        assert!(a < b);
        return self.query_range(a, b, 0, 0, self.n);
    }

    pub fn query_range(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> i64 {
        if r <= a || b <= l {
            return MAX;
        }
        if a <= l && r <= b {
            return self.seg[k];
        }
        let x = self.query_range(a, b, k * 2 + 1, l, (l + r) / 2);
        let y = self.query_range(a, b, k * 2 + 2, (l + r) / 2, r);
        cmp::min(x, y)
    }
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

CS Academy Round #34 Point in Kgon

復習

問題

https://csacademy.com/contest/round-34/task/point-in-kgon/

コード

import java.util.Scanner;

public class Main {

  private static final int MOD = (int) (1e9 + 7);

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    int K = in.nextInt();
    long[] x = new long[N * 2];
    long[] y = new long[N * 2];
    for (int i = 0; i < N; i++) {
      x[i] = in.nextInt();
      y[i] = in.nextInt();
    }
    int px = in.nextInt();
    int py = in.nextInt();
    for (int i = 0; i < N; i++) {
      x[i] -= px;
      y[i] -= py;
      x[i + N] = x[i];
      y[i + N] = y[i];
    }

    Combination combination = new Combination(N, MOD);
    long sum = 0;
    int bottom = 0;
    for (int i = 0; i < N; i++) {
      while (bottom + 1 < N * 2 && x[i] * y[bottom + 1] - y[i] * x[bottom + 1] >= 0) {
        bottom++;
      }

      int count = bottom - i;
      sum += combination.get(count, K - 1);
      sum %= MOD;
    }

    long ans = (combination.get(N, K) - sum + MOD) % MOD;
    System.out.println(ans);
  }

  static class Combination {

    private long[] fact;
    private long[] invFact;
    private int MOD;

    public Combination(int max, int MOD) {
      this.MOD = MOD;
      long[] inv = new long[max + 1];
      fact = new long[max + 1];
      invFact = new long[max + 1];
      inv[1] = 1;
      for (int i = 2; i <= max; i++) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
      }
      fact[0] = invFact[0] = 1;
      for (int i = 1; i <= max; i++) {
        fact[i] = fact[i - 1] * i % MOD;
      }
      for (int i = 1; i <= max; i++) {
        invFact[i] = invFact[i - 1] * inv[i] % MOD;
      }
    }

    public long get(int x, int y) {
      if (x < y) {
        return 0;
      }
      return fact[x] * invFact[y] % MOD * invFact[x - y] % MOD;
    }
  }
}

CS Academy Round #36 BBox Count

復習

問題

CS Academy

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

  private static final int MAX = 2500;

  private static long count(ArrayList<Integer> list, FenwickTree bit) {
    long ans = 0;
    int top;
    int bottom = 0;
    for (int p : list) {
      top = p;
      if (top - bottom >= 2) {
        ans += choose2Mod(bit.sum(bottom, top));
      }
      bottom = top + 1;
    }
    ans += choose2Mod(bit.sum(bottom, MAX));
    return ans;
  }

  private static long count(ArrayList<Integer> list1, ArrayList<Integer> list2, FenwickTree bit) {
    long ans = 0;
    int top;
    int bottom = 0;

    for (int i = 0, j = 0; i < list1.size() || j < list2.size(); ) {
      int p1 = i < list1.size() ? list1.get(i) : MAX;
      int p2 = j < list2.size() ? list2.get(j) : MAX;
      int p;
      if (p1 == p2) {
        p = p1;
        i++;
        j++;
      } else if (p1 > p2) {
        p = p2;
        j++;
      } else {
        p = p1;
        i++;
      }

      top = p;
      if (top - bottom >= 2) {
        ans += choose2Mod(bit.sum(bottom, top));
      }
      bottom = top + 1;
    }

    ans += choose2Mod(bit.sum(bottom, MAX));
    return ans;
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    ArrayList<Integer>[] points = new ArrayList[MAX];
    for (int i = 0; i < MAX; i++) {
      points[i] = new ArrayList<>();
    }
    for (int i = 0; i < N; i++) {
      int x = in.nextInt() - 1;
      int y = in.nextInt() - 1;
      points[x].add(y);
    }
    for (ArrayList<Integer> p : points) {
      Collections.sort(p);
    }

    long ans = 0;

    boolean[] added = new boolean[MAX];
    FenwickTree bit = new FenwickTree(MAX);
    for (int i = 0; i < MAX; i++) {
      if (points[i].isEmpty()) {
        continue;
      }

      Arrays.fill(added, false);
      bit.clear();

      for (int j = i; j < MAX; j++) {
        if (points[j].isEmpty()) {
          continue;
        }
        for (int p : points[j]) {
          if (!added[p]) {
            bit.add(p, 1);
            added[p] = true;
          }
        }

        if (i == j) {
          continue;
        }
        ArrayList<Integer> left = points[i];
        ArrayList<Integer> right = points[j];

        long total = choose2Mod(bit.sum(0, MAX));
        ans += total;
        ans -= count(left, bit);
        ans -= count(right, bit);
        ans += count(left, right, bit);
      }
    }

    System.out.println(ans);
  }


  private static long choose2Mod(long x) {
    return (x * (x - 1) >> 1);
  }

  static class FenwickTree {

    int N;
    long[] data;

    FenwickTree(int N) {
      this.N = N + 1;
      data = new long[N + 1];
    }

    void clear() {
      Arrays.fill(data, 0);
    }

    void add(int k, long val) {
      for (int x = k; x < N; x |= x + 1) {
        data[x] += val;
      }
    }

    // [0, k)
    long sum(int k) {
      if (k >= N) {
        k = N - 1;
      }
      long ret = 0;
      for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) {
        ret += data[x];
      }
      return ret;
    }

    // [l, r)
    long sum(int l, int r) {
      return sum(r) - sum(l);
    }
  }
}

CS Academy Round #34 Point in Kgon

問題

https://csacademy.com/contest/archive/task/point-in-kgon/

解法

これを見ました。
http://kmjp.hatenablog.jp/entry/2017/06/23/0930

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

  private final int MOD = (int) (1e9 + 7);
  private final Combination combination = new Combination(400001, MOD);

  private void solve(FastScanner in, PrintWriter out) {
    int N = in.nextInt();
    int K = in.nextInt();
    long[] X = new long[N * 2];
    long[] Y = new long[N * 2];
    for (int i = 0; i < N; i++) {
      X[i] = in.nextInt();
      Y[i] = in.nextInt();
    }

    int px = in.nextInt();
    int py = in.nextInt();
    for (int i = 0; i < N; i++) {
      X[i] -= px;
      Y[i] -= py;
      X[i + N] = X[i];
      Y[i + N] = Y[i];
    }

    long ans = combination.get(N, K);
    int right = 0;
    for (int left = 0; left < N; left++) {
      right = Math.max(right, left + 1);
      while (right < left + N && X[left] * Y[right] - Y[left] * X[right] >= 0) {
        right++;
      }
      ans += MOD - combination.get(right - left - 1, K - 1);
      ans %= MOD;
    }

    out.println(ans % MOD);
  }

  class Combination {

    private long[] fact;
    private long[] invFact;
    private int MOD;

    public Combination(int max, int MOD) {
      this.MOD = MOD;
      long[] inv = new long[max + 1];
      fact = new long[max + 1];
      invFact = new long[max + 1];
      inv[1] = 1;
      for (int i = 2; i <= max; i++) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
      }
      fact[0] = invFact[0] = 1;
      for (int i = 1; i <= max; i++) {
        fact[i] = fact[i - 1] * i % MOD;
      }
      for (int i = 1; i <= max; i++) {
        invFact[i] = invFact[i - 1] * inv[i] % MOD;
      }
    }

    public long get(int x, int y) {
      if (x < y || y < 0) {
        return 0;
      }
      return fact[x] * invFact[y] % MOD * invFact[x - y] % MOD;
    }
  }

  public static void main(String[] args) {
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(new FastScanner(), out);
    out.close();
  }

  private static class FastScanner {

    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) {
        return buffer[ptr++];
      } else {
        return -1;
      }
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
        ptr++;
      }
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextInt();
      }
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextLong();
      }
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) {
        array[i] = next();
      }
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) {
        array[i] = next().toCharArray();
      }
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}