Hatena::ブログ(Diary)

nameless - ver. d.hatena


只今

2011.11.19

Problem 2

問題文


メモ

フィボナッチ数列

n12345678910
f(n)123581321345589

※ 問題文よりにあわせる

より、偶数になる項は

n = 3m - 1


実装

SBCL

※ メモ化関数ここ より拝借

(defun memoize (func)
  (let ((table (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (let ((value (gethash args table nil)))
          (unless value
            (setf value (apply func args))
            (setf (gethash args table) value))
          value))))

(defun fib(n)
  (cond ((<= n 1) 1)
        (t
         (+ (fib (- n 1)) (fib (- n 2))))))

(setf (symbol-function 'fib) (memoize #'fib))

(defun problem2()
  (let ((sum 0) (f 0) (m 1))
    (loop
      (setq f (fib (- (* 3 m) 1)))
      (if (> f 4000000) (return sum))
      (incf sum f)
      (incf m))))

(time (print (problem2)))

実行結果

4613732
Evaluation took:
  0.001 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)

Problem 10

問題文


メモ

200 万範囲以内の素数を求める -> エラトステネスの篩


実装

java
public class Problem10 {

    public void execute(int m) {
        long retval = 0L;
        boolean[] numbers = createPrimeNumbers(m);
        for(int i=0; i<=m; i++)
            if(numbers[i])
                retval += i;
        System.out.println("anser: " + retval);
    }

    boolean[] createPrimeNumbers(int m) {
        int MAX = m + 1;
        boolean[] numbers = new boolean[MAX];
        for(int i=2; i<MAX; i++)
            numbers[i] = true;
        for(int i=2; i<MAX; i++)
            if(numbers[i])
                for(int j=i*2; j<MAX; j+=i)
                    numbers[j] = false;
        return numbers;
    }

    public static void main(String[] args) {
        long s;

        s = System.currentTimeMillis();
        (new Problem10()).execute(10);
        System.out.println("time: " + (System.currentTimeMillis() - s));

        s = System.currentTimeMillis();
        (new Problem10()).execute(2000000);
        System.out.println("time: " + (System.currentTimeMillis() - s));
    }
}

実行結果

m = 10
answer: 17
time: 0 msec

m = 2000000
answer: 142913828922
time: 27 msec

Problem 5

問題文


メモ

最小公倍数を求めればいい


実装

xyzzy-lisp
(defun problem5(m)
  (do ((i 2 (1+ i)) (n 1))
	  ((> i m) n)
	(setq n (lcm n i))))

実行結果

; m = 10
(problem5 10)
2520

; m = 20
(problem5 20)
232792560

1310 : Find the Multiples

問題文



メモ



実装

java

package aoj1310;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        String[] sp;
        int n, s, w, q;
        int[] a;
        while((line = br.readLine()) != null) {
            if(line.equals("0 0 0 0"))
                break ;
            sp = line.split(" ");
            n = Integer.parseInt(sp[0]);
            s = Integer.parseInt(sp[1]);
            w = Integer.parseInt(sp[2]);
            q = Integer.parseInt(sp[3]);
            a = createA(n, s, w);
            if(q == 2 || q == 5)
                System.out.println(solve2(a, n, s, w, q));
            else
                System.out.println(solve(a, n, s, w, q));
        }
        br.close();
    }
    static int[] createA(int n, int s, int w) {
        int[] a = new int[n];
        for(int i=0; i<n; i++) {
            a[i] = (s / 7) % 10;
            if(s % 2 == 0)
                s /= 2;
            else 
                s = (s/2)^w;
        }
        return a;
    }
    static int solve(int[] a, int n, int s, int w, int q) {
        int retval = 0;
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        m.put(0, 1);
        int key = 0;
        int ten = 1;
        for(int i=n-1; i>-1; i--) {
            key = (key + (ten * a[i])) % q;
            ten = (ten * 10) % q;
            if(a[i] > 0)
                retval += (m.get(key) == null) ? 0 : m.get(key);
            m.put(key, ((m.get(key) == null) ? 0 : m.get(key))+1);
        }
        return retval;
    }
    static int solve2(int[] a, int n, int s, int w, int q) {
        int retval = 0;
        int nz = 0;
        for(int i=0; i<n; i++) {
            if(a[i] > 0)
                nz++;
            if(a[i] == 0 || a[i] % q == 0)
                retval += nz;
        }
        return retval;
    }
}

