チャレンジテスト
採用応募には、チャレンジテスト（問題Aまたは問題Bのいずれか1問）への解答が必須となります。
新卒採用、中途採用、インターン採用ページの「応募の流れ」を確認のうえ、各採用エントリーフォームよりご応募ください。
問題 A
１ ～ ４のN乗 まですべての数を４進数表記した際に使用される “３” の個数を、標準出力に出力するプログラムを作成してください。なお、プログラミング言語はC,C++,Java,Pythonに限ります。
■入力
標準入力から 0≦N≦30 で与えられるものとします。
■ヒント
・N=2 のとき、使用される “3” の個数は 8 になります。
・N=30 のとき、使用される “3” の個数は 8646911284551352320 になります。
問題 B
xy平面上にn個の長方形が配置されています。できるだけ多くの長方形を通過するように直線を引いたときの、通過する長方形の数を標準出力に出力するプログラムを書いてください。なお、プログラミング言語はC,C++,Java,Pythonに限ります。
■入力
長方形の数をn、i番目の長方形の左上座標をx[i], y[i], 幅、高さをw[i], h[i]とすると、以下の順に標準入力から与えられます。
n
x[0] y[0] w[0] h[0]
x[1] y[1] w[1] h[1]
・
・
x[n-1] y[n-1] w[n-1] h[n-1]
■注意点
・0 < n <= 1000
・各長方形は0 <= x <= 10000, 0 <= y <= 10000に存在
・各長方形の座標は整数、幅、高さは1以上の整数
・長方形は互いに重なることもあります
・長方形の頂点を通る場合も、通過したとみなします
■ヒント
Case1
Input
4
0 0 1 1
9999 0 1 1
0 9999 1 1
9999 9999 1 1
Output
2
Case2
Input
6
2 1 4 3
1 10 1 3
5 7 5 4
8 8 3 2
13 4 3 1
17 1 1 14
Output
5
Case3
Input
input3.txt
※データ数が多いため、テキストファイルとして用意しました。ダウンロードしてご利用ください。
Output
509