Programming Challenge -PKU-

Programming Challenge -PKU-内検索 / 「2068 Nim」で検索した結果

• 2068 Nim
  2068 Nim 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2068 解答方針 動的計画法．table[i][j]には残り i+1 個で j+1 人目のターンならば，j+1人目のプレイヤーは勝利できるか否かを格納する． 解答例 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 s = sc.nextInt(); ...
• 全掲載問題リスト
  ...and Busy 2068 Nim 2069 Super Star 2140 Herd Sums 2142 The Balance 2143 Make a Sequence 2144 Leaky Cryptography 2145 Pathological Paths 2146 Confusing Login 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 Em...
• 2688 Cleaning Robot
  2688 Cleaning Robot 解答例 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); while(true){ int w = sc.nextInt(); int h = sc.nextInt(); if(w==0 h==0) break; char[][] floor = ne...
• 2067 Young, Poor and Busy
  2067 Young, Poor and Busy 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2067 解答方針 KenがHakodateを8時以降に出発したときの，各地点への到着時刻・費用（Hakodateからその地点までの往路分）のリストをDFSで求める（各地点への行きかたは複数あるので，各地地点における到着時刻・費用の組は複数ある）．ただし，既に求められた到着時刻・費用の組と比較して，到着時刻が早いか費用が安いかのどちらも成り立たないものはカットする．同様に，KeikoがTokyoを8時以降に出発したときの各地点への到着時刻・費用も求める． 次に，Kenが各地点を出発してHakodateに18時までに戻るための各地点の出発時刻・費用（その地点からHakodateまでの復路分）のリストを求める．これは枝の向き及び時間...
• 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...
• 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...
• 2042 Lagranges Four-Square Theorem
  2042 Lagranges Four-Square Theorem 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2042 解答方針 問題自体は単純ですが，時間が非常に厳しいです．平方数および二つの平方数の和で表せる数をあらかじめHashSetに登録しておくことで高速化しています． 解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Solver sol = new Solver(); while(true){ int n = sc.nextInt(); ...
• 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); ...
• 2044 Weather Forecast
  2044 Weather Forecast 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2044 解答方針 探索問題のテクニックが詰まっている良問． 一日目の雲の位置はわかっているので，その状態を根としたDFSを行う．雲を動かせる位置の候補は必ず5ヶ所（南北方向に動かすのが2通り，東西方向が2通り，不動が1通り）なので，1つの状態から5つの子状態が生まれるが，「雲の覆うマスでその日にイベントがある」「7日間連続して雲に覆われないマスがある」のどちらかが成り立つ場合は当然カットする．さらに計算時間短縮のために「すでに探索した状態」をカットすることは必須となる． さて，DFSの単位となる「状態」をどうやって定義するかであるが，「現在の日付」「現在の雲の位置」「各マスの連続日照日数」さえわかればよい．ここで，連続日照日数...
• 2683 Ohgas' Fortune
  2683 Ohgas Fortune 解答例 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int m = sc.nextInt(); for(int i=0;i m;i++){ int f = sc.nextInt(); int y = sc.nextInt(); int n = sc.nextInt(); int max = Integer.MIN_VALUE;...
• 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...
• 2032 Square Carpets
  2032 Square Carpets 解答方針 BFS+枝刈りが基本方針． 具体的には，使用したカーペットの枚数と床の状態（床の各マスの状態を保持した二次元配列）をまとめたクラスStateを作成し，これをデータ単位としてBFSを行う．BFSは，初期状態をキューに入れたあと，「キューから要素を取り出す- その要素から新しい要素を生成してキューに入れる」を終状態が現れるまで繰り返すことで実現できる． 問題は取り出した要素から新しい要素を生成する部分である．解答例では，取り出した要素の床のうち，傷がついているがまだカーペットで覆っていないマスを探し，そのマスを覆うようなカーペットの敷き方で可能なものをすべて生成している． たとえば， // 1 scratched and not covered by carpets // 0 flawless // -1 ...
• 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 ...
• 2686 Traveling by Stagecoach
  2686 Traveling by Stagecoach 解答例 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(); int a = sc.nextInt()-1; int b = sc.nextInt()-1; if(n==0 m==0 p==0) brea...
• 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){...
• 2684 Polygonal Line Search
  2684 Polygonal Line Search 解答例 import java.util.*; public class Main { private static Scanner sc; public static void main(String[] args) { sc = new Scanner(System.in); int n; while((n=sc.nextInt()) 0){ int m0 = sc.nextInt(); PolyLine tmp = new PolyLine(m0, readPoints(m0)); PolyLine rtmp = tmp.reverse(); int[] tmpcode ...
• 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 =...
• 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(); ...
• 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,-...
• 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の場合は例外的に処理する必要があることに注意する． ...
• 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...
• 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; ...
• 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)で実行できるので，全体...
• 2041 Unreliable Message
  2041 Unreliable Message 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2041 解答例 昔Cで書いたプログラムを簡単に書き換えたものなので汚いです． import java.util.*; public class Main { static void inverseJ(char st[],int n){ int i; for(i=n-1;i =0;i--){ st[i+1] = st[i]; } st[0] = st[n]; } static void inverseC(char st[],int n){ int i; st[n] = st[0]; ...
• 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) { ...
• 2043 Area of Polygons
  2043 Area of Polygons 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2043 解答方針 どのマスが塗りつぶされるかを，1行ずつ（つまり，y座標ごとに）調べていきます．多角形のうちy+EPSILONとy+1-EPSILONにはさまれた部分は複数の台形からなるので，各台形によって塗りつぶされるマスを調べていけばよいわけです．EPSILONは誤差対策のための小さな数です． 解答例 import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ //read...
• 2048 Monster Trap
  2048 Monster Trap 問題 http //acm.pku.edu.cn/JudgeOnline/problem?id=2048 解答方針 まず，ある点が多角形の内部にあるかどうかを判定する方法を知っている必要がある．これは，判定したい点を中心に，多角形の頂点を回りながら見ていき，角度の変化を足し合わせ，360度なら内側，0度なら外側と判定する．ただし，多角形が自分自身と重なりをもつような場合はこの判定法は使えないので注意（そのような図形を多角形と呼ぶかは疑問だが）． この問題では原点を囲むループあるかどうかを判定することになるのだが，そのループをどう見つけるかが問題． ここでは線分を一本ずつ追加していき，そのたびに新しくできるループについて原点を含むかどうかを判定していくというアルゴリズムで臨んだ．すべてのループに対してチェックを行うとなると大変だが，...
• @wiki全体から「2068 Nim」で調べる

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