2011.11.18

0226 : Hit and Blow

問題文


メモ



実装

java

package aoj0226;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        String[] sp;
        List<String> a = new ArrayList&let;String>();
        List<String> b = new ArrayList&let;String>();
        int hit, blow, i;
        while((line = br.readLine()) != null) {
            sp = line.split(" ");
            if("0".equals(sp[0]) && "0".equals(sp[1]))
                break ;
            a.clear();
            for(i=0; i<4; i++)
                a.add(Integer.toString(sp[0].charAt(i)-'0'));
            b.clear();
            for(i=0; i<4; i++)
                b.add(Integer.toString(sp[1].charAt(i)-'0'));
            hit = 0;
            blow = 0;
            for(i=0; i<4; i++) {
                if(a.get(i).equals(b.get(i)))
                    hit++;
                else if(a.contains(b.get(i)))
                    blow++;
            }
            System.out.println(new StringBuilder().append(hit).append(" ").append(blow).toString());
        }
        br.close();
    }
}

0221 : FizzBuzz

問題文


メモ



実装

java

package aoj0221;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        int m, n, i, j;
        String s;
        String[] sp;
        List<Integer> f = new ArrayList<Integer>();
        StringBuilder sb;
        while((line = br.readLine()) != null) {
            sp = line.split(" ");
            m = Integer.parseInt(sp[0]);
            n = Integer.parseInt(sp[1]);
            if(m == 0 && n == 0)
                break ;
            f.clear();
            for(j=0; j<m; j++)
                f.add(j);
            for(i=1, j=0; n>0; n--, i++) {
                line = br.readLine();
                if(f.size() > 1) {
                    if(i % 3 == 0 && i % 5 == 0)
                        s = "FizzBuzz";
                    else if(i % 3 == 0)
                        s = "Fizz";
                    else if(i % 5 == 0)
                        s = "Buzz";
                    else
                        s = Integer.toString(i);
                    if(!line.equals(s))
                        f.remove(j);
                    else
                        j++;
                    j %= f.size();
                }
            }
            sb = new StringBuilder();
            for(int num : f)
                sb.append(num+1).append(" ");
            System.out.println(sb.delete(sb.length()-1, sb.length()).toString());
        }
        br.close();
    }
}

0219 : A Popular Ice-cream Shop

問題文


メモ



実装

java

package aoj0219;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        int n, i, j;
        int[] c;
        StringBuilder sb;
        while((line = br.readLine()) != null) {
            if(line.isEmpty())
                continue ;
            n = Integer.parseInt(line);
            if(n == 0)
                break ;
            c = new int[10];
            for(; n>0; n--)
                c[Integer.parseInt(br.readLine())]++;
            for(i=0; i<10; i++) {
                sb = new StringBuilder();
                if(c[i] == 0)
                    sb.append("-");
                else
                    for(j=c[i]; j>0; j--)
                        sb.append("*");
                System.out.println(sb.toString());
            }
        }
        br.close();
    }
}

0220 : Binary Digit A Doctor Loved

問題文


メモ

整数部8桁以内 + 小数部4桁以内

2^{7} ~ 2^{-4} が範囲内となる


実装

java

package aoj0220;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        double n;
        int i;
        StringBuilder sb;
        while((line = br.readLine()) != null) {
            if(line.isEmpty())
                continue ;
            n = Double.parseDouble(line);
            if(n < 0d)
                break ;
            sb = new StringBuilder();
            for(i=7; i>-5; i--) {
                if(n / Math.pow(2, i) > 2d) {
                    sb = new StringBuilder("NA");
                    break ;
                }
                if(n != 0d) {
                    sb.append((int)(n / Math.pow(2, i)));
                    n %= Math.pow(2, i);
                } else {
                    sb.append("0");
                }
                if(i == 0)
                    sb.append(".");
            }
            if(n > 0d)
                System.out.println("NA");
            else
                System.out.println(sb.toString());
        }
        br.close();
    }
}

