Codeforces#64に初挑戦！

というわけで、まぁTopCoder部のカレンダーにものってるもんだし、標準入出力をあつかうプロコンやっといたほうが後のため…とおもいまして、やってきましたよ。

Codeforcesを知らない人向けに行っておくと、これは未だにベータ版のコンテスト(だいぶ完成しているようにも見えるんですが・・・)で、ロシア語と英語の二か国語での開催。

使える言語はC++、C、Erlang、Python、Perl、Java…みたいにいっぱいあります(コンパイラの様子を見るとUnixかLinux系をサーバーとして使ってそこに入ってるコンパイラをフル活用しているよう)

2時間で5問とくのですが、TopCoderみたいにHackという制度があり、時間中に他人のコードを見てエラーを起こさせたら(ryみたいなことができます(この場合自分の解答は改変できなくなる。)

形式はICPC方式だそうで。そこらへんはよくわからん…

標準入出力についてはもひとつのブログにまとめておいたんで。

今回は

A Cookies
B Text Messaging
C Lucky Ticket
D Professors tasks
E Information Reform

の五問。

最初…っていっても仕方ありませんね。今回は二問だけ解きました。

A Cookies
問題の詳細は何かにまかすとして(笑)

まず僕はJavaでとりあえず書いたのですがオーバーフローしてしまって(；´Д｀)

で、何を思ったかPythonやCで改善移植をはかったんですね。

#! /usr/bin/env python

def solve(n):
    len = 2^n
    sum = 0
    for i in range(1, len-1):
        sum += i
    be = solve(n-1)
    ol = solve(n-2)
    sum = sum - (2^(n-1))^2 + be - ((2^(n-2))^2 - ol)*2
    return sum

def main():
    n = int(raw_input())
    ans = solve(n)
    print ans

if __name__ == '__main__':
    main()

とか・・・

#include <stdio.h>
#include <math.h>

int solve(int n) {
        int sum = pow(pow(2, n), 2)/2+pow(2, n)*2-1;
        if (n != 1) { 
                int count = 1;
                while (count < n) {
                        sum+=solve(count);
                        count++; 
                }
        }
        return sum;
}   
    
int main() {
        int a;
        scanf("%d", &a);
        int ans = pow(pow(2, a), 2) - solve(a);
        printf("%d", ans);
}

Cまともに書いたの久しぶりだ(笑)

でも答えはずれるばかり…

まぁこれだけ書けばなんかJavaで行けるんじゃないかと…

そして完成したコードがコチラ

import java.io.*;

public class A {
        public static int solve(int n) {
                int sum = 0; 
                if (n == 1) {
                        sum = 1;
                } else {
                        sum = solve(n-1)*3;
                }       
                return sum;
        }
        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                int n = Integer.parseInt(br.readLine());
                int ans = solve(n);
                System.out.println(ans);
        }
}

前の答えを三回かければいいとか覚醒した(笑)

で、コレをいつぐらいかな？

結構ギリギリになって提出したら80msってでたので、まぁ大丈夫なのかな・・・と。

それで次とりかかりました。
B Text Messaging
これは、まぁ行き詰まってたときに問題全部流してたんで問題文の解読にはあまり時間がかからなかったです。

とりあえずサンプルから察して残り５分ぐらいで書いてみた。

import java.io.*;

public class B {
        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                int n = Integer.parseInt(br.readLine());
                String[] string = br.readLine().split(" ");
                int count = 0;
                for (int i = 0; i< string.length; i++) {
                        String st = string[i];
                        if ('?' == st.charAt(st.length()-1) && st.length() <= n) count++;
                        else if ('!' == st.charAt(st.length()-1) && st.length() <= n) count++;
                        else if ('.' == st.charAt(st.length()-1) && st.length() <= n) count++;
                }
                if (count == 0) System.out.println("Impossible");
                else System.out.println(count);
        }       
}