Programming Challenge -PKU-

Programming Challenge -PKU-内検索 / 「1001 Exponentiation」で検索した結果

• 全掲載問題リスト
  1000 A+B Problem? 1001 Exponentiation? 1012 Joseph 1017 Packets 1026 Cipher 1039 Pipe 1040 Transportation 1041 John s trip 1049 Microprocessor Simulation 1050 To the Max 1125 Stockbroker Grapevine 1128 Frame Stacking 1129 Channel Allocation 1130 Alien Security 1131 Octal Fractions 1144 Network 1256 Anagram 1263 Reflections 1273 Drainage Ditches 1406 A Starship Hakodate-maru 140...
• 1040 Transportation
  1040 Transportation 解答例 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 onum = sc.nextInt(); if(n==0 m==0 onum==0) break; Order[] os = new Order[onum]; for(int i=0;i onum...
• 1049 Microprocessor Simulation
  1049 Microprocessor Simulation 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ String input = sc.next(); if(input.charAt(0)== 8 ) break; Processor proc = new Processor(input); proc.execute(); proc.println(); } } } class...
• 1845 Sumdiv
  1845 Sumdiv 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1845 解答方針 いくつかの数学的事実を用いる． p1^r1 p2^r2 ... pn^rn の約数の和は (1 + p1 + ... + p1^r1)(1 + p2 + ... + p2^r2) ... (1 + pn + ... + pn^rn) とかける． フェルマーの小定理により a^(p-1) = 1 (mod p) がなりたつ． さらに， 1 + a + a^2 + ... + a^(p-2) = | when a = 0 then 1 | when a = 1 then p-1 | otherwise then 0 (mod p) がなりたつ． 解答例 import java...
