Programming Challenge -PKU-

Programming Challenge -PKU-内検索 / 「2147 Dice Puzzle」で検索した結果

• 2147 Dice Puzzle
  2147 Dice Puzzle 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int s=0;s n;s++){ int top[][] = new int[3][3]; int front[][] = new int[3][3]; for(int i=0;i 3;i++){ for(int j=0;j 3;j++){ top[i][j] = ...
• 全掲載問題リスト
  ...in Names 2147 Dice Puzzle 2149 Inherit the Spheres 2195 Going Home 2227 The Wedding Juicer 2440 DNA 2505 A multiplication game 2535 Very Simple Problem 2597 Line Segment Erase 2632 Crashing Robots 2633 Funny Games 2635 The Embarrassed Cryptographer 2636 Electrical Outlets 2637 WorstWeather Ever 2639 Necklace Decomposition 2640 Playground 2683 Ohgas Fortune 2684 Polygonal Line ...
• 1409 77377
  1409 77377 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1409 解答方針 「単語を入力するための数字列」から「単語文字列」へのMultiMapを用意し，与えられた単語をすべて登録する．JavaではC++のようなMultiMapがないので，HashMapとArrayListの組み合わせでMultiMapを実現している． 入力数字列の解析はDFSで行う．DFSはStateクラス単位で行う．Stateクラスは「今までにマッチした単語のリスト」rwords と「まだ単語とマッチしていない入力数字列」buffer を保持する．初期状態ではrwodsは空で，bufferは入力数字列そのものである．DFSである状態をスタックから取り出したら，bufferを1文字ずつ50文字まで読み込んでいく．読み込んだ数字列がある単語の入力...
• 2143 Make a Sequence
  2143 Make a Sequence 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2143 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); int m = sc.nextInt(); int p = sc.nextInt(); if(n==0 m==0 p==0) break; Point[] input ...
• 1407 e-market
  1407 e-market 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1407 解答方針 出力は商品ごと，商人ごとに辞書順で行うことから，商品名から取引価格リストへのMap，人名から支出・収入へのMapをTreeMapで実装しておくと便利である． シミュレーションの過程では，待機売り手リスト，待機買い手リストを保持しておき，新しい売り手または買い手が来る毎にルールに従った処理を行えばよい． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ ...
• 2146 Confusing Login Names
  2146 Confusing Login Names 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2146 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; int d = sc.nextInt(); String[] input = new String[n]; ...
• 2142 The Balance
  2142 The Balance 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2142 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int a = sc.nextInt(); int b = sc.nextInt(); int d = sc.nextInt(); if(a==0 b==0 d==0) break; int x...
• 2140 Herd Sums
  2140 Herd Sums 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2140 解答例 import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int cnt = 0; for(int m=1;m =n;m++){ if(n (m*(m+1))/2) break; if(m%2==1){ if(n%m==0) cnt++; } ...
• 2145 Pathological Paths
  2145 Pathological Paths 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2145 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); int m = sc.nextInt(); if(n==0 m==0) break; Directory root = new Directory(false)...
• 2144 Leaky Cryptography
  2144 Leaky Cryptography 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2144 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i=0;i n;i++){ int[] a = new int[9]; for(int j=0;j 9;j++){ long tmp = sc.nextLong(16); ...
• 2149 Inherit the Spheres
  2149 Inherit the Spheres 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2149 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; Sphere[] sph = new Sphere[n]; for(int i=0;i n;i++){ sph[i] = n...
• 1418 Viva Confetti
  1418 Viva Confetti 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1418 解答方針 i 番目の円 Ci が上から見えるかどうかを調べるには，次のステップを踏めばよい． # ある円 Cj (j i) が存在して Cj が Ci を含むならば，Ci は上から見えないと判定できる # すべての円 Cj (j i) に対して Ci が Cj を含むか Ci と Cj が交わりを持たないならば，Ci は上から見えると判定できる # チェック点の集合を「Cj と Ck (i = j k) の交点で Ci の内部にある点」とする．あるチェック点で，どの円Cl (i l) にも覆われない点（境界上にあるときは覆われないと判定する）が存在すれば，そのチェック点は Ci の内部の点で上から見える点である...
• 2069 Super Star
  2069 Super Star 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2069 解答方針 最小包含球となりうる球は以下のいずれかである． #二点が直径の両端にある球 #三点が赤道上にある球 #四点が表面上にある球 よって，最小包含球となりうる球を列挙して，それらの球のうちすべての点を含むもので最小のものを調べればよい．数値誤差対策については 1981 Circle and Points と同様である． 三点が赤道上にある球，四点が表面上にある球の中心座標の計算は，三元一次連立方程式を解くことで行う．連立方程式の解法はクラメルの公式に基づいている． 解答例 import java.util.Scanner; public class Main { public static void main(St...
• 2195 Going Home
  2195 Going Home 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int h, w; while(true){ h = sc.nextInt(); w = sc.nextInt(); if(h==0 w==0) break; char[][] floor = new char[h][w]; for(int i=0;i h;i++){ String s...
• 1459 Power Network
  1459 Power Network 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1459 解答方針 ネットワーク最大流問題．有名問題なので，詳しいアルゴリズムはグラフ理論の教科書に譲る．ここでは概要を書いておく． 複数のソース（入口），シンク（出口）があるネットワークの最大流を考える場合は，もとのソース，シンクは単なるノードとし，新たな頂点「スーパーソース」，「スーパーシンク」をソース，シンクとするネットワークを考えればよい．このとき，スーパーソースから各「元ソース」へ，各「元シンク」からスーパーシンクへ経路をつくり，経路の容量は各「元ソース」，「元シンク」の容量とする． あとは補助ネットワークを構成して増大路を求め，補助ネットワークを更新する操作を，増大路がなくなるまで繰り返す．なお，増大路を求めるときは，BF...
• 1480 Optimal Programs
  1480 Optimal Programs 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int cnt = 0; while(true){ int n = sc.nextInt(); if(n==0) break; cnt++; int x[] = new int[n]; int y[] = new int[n]; for(int i=0;i ...
• 1485 Fast Food
  1485 Fast Food 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int cnt = 0; while(true){ int n = sc.nextInt(); int k = sc.nextInt(); if(n==0 k==0) break; int[] x = new int[n]; for(int i=0;i n;i++){ x[i] = sc....
• 1416 Shredding Company
  1416 Shredding Company 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1416 解答例 import java.util.*; public class Main { public static void main(String args[]){ Scanner sc = new Scanner(System.in); while(true){ int target = sc.nextInt(); String input = sc.next(); if(target==0 input.equals("0")) break; int inputlen = ...
• 1481 The Die Is Cast
  1481 The Die Is Cast 解答例 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int cnt = 0; while(true){ int w = sc.nextInt(); int h = sc.nextInt(); if(w==0 h==0) break; cnt++; char image[][] = new cha...
• 1415 Map of Ninja House
  1415 Map of Ninja House 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1415 解答方針 与えられる探索が普通の深さ優先探索に他ならないことに気付けば楽． 解答例 古いコードなので気をつけてください．Java1.5では警告が出ると思います． import java.io.*; import java.util.*; //内部では部屋番号は0から開始するものとして処理．出力で調整． class room{ int door[],ptr;//ドアの行き先の部屋の配列，ptrは配列をスタック的に扱うための変数 int level;//入り口からの距離 //コンストラクタ，ドア配列の大きさを部屋ごとに変えるため room(int n){ int ...
• 1460 Firefighters
  1460 Firefighters 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1460 解答方針 四則演算の電卓を作るところが勝負．あとは全探索． 四則演算の式は次のように表現できる．"A|B"は「AまたはB」，"E*"は「Eの0回以上の繰り返し」，"E+"は「Eの1回以上の繰り返し」を意味する． expr = term (( + | - ) term)* term = factor (( * | / ) factor)* factor = num | ( expr ) num = ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 )+ これに従って再帰的下向き構文解析を行う． なお，...
• 1458 Common Subsequence
  1458 Common Subesequence 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1458 解答方針 最長共通部分列問題． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String s1 = sc.next(); String s2 = sc.next(); Solver sol = new Solver(s1,s2); System.out...
• 1411 Calling Extraterrestrial Intelligence Again
  1411 Calling Extraterrestrial Intelligence Again 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1411 解答例 昔Cで書いたプログラムを書き換えたものなので汚いです． import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int[] prm = new int[20000]; makePNTable(prm); while(true){ int m = sc.nextInt(); ...
• 2047 Concert Hall Scheduling
  2047 Concert Hall Scheduling 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2047 解答方針 ホールAをi日目，ホールBをj日目まで利用したときの最大利益をmax[i][j]とし，動的計画法（表は対角線対称になる）．i = j のときに注意． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; ...
• 1482 It's not a Bug, It's a Feature!
  1482 It s not a Bug, It s a Feature! 解答例 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int cnt = 0; while(true){ int n = sc.nextInt(); int m = sc.nextInt(); if(n==0 m==0) break; cnt++; ...
• 1417 True Liars
  1417 True Liars 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1417 解答方針 "i j yes" からは i と j が同じ種族であることがわかります．"i j no" からは i と j が違う種族であることがわかります．逆に，それ以上の情報は得られません． これを利用して，島の住人を「そのグループのうち一人の種族が決まれば他の全員の種族も決まるようなグループ」に分割します．プログラム中ではStep1，Step2に該当します．こうすることで，探索空間の大きさを「2^(住人の数)」から「2^(グループの数)」に減らすことができます．グループの代表者の種族さえ決めればよいからです．ただ，これでもまだ探索空間は十分大きいので，枝刈りを適切に行う必要があります． 解答例 i...
• 1144 Network
  1144 Network 解答方針 関節点の個数を数える問題．アルゴリズムについてはグラフ理論の教科書に譲る． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = (new Scanner(sc.nextLine())).nextInt(); if(n==0) break; boolean a[][] = new boolean[n][n]; for(int i=0;i n;i++) Arrays.fill(a[i], ...
• 1484 Blowing Fuses
  1484 Blowing Fuses 解答例 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int cnt = 0; while(true){ int n = sc.nextInt(); int m = sc.nextInt(); int c = sc.nextInt(); if(n==0 m==0 c==0) break; ...
• 1414 Life Line
  1414 Life Line 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1414 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); int c = sc.nextInt(); if(n==0 c==0) break; int table[][] = new int[n+2][n+2]; ...
• 1412 Equals are Equals
  1412 Equals are Equals 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1412 解答方針 構文解析については1460 Firefightersと基本的には同じ． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ String ans = sc.nextLine(); if(ans.equals(".")) break; Polynomial anspoly =...
• 1012 Joseph
  1012 Joseph 解答例 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int ans[] = new int[14]; ans[0] = -1; for(int i=1;i 14;i++){ int c = 1; while(true){ if(proper(i, c)){ ans[i] = c; ...
• 1406 A Starship Hakodate-maru
  1406 A Starship Hakodate-maru 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1406 解答例 import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc = new Scanner(System.in); while(true){ int f = sc.nextInt(); if(f==0) break; int c = cbrt(f); int c1 = c; int c2 ...
• 1456 Supermarket
  1456 Supermarket 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1456 解答方針 「その日に売れるもので一番高いものを売る」という戦略を，10000日目から1日目まで，逆順に適用していく． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); if(n==0) System.out.println("0"); ...
• 1408 Fishnet
  1408 Fishnet 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1408 解答方針 すべての四角形の面積を計算するだけ．工夫があるのは直線の扱い方である．ここでは直線は常に ax + by + c = 0 の形で扱っている．y = ax + b の形で扱うと，y軸平行な直線を特別扱いしなければならないからだ．ax + by + c = 0 の形で扱うと確かに計算が煩雑になるが，基本的な処理をあらかじめて用意しておけば問題ないだろう． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); wh...
• 2046 Gap
  2046 Gap 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2046 解答方針 BFS．ただし同じ状態は探索しないように，一度探索した状態はHashSetに登録するようにして，登録済みの状態に達したらその時点で枝刈りするようにする． PKUではメモリ制限が厳しいので，byte型を利用するなどしてメモリ使用量をおさえている． 解答例 import java.util.*; class State{ byte table[][]; int turn; public State(byte card[][]){ int i,j,sx,sy; table = new byte[4][8]; for(i=0;i 4;i++) table[i][0...
• 1423 Big Number
  1423 Big Number 解答例 import java.util.*; public class Main { public static void main(String[] args) { final int ASIZE = 100000; Scanner sc = new Scanner(System.in); int a[] = new int[ASIZE]; double x = 0.0; a[0] = 1; for(int i=1;i ASIZE;i++){ x += Math.log10(i); a[i] = (int)x + 1; } // xl...
• 1486 Sorting Slides
  1485 Sotring Slides 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int casenum = 0; while(true){ int n = sc.nextInt(); if(n==0) break; casenum++; Rectangle[] rs = new Rectangle[n]; for(int i=0;i n;i++){ rs[i]...
• 1413 GIGA Universe Cup
  1413 GIGA Universe Cup 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1413 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double p[] = new double[9]; for(int i=0;i =8;i++) p[i] = prob(i); int n = sc.nextInt(); sc.nextLine(); for(int i=0;i n;i++){ ...
• @wiki全体から「2147 Dice Puzzle」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索