0218 : Dividing Students

問題文


メモ



実装

java

package aoj0218;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        String[] sp;
        int n, pm, pe, pj;
        while((line = br.readLine()) != null) {
            n = Integer.parseInt(line);
            if(n == 0)
                break ;
            for(; n>0; n--) {
                sp = br.readLine().split(" ");
                pm = Integer.parseInt(sp[0]);
                pe = Integer.parseInt(sp[1]);
                pj = Integer.parseInt(sp[2]);
                if(pm == 100 || pe == 100 || pj == 100)
                    System.out.println("A");
                else if((pm + pe) / 2 >= 90)
                    System.out.println("A");
                else if((pm + pe + pj) / 3 >= 80)
                    System.out.println("A");
                else if((pm + pe + pj) / 3 >= 70)
                    System.out.println("B");
                else if((pm + pe + pj) / 3 >= 50 && (pm >= 80 || pe >= 80))
                    System.out.println("B");
                else
                    System.out.println("C");
            }
        }
        br.close();
    }
}

0217 : Walking in the Hospital

問題文


メモ



実装

java

package aoj0217;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        String[] sp;
        int n, d, md;
        String mp;
        while((line = br.readLine()) != null) {
            if(line.isEmpty())
                continue ;
            n = Integer.parseInt(line);
            if(n == 0)
                break ;
            md = 0;
            mp = "";
            for(; n>0; n--) {
                sp = br.readLine().split(" ");
                d = Integer.parseInt(sp[1]) + Integer.parseInt(sp[2]);
                if(d > md) {
                    md = d;
                    mp = sp[0];
                }
            }
            System.out.println((new StringBuilder().append(mp).append(" ").append(md)).toString());
        }
        br.close();
    }
}

0216 : Cutting Down Water Bills

問題文


メモ



実装

java

package aoj0216;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        int w, t, i;
        while((line = br.readLine()) != null) {
            w = Integer.parseInt(line);
            if(w == -1)
                break ;
            t = 1150;
            w -= 10;
            for(i=2; i<5; i++) {
                if(w <= 0)
                    break ;
                switch (i) {
                case 2 :
                    t += (w < 10) ? w * 125 : 10 * 125;
                    break;
                case 3 :
                    t += (w < 10) ? w * 140 : 10 * 140;
                    break;
                case 4 :
                    t += w * 160;
                    break;
                }
                w -= 10;
            }
            System.out.println(4280 - t);
        }
        br.close();
    }
}

0206 : Next Trip

問題文


メモ



実装

java

package aoj0206;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        String[] sp;
        int L, M, N, i, month;
        while((line = br.readLine()) != null) {
            L = Integer.parseInt(line);
            if(L == 0)
                break ;
            for(i=0,month=0; i<12; i++) {
                if(L > 0)
                    month++;
                sp = br.readLine().split(" ");
                M = Integer.parseInt(sp[0]);
                N = Integer.parseInt(sp[1]);
                L -= (M - N);
            }
            System.out.println((L > 0) ? "NA" : month);
        }
        br.close();
    }
}

1044 : CamelCase

問題文


メモ



実装

java

