PKU Judge Online 3061 Subsequence

■3061 Subsequence

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p3061;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    int n, s;
    int[] a;

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            n=sc.nextInt();
            s=sc.nextInt();
            a=new int[n];
            for(int i=0; i<n; i++)
                a[i]=sc.nextInt();
            println(cal()+"");
        }
    }

    int cal(){
        int res=n+1;
        int p=0, q=0, sum=0;

        for(;;){
            while(q<n&&sum<s)
                sum+=a[q++];
            if(sum<s)
                break;
            res=Math.min(res, q-p);
            sum-=a[p++];
        }
        return res%(n+1);
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 2456 Aggressive cows

■2456 Aggressive cows

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p2456;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    int n, c;
    int[] a;

    void run(){
        n=sc.nextInt();
        c=sc.nextInt();
        a=new int[n];
        for(int i=0; i<n; i++)
            a[i]=sc.nextInt();
        Arrays.sort(a);

        int low=0, up=INF;

        for(int i=0; i<100; i++){
            int mid=(low+up)/2;
            if(C(mid))
                low=mid;
            else
                up=mid;
        }
        println(""+low);
    }

    boolean C(int x){
        int last=0;
        for(int i=1; i<c; i++){
            int next=last+1;
            while(next<n&&a[next]-a[last]<x)
                next++;
            if(next==n)
                return false;
            last=next;
        }
        return true;
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3723 Conscription

■3723 Conscription

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p3723;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    int[] p, rank;

    void run(){
        int t=Integer.parseInt(sc.next());
        for(int k=0; k<t; k++){
            int n=Integer.parseInt(sc.next());// girl
            int m=Integer.parseInt(sc.next());// boy
            int r=Integer.parseInt(sc.next());
            E[] es=new E[r];
            for(int i=0; i<r; i++){
                int x=Integer.parseInt(sc.next());
                int y=Integer.parseInt(sc.next())+n;
                int d=Integer.parseInt(sc.next());
                es[i]=new E(x, y, d);
            }
            Arrays.sort(es, new Comparator<E>(){
                public int compare(E e1, E e2){
                    return e2.d-e1.d;
                }
            });

            p=new int[n+m];
            rank=new int[n+m];
            for(int i=0; i<n+m; i++)
                p[i]=i;
            int sumD=0;
            for(E e : es){
                // println(e.d+"");
                if(find(e.x)!=find(e.y)){
                    sumD+=e.d;
                    union(e.x, e.y);
                }
            }
            int ans=10000*(n+m)-sumD;
            println(""+ans);
        }
    }

    void union(int x, int y){
        x=find(x);
        y=find(y);
        if(rank[x]<rank[y]){
            p[x]=y;
        }else{
            p[y]=x;
            if(rank[x]==rank[y]){
                rank[x]++;
            }
        }
    }

    int find(int x){
        if(p[x]!=x)
            p[x]=find(p[x]);
        return p[x];
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }

    class E{
        int x, y;
        int d;

        E(int x, int y, int d){
            this.x=x;
            this.y=y;
            this.d=d;
        }
    }
}

PKU Judge Online 1182 食物链

■1182 食物链

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p1182;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    int[] p;
    int[] rank;

    void run(){
        int n=Integer.parseInt(sc.next());
        int k=Integer.parseInt(sc.next());
        p=new int[3*n];
        rank=new int[3*n];
        for(int i=0; i<3*n; i++)
            p[i]=i;
        int ans=0;
        for(int i=0; i<k; i++){
            int d=Integer.parseInt(sc.next());
            int x=Integer.parseInt(sc.next())-1;
            int y=Integer.parseInt(sc.next())-1;
            if(x<0||x>=n||y<0||y>=n){
                ans++;
                continue;
            }
            if(d==1){
                // x=y
                if(same(x, y+n)||same(x, y+2*n)){
                    ans++;
                }else{
                    union(x, y);
                    union(x+n, y+n);
                    union(x+2*n, y+2*n);
                }
            }else if(d==2){
                // x->y
                // x=y+n
                if(same(x, y)||same(x, y+2*n)){
                    ans++;
                }else{
                    union(x, y+n);
                    union(x+n, y+2*n);
                    union(x+2*n, y);
                }
            }
        }
        println(""+ans);

    }

    boolean same(int x, int y){
        return findSet(x)==findSet(y);
    }

    void union(int x, int y){
        x=findSet(x);
        y=findSet(y);
        if(rank[x]<rank[y]){
            p[x]=y;
        }else{
            p[y]=x;
            if(rank[x]==rank[y])
                rank[x]++;
        }
    }

    int findSet(int x){
        if(p[x]!=x)
            p[x]=findSet(p[x]);
        return p[x];
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 2431 Expedition

■2431 Expedition

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p2431;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        Stop[] stops=new Stop[n+1];
        for(int i=n-1; i>=0; i--){
            stops[i]=new Stop();
            stops[i].pos=sc.nextInt();
            stops[i].fuel=sc.nextInt();
        }
        stops[n]=new Stop();
        int l=sc.nextInt();
        int p=sc.nextInt();
        for(int i=0; i<=n; i++)
            stops[i].pos=l-stops[i].pos;
        Arrays.sort(stops, new Comparator<Stop>(){
            public int compare(Stop p1, Stop p2){
                return p1.pos-p2.pos;
            }
        });
        int pos=0;
        int ans=0;
        PriorityQueue<Integer> q=new PriorityQueue<Integer>();
        for(int i=0; i<=n; i++){
            int d=stops[i].pos-pos;
            while(p-d<0){
                if(q.isEmpty()){
                    println("-1");
                    return;
                }
                p-=q.poll();
                ans++;
            }
            p-=d;
            pos=stops[i].pos;
            q.offer(-stops[i].fuel);
        }
        println(""+ans);
    }

    class Stop{
        int pos;
        int fuel;
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3253 Fence Repair

■3253 Fence Repair

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p3253;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=1<<28;
    final double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        PriorityQueue<Long> queue=new PriorityQueue<Long>();
        for(int i=0; i<n; i++)
            queue.offer(sc.nextLong());
        long ans=0;
        for(; queue.size()>1;){
            long k1=queue.poll();
            long k2=queue.poll();
            ans+=k1+k2;
            queue.offer(k1+k2);
        }
        println(""+ans);
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3069 Saruman's Army

■3069 Saruman's Army

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p3069;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=1<<28;
    final double EPS=1e-9;

    void run(){
        for(;;){

            int r=sc.nextInt();
            int n=sc.nextInt();

            if(r==-1&&n==-1)
                break;

            int[] a=new int[n];
            for(int i=0; i<n; i++)
                a[i]=sc.nextInt();
            Arrays.sort(a);

            int ans=0;
            for(int i=0; i<n;){
                int s=a[i++];
                while(i<n&&a[i]<=s+r)
                    i++;
                int p=a[i-1];
                while(i<n&&a[i]<=p+r)
                    i++;
                ans++;
            }
            println(ans+"");
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3617 Best Cow Line

■3617 Best Cow Line

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p3617;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=1<<28;
    final double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        char[] cs=new char[n];
        for(int i=0; i<n; i++)
            cs[i]=sc.next().charAt(0);
        int l=0;
        int r=n-1;
        for(int k=1; k<=n; k++){
            boolean left=false;
            for(int i=0; l+i<=r-i; i++){
                if(cs[l+i]<cs[r-i]){
                    left=true;
                    break;
                }else if(cs[l+i]>cs[r-i]){
                    break;
                }
            }
            if(left)
                print(cs[l++]+"");
            else
                print(cs[r--]+"");
            if(k%80==0)
                println("");
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 2386 Lake Counting

■2386 Lake Counting

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p2386;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=1<<28;
    final double EPS=1e-9;

    int n, m;
    int[][] a;
    boolean[][] f;

    void run(){
        n=sc.nextInt();
        m=sc.nextInt();
        a=new int[n][m];
        f=new boolean[n][m];
        for(int j=0; j<n; j++){
            String s=sc.next();
            for(int i=0; i<m; i++){
                a[j][i]=s.charAt(i)=='.'?0:1;
            }
        }
        int ans=0;
        for(int j=0; j<n; j++){
            for(int i=0; i<m; i++){
                if(a[j][i]==1&&!f[j][i]){
                    ans++;
                    visit(i, j);
                }
            }
        }
        println(ans+"");
    }

    void visit(int x, int y){
        f[y][x]=true;
        for(int j=-1; j<=1; j++){
            int y2=y+j;
            if(y2<0||y2>=n)
                continue;
            for(int i=-1; i<=1; i++){
                int x2=x+i;
                if(x2<0||x2>=m)
                    continue;
                if(a[y2][x2]==1&&!f[y2][x2]){
                    visit(x2, y2);
                }
            }
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 1852 Ants

■1852 Ants

□Problem
プログラミングコンテストチャレンジブック参照．

□Solution
プログラミングコンテストチャレンジブック参照．

□Code

package p1852;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final double EPS=1e-9;

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            int length=sc.nextInt();
            int n=sc.nextInt();
            int earlist=0, latest=0;
            for(int i=0; i<n; i++){
                int a=sc.nextInt();
                int min=Math.min(a, length-a);
                int max=Math.max(a, length-a);
                earlist=max(earlist,min);
                latest=max(latest,max);
            }
            println(earlist+" "+latest);
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3085 Quick Change

■3085 Quick Change

□Problem
￠25,￠10,￠5,￠1の硬貨がある．￠nを最も硬貨が少なくなるように表せ．

□Solution
典型的な動的計画法．
dp[i][n]をi-1までの硬貨を使って，￠nを表す最小枚数とすると，
dp[i+1][n]=min{dp[i][n], dp[i][n-cent_i+1]+1}
ここで，cent_iは硬貨のiの価値．
dp[i][n]はnに初期化しておく．

□Code

package p3085;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int[] cents={25, 10, 5, 1};
        int n=sc.nextInt();
        for(int k=1; k<=n; k++){
            int c=sc.nextInt();
            int[] a=new int[c+1];
            for(int i=0; i<=c; i++)
                a[i]=i;
            int[] b=new int[c+1];
            for(int j=0; j<4; j++){
                for(int i=cents[j]; i<=c; i++){
                    int s=i-cents[j];
                    if(a[s]+1<=a[i]){
                        a[i]=a[s]+1;
                        b[i]=j;
                    }
                }
            }
            int[] count=new int[4];
            for(;;){
                count[b[c]]++;
                c-=cents[b[c]];
                if(c==0)
                    break;
            }
            println(k+" "+count[0]+" QUARTER(S), "+count[1]+" DIME(S), "
                    +count[2]+" NICKEL(S), "+count[3]+" PENNY(S)");
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 1028 Web Navigation

■1028 Web Navigation

□Problem
ウェブブラウザのシミュレーションを行え．命令は以下のとおりである．
BACK: 前のページに戻る．
FORWARD: 次のページに進む．
VISIT: 指定されたURLにジャンプ．
QUIT: ブラウザを終了する．

□Solution
閲覧したページをリストに格納しておけばOK．

□Code

package p1028;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        LinkedList<String> backward=new LinkedList<String>();
        LinkedList<String> forward=new LinkedList<String>();
        String url="http://www.acm.org/";
        for(;;){
            String[] ss=sc.nextLine().split(" ");
            String s=ss[0];
            if(s.equals("VISIT")){
                backward.addFirst(url);
                forward.clear();
                url=ss[1];
                println(url);
            }else if(s.equals("BACK")){
                if(backward.size()==0)
                    println("Ignored");
                else{
                    forward.addFirst(url);
                    url=backward.removeFirst();
                    println(url);
                }
            }else if(s.equals("FORWARD")){
                if(forward.size()==0)
                    println("Ignored");
                else{
                    backward.addFirst(url);
                    url=forward.removeFirst();
                    println(url);
                }
            }else if(s.equals("QUIT")){
                break;
            }
        }
        System.out.flush();
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 1051 P,MTHBGWB

■1051 P,MTHBGWB

□Problem
省略．

□Solution
省略．

□Code

package p1051;

import java.util.*;
import java.util.Map.Entry;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        HashMap<Character, String> map1=new HashMap<Character, String>();
        map1.put('A', ".-");
        map1.put('B', "-...");
        map1.put('C', "-.-.");
        map1.put('D', "-..");
        map1.put('E', ".");
        map1.put('F', "..-.");
        map1.put('G', "--.");

        map1.put('H', "....");
        map1.put('I', "..");
        map1.put('J', ".---");
        map1.put('K', "-.-");
        map1.put('L', ".-..");
        map1.put('M', "--");
        map1.put('N', "-.");

        map1.put('O', "---");
        map1.put('P', ".--.");
        map1.put('Q', "--.-");
        map1.put('R', ".-.");
        map1.put('S', "...");
        map1.put('T', "-");
        map1.put('U', "..-");

        map1.put('V', "...-");
        map1.put('W', ".--");
        map1.put('X', "-..-");
        map1.put('Y', "-.--");
        map1.put('Z', "--..");

        map1.put('_', "..--");
        map1.put(',', ".-.-");
        map1.put('.', "---.");
        map1.put('?', "----");

        HashMap<String, Character> map2=new HashMap<String, Character>();
        for(Entry<Character, String> entry : map1.entrySet())
            map2.put(entry.getValue(), entry.getKey());

        int n=sc.nextInt();
        sc.nextLine();
        for(int t=1; t<=n; t++){
            String s=sc.nextLine();
            int len=s.length();
            String e="";
            int[] a=new int[len];
            for(int i=0; i<len; i++){
                e+=map1.get(s.charAt(i));
                a[i]=map1.get(s.charAt(i)).length();
            }
            String ans="";
            int k=0;
            for(int j=0; j<len; j++){
                String key="";
                for(int i=0; i<a[len-1-j]; i++)
                    key+=e.charAt(k++);
                ans+=map2.get(key);
            }
            println(t+": "+ans);
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3173 Parkside's Triangle

■3173 Parkside's Triangle

□Problem
省略．

□Solution
省略．

□Code

package p3173;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        int s=sc.nextInt();
        int[][] a=new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++){
                a[j][i]=s++;
                if(s==10)
                    s=1;
            }
        }
        for(int j=0; j<n; j++){
            for(int i=0; i<j; i++)
                print("  ");
            for(int i=j; i<n; i++)
                print(a[j][i]+(i==n-1?"":" "));
            println("");
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3100 Root of the Problem

■3100 Root of the Problem

□Problem
整数b，nが与えられる．aⁿがbと最も近くなるような整数aを求めよ．

□Solution
a=e^log(b)/n
なので，上式で近そうな値をとり，その周辺を探す．

□Code

package p3100;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        for(;;){
            int b=sc.nextInt();
            int n=sc.nextInt();
            if(b==0&&n==0)
                break;
            int a=(int)Math.exp(Math.log(b)/n);
            a--;
            int ans=a;
            double ansPowN=Math.pow(ans, n);
            for(int i=a;; i++){
                double iPowN=Math.pow(i, n);
                if(Math.abs(b-iPowN)<Math.abs(b-ansPowN)){
                    ans=i;
                    ansPowN=iPowN;
                }
                if(iPowN>b){
                    break;
                }
            }
            println(ans+"");
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3176 Cow Bowling

■3176 Cow Bowling

□Problem

          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5

このようなピラミッドを上から底辺までたどっていく．たどって来た数字を全て足し合わせたた合計の最大値を求めよ．

□Solution
下からDPしていく．

□Code

package p3176;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        int[][] a=new int[n][n];
        for(int j=0; j<n; j++)
            for(int i=0; i<=j; i++)
                a[j][i]=sc.nextInt();
        for(int j=n-2; j>=0; j--)
            for(int i=0; i<=j; i++)
                a[j][i]+=Math.max(a[j+1][i], a[j+1][i+1]);
        println(""+a[0][0]);
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3086 Triangular Sums

■3086 Triangular Sums

□Problem
省略．

□Solution
省略．

□Code

package p3086;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int N=sc.nextInt();
        for(int k=1; k<=N; k++){
            int n=sc.nextInt();
            int ans=0;
            for(int i=1; i<=n; i++)
                ans+=i*(i+1)*(i+2)/2;
            println(k+" "+n+" "+ans);
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}

PKU Judge Online 3077 Rounders

■3077 Rounders

□Problem
省略．

□Solution
省略．

□Code

package p3077;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 final int INF=Integer.MAX_VALUE;
 final double EPS=1e-9;

 void run(){
  for(int n=sc.nextInt(); n>0; n--){
   int m=sc.nextInt();
   int ans=1;
   for(; m/10!=0;){
    if(m%10>=5)
     m+=10;
    m/=10;
    ans*=10;
   }
   ans*=m;
   println(ans+"");
  }
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

PKU Judge Online 3030 Nasty Hacks

■3030 Nasty Hacks

□Problem
省略．

□Solution
省略．

□Code

package p3030;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 final int INF=Integer.MAX_VALUE;
 final double EPS=1e-9;

 void run(){
  for(int n=sc.nextInt(); n>0; n--){
   int r=sc.nextInt();
   int e=sc.nextInt();
   int c=sc.nextInt();
   e-=c;
   if(e>r)
    println("advertise");
   else if(e<r)
    println("do not advertise");
   else
    println("does not matter");
  }
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

PKU Judge Online 3094 Quicksum

■3094 Quicksum

□Problem
省略．

□Solution
省略．

□Code

package p3094;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        for(;;){
            String s=sc.nextLine();
            if(s.equals("#"))
                break;
            int ans=0;
            for(int i=0; i<s.length(); i++)
                if(Character.isUpperCase(s.charAt(i)))
                    ans+=(i+1)*(s.charAt(i)-'A'+1);
            println(ans+"");
        }
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}