結果
問題 | No.2519 Coins in Array |
ユーザー |
![]() |
提出日時 | 2023-10-27 23:23:30 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 449 ms / 2,000 ms |
コード長 | 2,810 bytes |
コンパイル時間 | 2,931 ms |
コンパイル使用メモリ | 86,956 KB |
実行使用メモリ | 71,060 KB |
最終ジャッジ日時 | 2024-09-25 15:21:05 |
合計ジャッジ時間 | 12,847 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.HashMap;import java.util.Map;import java.util.PriorityQueue;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());String[] sa = br.readLine().split(" ");long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(sa[i]);}br.close();if (n >= 4) {PrintWriter pw = new PrintWriter(System.out);pw.println(0);for (int i = 0; i < n - 1; i++) {pw.println("1 2");}pw.flush();} else if (n == 2) {Map<Long, Integer> map0 = bunkai(a[0]);Map<Long, Integer> map1 = bunkai(a[1]);long m = (a[0] - 1) * (a[1] - 1);for (Long k : map0.keySet()) {if (map1.containsKey(k)) {m = 0;break;}}if (a[0] == 0 || a[1] == 0) {m = 0;}System.out.println(m);System.out.println("1 2");} else {Map<Long, Integer> map0 = bunkai(a[0]);Map<Long, Integer> map1 = bunkai(a[1]);Map<Long, Integer> map2 = bunkai(a[2]);Map<Long, Integer> map01 = bunkai((a[0] - 1) * (a[1] - 1));Map<Long, Integer> map12 = bunkai((a[1] - 1) * (a[2] - 1));Map<Long, Integer> map20 = bunkai((a[2] - 1) * (a[0] - 1));for (Long k : map0.keySet()) {if (map12.containsKey(k)) {System.out.println(0);System.out.println("2 3");System.out.println("1 2");return;}}for (Long k : map1.keySet()) {if (map20.containsKey(k)) {System.out.println(0);System.out.println("1 3");System.out.println("1 2");return;}}for (Long k : map2.keySet()) {if (map01.containsKey(k)) {System.out.println(0);System.out.println("1 2");System.out.println("1 2");return;}}PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.a - o2.a);for (int i = 0; i < n; i++) {Obj o = new Obj();o.i = i;o.a = (int) a[i];que.add(o);}Obj f = que.poll();long m = f.a;Obj o1 = que.poll();Obj o2 = que.poll();if (m != 0) {m = (m - 1) * (o1.a - 1);}if (m != 0) {m = (m - 1) * (o2.a - 1);}System.out.println(m);System.out.println((f.i + 1) + " " + (o1.i + 1));System.out.println("1 2");}}static class Obj {int i, a;}static Map<Long, Integer> bunkai(long n) {Map<Long, Integer> soinsu = new HashMap<>();int end = (int) Math.sqrt(n);long d = 2;while (n > 1) {if (n % d == 0) {n /= d;soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);end = (int) Math.sqrt(n);} else {if (d > end) {d = n - 1;}d++;}}return soinsu;}}