package aoj1044;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        String[] sp;
        while((line=br.readLine()) != null) {
            sp = line.split(" ");
            if(sp[1].equals("X"))
                break ;
            else if(sp[1].equals("D"))
                System.out.println(d(sp[0].toCharArray()));
            else if(sp[1].equals("U"))
                System.out.println(u(d(sp[0].toCharArray()).toCharArray()));
            else if(sp[1].equals("L"))
                System.out.println(l(d(sp[0].toCharArray()).toCharArray()));
        }
        br.close();
    }

    static String d(char[] cs) {
        StringBuilder sb = new StringBuilder();
        for(int i=0, len=cs.length; i<len; i++)
            if(i == 0)
                sb.append(String.valueOf(cs[i]).toLowerCase());
            else if(cs[i] >= 'A' && cs[i] <= 'Z')
                sb.append("_").append(String.valueOf(cs[i]).toLowerCase());
            else
                sb.append(cs[i]);
        return sb.toString();
    }
    static String l(char[] cs) {
        StringBuilder sb = new StringBuilder();
        for(int i=0, len=cs.length; i<len; i++)
            if(cs[i] == '_')
                sb.append(String.valueOf(cs[++i]).toUpperCase());
            else
                sb.append(cs[i]);
        return sb.toString();
    }
    static String u(char[] cs) {
        StringBuilder sb = new StringBuilder();
        for(int i=0, len=cs.length; i<len; i++)
            if(i == 0)
                sb.append(String.valueOf(cs[i]).toUpperCase());
            else if(cs[i] == '_')
                sb.append(String.valueOf(cs[++i]).toUpperCase());
            else
                sb.append(cs[i]);
        return sb.toString();
    }
}

1041 : Kyudo: A Japanese Art of Archery

問題文


メモ



実装

java

package aoj1041;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        int n, sum;
        while((line=br.readLine()) != null) {
            n = Integer.parseInt(line);
            if(n == 0)
                break ;
            sum = 0;
            for(n=n/4; n>0; n--)
                sum += Integer.parseInt(br.readLine());
            System.out.println(sum);
        }
        br.close();
    }
}

2011.11.13

10004 : Sorting Three Numbers

問題文


実装

C++

#include <iostream>
using namespace std;

int main(){
    int i, j, len=3;
    int num[len];
    cin >> num[0] >> num[1] >> num[2];
    for(i=0; i<len-1; i++)
        for(j=len-1; j>i; j--)
            if(num[j] < num[j-1])
                swap(num[j], num[j-1]);
    cout << num[0] << " " << num[1] << " " << num[2] << endl;
    return 0;
}

10003 : Small, Large, or Equal

問題文


実装

C++

#include <iostream>

using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    cout << "a " << ((a==b) ? "==" : (a>b) ? ">" : "<") << " b" << endl;
    return 0;
}

10002 : Rectangle

問題文


実装

C++

#include <iostream>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    cout << (a*b) << " " << (2*a+2*b) << endl;
    return 0;
}

10001 : X Cubic

問題文


実装

C++

#include <iostream>
using namespace std;

int main(){
    int x;
    cin >> x;
    cout << (x*x*x) << endl;
    return 0;
}

10000 : Hello World

問題文


実装

C++

#include <iostream>
using namespace std;

int main(){
    cout << "Hello World" << endl;
    return 0;
}

2009.03.15

ブログ

今更ですが、だいぶ前から


開発系とか


読書日記+α


で、書いてます。

使い分けは適当です。

ついでに内容も適当です。

それだけです。

2008.06.18

Problem 28

problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:


21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.


What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

http://projecteuler.net/index.php?section=problems&id=28:title


consideration

問題

  • 1001 * 1001 の螺旋の場合の、両対角線上の数の総和を求めろ


programing(java

/**
 * Project Euler Problem 28
 */
public class Problem28 {

    /**
     * main
     * @param args
     */
    public static void main(String[] args) {
        Problem28 problem28 = new Problem28();
    }

    /**
     * コンストラクタ
     */
    public Problem28() {
        long maxVal = 1001L * 1001L;
        long sum = 0L;
        int interval = 0;
        int corner = 0;
        int tmp = 0;
        for (int i=1; i<=maxVal; i++) {
            if (interval == 0 || i == (tmp + interval)) {
                tmp = i;
                sum += i;
                if (corner == 0 || corner == 4) {
                    interval += 2;
                    corner = 0;
                }
                corner++;
            }
        }
        // 出力
        System.out.println(sum);
    }
}


TODO

そろそろ何もいわなくったっていい気がしてきた。

ええ、お察しの通りです。

(以下略



その他

問題読んで、なにも考えずに、思うが侭にプログラミングした。

原始的な解答、かな。