• 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...
• 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 )+ これに従って再帰的下向き構文解析を行う． なお，...
• 2031 Building a Space Station
  2031 Building a Space Station 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2031 解答方針 最小全域木．今回はKruskalのアルゴリズムで解いた． 解答例 import java.io.*; import java.util.*; import java.text.*; public class Main{ public static void main(String[] args)throws IOException{ Scanner sc = new Scanner(System.in); DecimalFormat formatter = new DecimalFormat("#0.000"); int n =...
• 1039 Pipe
  1039 Pipe 解答例 import java.util.*; public class Main { static final double EPS = 1.0E-6; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; Point[] ps = new Point[2*n]; for(int i=0;i n;i++){ double x = sc.nextDouble(); ...
• 2685 Numeral System
  2685 Numeral System 解答例 import java.util.*; public class Main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i=0;i n;i++){ String s1 = sc.next(); String s2 = sc.next(); print_mcxi(mcxi_to_int(s...
• 2597 Line Segment Erase
  2597 Line Segment Erase 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2597 解答例 import java.util.*; public class Main{ static int[][][] mem; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); LineSegment ls[] = new LineSegment[n+1]; ls[0] = new LineSegment(-30000,-...
• 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 =...
• 2440 DNA
  2440 DNA 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2440 解答方針 長さn(n =3)の0,1の列で"010"，"111"を含まないもののうち，先頭の2文字が"00"のものをCn0，"01"のものをCn1，"10"のものをCn2，"11"のものをCn3とおいて，C(n+1)0，C(n+1)1，C(n+1)2，C(n+1)3をCn0，Cn1，Cn2，Cn3の式で表す．Xn = (Cn0, Cn1, Cn2, Cn3) とおくと，X(n+1) = A Xn (Aは4x4定数行列，具体的な形は省略) とかけるので，Xn = A^(n-3) X3とかける．行列の掛け算はO(log n)で実行できるので，全体...
• 2045 Molecular Formula
  2045 Molecular Formula 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2045 解答方針 文法は次のようにもかくことができる．A+はAの1回以上の繰り返しを意味する．なお，下の式では文法を記述するためのカッコは(,)と書き，記号としてのカッコは ( , ) と書いている． Molecular - 　( Atom | Atom Number | ( Molecular ) Number )+ これに従って構文解析器を設計すればよい． なお，未知の原子があったときの処理には例外処理を利用している． 解答例 import java.util.*; public class Main { public static void main(String[] args) { ...
• 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 ...
• 1606 Jugs
  1606 Jugs 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1606 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int amax = sc.nextInt(); int bmax = sc.nextInt(); int n = sc.nextInt(); Solver sol = new Solver(amax,bmax,n); ...
• 2769 Reduced ID Numbers
  2769 Reduced ID Numbers 解答例 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i=0;i n;i++){ int g = sc.nextInt(); int a[] = new int[g]; for(int j=0;j g;j++){ a[j] = sc.nextInt();...
• 1131 Octal Fractions
  1131 Octal Fractions 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1131 解答例 import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String line = sc.nextLine(); BigInteger input = new BigInteger(line.substring(2),8); BigDecimal d = new ...
• 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"); ...
• 2535 Very Simple Problem
  ...int min = 1001; int max = -1; for(int j=0;j p;j++){ rating[j] = sc.nextInt(); if(min rating[j]) min = rating[j]; if(max rating[j]) max = rating[j]; } for(int j=0;j p;j++){ if(min==rating[j]) simplest[j]++; if(max==rating[j]) hardest[j] = true; } } ...
• 1026 Cipher
  1026 Cipher 解答例 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; int a[] = new int[n]; for(int i=0;i n;i++){ a[i] = sc.nextInt() - 1; } ...
• 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 ...
• 1041 John's trip
  1041 John s trip 解答例 import java.util.*; public class Main { static final int NMAX = 1995; // 辺数の最大値 static final int MMAX = 45; //　頂点数の最大値 public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int ix, iy, iz; while(true){ ix = sc.nextInt(); iy = sc.nextInt(); ...
• 1263 Reflections
  1263 Reflections 解答例 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(); if(n==0) break; cnt++; Circle[] cs = new Circle[n]; for(int i=0;i n;i...
• 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]; ...
• 2739 Sum of Consecutive Prime Numbers
  2739 Sum of Consecutive Prime Numbers 解答例 import java.util.*; public class Main { static final int SIZE = 2000; static int[] primetable; public static void main(String[] args) { //make prime number table makePrimeTable(); //scanner Scanner sc = new Scanner(System.in); //solve int x; while((x = sc.nextInt())!=0){...
• 2227 The Wedding Juicer
  2227 The Wedding Juicer 解答例 import java.util.*; public class Main { static final int MAX = 1000000000; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int w = sc.nextInt(); int h = sc.nextInt(); int[][] b = new int[h+2][w+2]; int[...
• 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(); ...
• 1017 Packets
  1017 Packets 解答例 import java.util.*; public class Main { public static void main(String args[]){ Scanner sc = new Scanner(System.in); while(true){ int p1 = sc.nextInt(); int p2 = sc.nextInt(); int p3 = sc.nextInt(); int p4 = sc.nextInt(); int p5 = sc.nextInt(); int p6 = sc.nextInt(); if (p1 + p...
• 2637 WorstWeather Ever
  2637 WorstWeather Ever 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); TreeSet Integer yset = new TreeSet Integer (); HashMap Integer, Integer y_to_i = new HashMap Integer, Integer (); int r[] = new int[n]; f...
• 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 = ...
• 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...
• 2800 Joseph's Problem
  2800 Joseph s Problem 解答例 public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); long n = sc.nextInt(); long k = sc.nextInt(); long r = 0; /* for(int i=1;i =n;i++) r += k%i; System.out.println(r); */ long n0 = (long)Math.sqrt(n); ...
• 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; ...
• 2030 The Secret Number
  2030 The Secret Number 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2030 解答方針 典型的な動的計画法で解ける． 二次元配列valtable（valtable[i][j]はi行j列を末尾とする数字の最大値）を左上から埋めていく．その際の基本式は //table[i][j] 入力のi行j列の文字 //valtable[i][j] i行j列を末尾とする数字の最大値 if(table[i][j]が数字) then valtable[i][j] = max(valtable[i][j-1],valtable[i-1][j])*10 + table[i][j]の値; else valtable[i][j] = 0; である．i=0やj=0の場合は例外的に処理する必要があることに注意する． ...
• 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...
• 1923 Fouriers Lines
  1923 Fouriers Lines 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=1923 解答方針 交差点の数は，直線を平行な直線のグループに分けたときの各グループの直線数がわかれば計算できる．たとえば，問題文の図の状況は (8,4,2,1,1,1) という組で表現することができ，交点数は 0*8+8*4+(8+4)*2+(8+4+2)*1+(8+4+2+1)*1+(8+4+2+1+1)*1=101 と計算できる． 与えられた直線数nに対し，nを自然数の和として表す方法を列挙し，nの自然数の和への分割方法をn本の直線の平行な直線のグループへの分割方法と解釈して，交点数が与えられたものと等しくなるか調べていけばよい．なお，分割される領域数は「直線数+交点数+1」で求めることができる．問題文の「分割される領...
• 2635 The Embarrassed Cryptographer
  2635 The Embarrassed Cryptographer 解答例 import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { int prime[] = new int[80000]; prime[0] = 2; int cnt = 3; int index = 1; while(index 80000){ boolean flag = true; for(int i=0;i index;i++){ if(cnt%prime[i]==0){ ...
• 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 ...
• 1922 Ride to School
  1922 Ride to School 解答例 import java.util.*; public class Main { static final double EPS = 1.0E-9; static final double GOAL = 4500; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; double v[] = new double[n]; double t[] = new double[n]; ...
• 1050 To the Max
  1050 To the Max 解答例 import java.util.*; public class Main { public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] a = new int[n+1][n+1]; a[0][0] = 0; for(int j=1;j =n;j++) a[0][j] = 0; for(int i=1;i =n;i++) a[i][0] = 0; ...
• @wiki全体から「1001 Exponentiation」で調べる

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