ページ 1 / 1
【雑談】A+B Ploblem
Posted: 2012年4月06日(金) 21:51
by みけCAT
競技プログラミングの問題としてよく(嘘)見る、「A+B Ploblem」
今回は、こんな問題を用意しました。
形式は
AOJの形式を想定しています。
コード:
A+B Ploblem
時間制限 1秒 メモリ制限 32768KB
問題
2個の整数A、Bが与えられる。
AとBの和を1行に出力しなさい。
入力
複数のデータセットの並びが入力として与えられる。
各データセットは以下の通りである。
1行目 A
2行目 B
ただしA、Bはともに正の整数で、1000桁未満である。
A、Bの先頭に余計な0は付いていない。
A、Bがともに0の時、入力の終わりを表す。このとき、出力を行ってはならない。
出力
入力データセットごとに、AとBの和を1行に出力する。
先頭に余計な0を出力してはならない。
行の最後には必ず改行を入れること。
サンプル入力
1
1
1
9
123456789
987654321
111111111111111111111111111111
222222222222222222222222222222
0
0
サンプル出力
2
10
1111111110
333333333333333333333333333333
適当に作ったジャッジ用データを添付しました。
いろいろな言語での解答、ショートコーディングなどを期待しています。
自分の解答(正解出力の作成にも使った)を置いておきます。
C言語
► スポイラーを表示
コード:
#include <stdio.h>
#include <string.h>
char num1[1004];
char num2[1004];
char num1_tmp[1004];
char num2_tmp[1004];
char result[1004];
int main(void) {
int len1,len2;
int i,carry;
while(1) {
scanf("%s",num1);
scanf("%s",num2);
if(strcmp(num1,"0")==0 && strcmp(num2,"0")==0)break;
len1=strlen(num1);
len2=strlen(num2);
memset(num1_tmp,'0',1000);
memset(num2_tmp,'0',1000);
memcpy(&num1_tmp[1000-len1],num1,len1);
memcpy(&num2_tmp[1000-len2],num2,len2);
carry=0;
for(i=1000-1;i>=0;i--) {
result[i]=(num1_tmp[i]-'0')+(num2_tmp[i]-'0')+carry+'0';
if(result[i]>'9') {
result[i]-=10;
carry=1;
} else carry=0;
}
for(i=0;result[i]=='0';i++);
for(;i<1000;i++)putchar(result[i]);
putchar('\n');
}
return 0;
}
※これを投稿した時点では、この掲示板には
バグがあるようです。
'は半角の’に置き換えてください。
Java
► スポイラーを表示
コード:
package main;
import java.io.*;
import java.math.BigInteger;
public class A_plus_B {
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自動生成されたメソッド・スタブ
BigInteger s1,s2;
BufferedReader d = new BufferedReader(new InputStreamReader(System.in));
while(true) {
try {
s1=new BigInteger(d.readLine());
s2=new BigInteger(d.readLine());
} catch(IOException e) {
break;
}
if(s1.equals(BigInteger.ZERO) && s2.equals(BigInteger.ZERO)) {
break;
}
System.out.println(s1.add(s2).toString());
}
}
}
!重要!
ジャッジデータに不正が見つかったため、作り直しました。(2012/4/19 21:30)
Re: 【雑談】A+B Ploblem
Posted: 2012年4月08日(日) 03:00
by トントン
Perlです。
こんな感じでしょうか?
コード:
use strict;
use Math::BigInt;
sub sum_ab {
my ($a, $b) = @_;
my $x = Math::BigInt->new($a);
$x->badd($b)
}
while(1) {
my $a = <STDIN>;
my $b = <STDIN>;
my $sum = sum_ab($a, $b);
print "$sum\n" if $sum or print ("\n"), last;
}
__END__
#Testcode
use Test::More;
subtest 'test1' => sub {
my $sum = sum_ab('1', '1');
is $sum, '2';
};
subtest 'test2' => sub {
my $sum = sum_ab('1', '9');
is $sum, '10';
};
subtest 'test3' => sub {
my $sum = sum_ab('123456789', '987654321');
is $sum, '1111111110';
};
subtest 'test4' => sub {
my $sum = sum_ab('111111111111111111111111111111', '222222222222222222222222222222');
is $sum, '333333333333333333333333333333';
};
subtest 'test5' => sub {
my $sum = sum_ab('0', '0');
is $sum, '0';
};
subtest 'test6' => sub {
my $sum = sum_ab('1', '0');
is $sum, '1';
};
subtest 'test7' => sub {
my $sum = sum_ab('0', '1');
is $sum, '1';
};
subtest 'test8' => sub {
my $sum = sum_ab(9x999, 9x999);
is $sum, '1999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998';
};
done_testing;
「judge」フォルダのテストは諦めましたorz
ベンチマーク、メモリ使用量はわかりません><
【追記】
アカン、バグっていた。
修正しました。
Re: 【雑談】A+B Ploblem
Posted: 2012年4月08日(日) 08:14
by みけCAT
>>トントンさん
最後に余計な改行を出力してしまいます。
AOJならおそらくWA:Presentation Errorとなりますね。
Re: 【雑談】A+B Ploblem
Posted: 2012年4月08日(日) 14:08
by トントン
みけCAT さんが書きました:>>トントンさん
最後に余計な改行を出力してしまいます。
AOJならおそらくWA:Presentation Errorとなりますね。
おっと。。。勘違してしまったようです。
コード:
#こっちに修正
print "$sum\n" if $sum or last;
難しい><
Re: 【雑談】A+B Ploblem
Posted: 2012年4月09日(月) 02:59
by かずま
A、Bはともに正の整数で、1000桁「未満」なんですよね。
コード:
#include <stdio.h>
#include <string.h>
int main(void)
{
char a[1000], b[1000], c[1000];
int i, j, k, n;
while (scanf("%s%s", a, b), *a-'0' || *b-'0') {
i = strlen(a), j = strlen(b), k = n = 0;
for (; i && j; k++) if (n = (c[k] = a[--i]+b[--j]-'0'*2+n) > 9) c[k] -= 10;
for (; i; k++) if (n = (c[k] = a[--i]-'0'+n) > 9) c[k] -= 10;
for (; j; k++) if (n = (c[k] = b[--j]-'0'+n) > 9) c[k] -= 10;
if (n) c[k++] = n;
while (k) putchar(c[--k]+'0');
putchar('\n');
}
return 0;
}
Re: 【雑談】A+B Ploblem
Posted: 2012年4月09日(月) 21:11
by みけCAT
>>かずまさん
おお、シンプルな仕組みのいいコードですね。
Re: 【雑談】A+B Ploblem
Posted: 2012年4月11日(水) 04:02
by かずま
マクロを使って文字数を減らしてみました。
コード:
#include <stdio.h>
#define F(x, y) for(; x; k++) if (n = (c[k] = y + n) > '9') c[k] -= 10
char a[1000], b[1000], c[1001] = {'\n'};
main() {
while (scanf("%s%s", a, b), *a-'0' || *b-'0') {
int i = strlen(a), j = strlen(b), k = 1, n = 0;
F(i && j, a[--i] + b[--j] - '0');
F(i, a[--i]);
F(j, b[--j]);
if (n) c[k++] = '1';
while (k) putchar(c[--k]);
}
}
Re: 【雑談】A+B Ploblem
Posted: 2012年4月13日(金) 03:17
by かずま
さらに短くしてみました。
コード:
#include <stdio.h>
#define F(x, y) for(; x; k++) if (n = (c[k] = y + n) > '9') c[k] -= 10
char a[1000], b[1000], c[1001] = "\n";
main() {
while (scanf("%s%s", a, b), *a-'0' || *b-'0') {
int i = strlen(a), j = strlen(b), k = 1, n = 0;
F(i&&j, a[--i]+b[--j]-'0'); F(i, a[--i]); F(j, b[--j]); F(n, '0');
while (k) putchar(c[--k]);
}
}
Python だと簡単なんですけどね。
コード:
while 1:
a = long(raw_input())
b = long(raw_input())
if a == 0 and b == 0: break
print a + b
[code=Python]と書くと括弧が消えてしまったので、Text にしました。
Re: 【雑談】A+B Ploblem
Posted: 2012年4月14日(土) 03:34
by かずま
今度は Ruby です。
コード:
while 1
a = gets.to_i
b = gets.to_i
if a == 0 && b == 0 then break end
puts a + b
end
Python とたいして変わらず、あまり面白くありません。
やっぱり C ですね。
コード:
#include <stdio.h>
#define F(x, y) while(x) if (n = (c[--k] = y + n) > '9') c[k] -= 10
char a[1000], b[1000], c[1001];
main() {
while (scanf("%s%s", a, b), *a-'0' || *b-'0') {
int i = strlen(a), j = strlen(b), k = 1000, n = 0;
F(i&&j, a[--i]+b[--j]-'0'); F(i, a[--i]); F(j, b[--j]); F(n, '0');
puts(c + k);
}
}
Re: 【雑談】A+B Ploblem
Posted: 2012年4月14日(土) 13:34
by みけCAT
>>かずまさん
いつも投稿ありがとうございます。
Re: 【雑談】A+B Ploblem
Posted: 2012年4月14日(土) 18:25
by かずま
かずま さんが書きました:今度は Ruby です。
コード:
while 1
a = gets.to_i
b = gets.to_i
if a == 0 && b == 0 then break end
puts a + b
end
Python とたいして変わらず、あまり面白くありません。
書き方次第で、Ruby も面白い。
コード:
while (a = gets.to_i + gets.to_i) != 0: puts a end
Re: 【雑談】A+B Ploblem
Posted: 2012年4月18日(水) 18:59
by asdjack
コード:
#include<stdio.h>
#include<string.h>
int main()
{
FILE *fp;
fp=fopen("input.txt","r");
char input1[1000]={0},input2[1000]={0};
int output[1000]={0};
int lengs1=0,lengs2=0,lengs3=0,lengs4=0;
int i,j=1,k;
fscanf(fp,"%s",input1);
fscanf(fp,"%s",input2);
while(input1[0]!='0' && input2[0]!='0')
{
lengs1=strlen(input1);
lengs2=strlen(input2);
lengs3=(lengs1>=lengs2)?lengs1+1:lengs2+1;
lengs4=lengs3;
while(lengs3>=0 && lengs1>=0 && lengs2>=0)
{
output[lengs3]+=(input1[lengs1--]-'0')+(input2[lengs2--]-'0');
if(output[lengs3]>=10)
{
output[lengs3]%=10;
output[lengs3-1]+=1;
}
lengs3--;
}
if(lengs1>=0||lengs2>=0)
{
while(lengs1>=0)
{
output[lengs3]+=(input1[lengs1--]-'0');
if(output[lengs3]>=10)
{
output[lengs3]%=10;
output[lengs3-1]+=1;
}
lengs3--;
}
while(lengs2>=0)
{
output[lengs3]+=(input1[lengs2--]-'0');
if(output[lengs3]>=10)
{
output[lengs3]%=10;
output[lengs3-1]+=1;
}
lengs3--;
}
}
if(output[0]!=0)
j=0;
for(i=j;i<lengs4;i++)
{
printf("%d",output[i]);
}
printf("\n");
for(k=0;k<1000;k++)
{
input1[k]=0;
input2[k]=0;
output[k]=0;
}
fscanf(fp,"%s",input1);
fscanf(fp,"%s",input2);
}
fclose(fp);
}
こういう問題に初めて挑戦してみましたが、
全然コンパクトにならなかった…
まだまだ勉強が足りないってことですね。
Re: 【雑談】A+B Ploblem
Posted: 2012年4月18日(水) 21:03
by みけCAT
>>asdjackさん
残念ながらWrong Answerです。
サンプル入力に対する出力くらい確認しましたか?
あなたの環境では正しく動いているのでしたら、その環境を教えてください。
http://ideone.com/pUshc
Re: 【雑談】A+B Ploblem
Posted: 2012年4月18日(水) 23:34
by asdjack
コード:
#include<stdio.h>
#include<string.h>
int main()
{
FILE *fp;
fp=fopen("input.txt","r");
char input1[1001]={0},input2[1001]={0};
int output[1002]={0};
int lengs1=0,lengs2=0,lengs3=0,lengs4=0;
int i,j=1,k;
fscanf(fp,"%s",input1);
fscanf(fp,"%s",input2);
while(input1[0]!='0' && input2[0]!='0')
{
lengs1=strlen(input1);
lengs2=strlen(input2);
lengs3=(lengs1>=lengs2)?lengs1+1:lengs2+1;
lengs4=lengs3;
while(lengs3>=0 && lengs1>=0 && lengs2>=0)
{
output[lengs3]+=(input1[lengs1--]-'0')+(input2[lengs2--]-'0');
if(output[lengs3]>=10)
{
output[lengs3]%=10;
output[lengs3-1]+=1;
}
lengs3--;
}
if(lengs1>=0||lengs2>=0)
{
while(lengs1>=0)
{
output[lengs3]+=(input1[lengs1--]-'0');
if(output[lengs3]>=10)
{
output[lengs3]%=10;
output[lengs3-1]+=1;
}
lengs3--;
}
while(lengs2>=0)
{
output[lengs3]+=(input2[lengs2--]-'0');
if(output[lengs3]>=10)
{
output[lengs3]%=10;
output[lengs3-1]+=1;
}
lengs3--;
}
}
if(output[0]!=0)
j=0;
for(i=j;i<lengs4;i++)
{
printf("%d",output[i]);
}
printf("\n");
for(k=0;k<1000;k++)
{
input1[k]=0;
input2[k]=0;
output[k]=0;
}
j=1;
fscanf(fp,"%s",input1);
fscanf(fp,"%s",input2);
}
fclose(fp);
}
input2が残ってる時の処理の部分が間違っていたのと、各配列の大きさを変更、修正しました。
AよりBが短い時の確認を忘れていたようです。
まだまだ勉強が足りませんね。
Re: 【雑談】A+B Ploblem
Posted: 2012年4月19日(木) 21:19
by みけCAT
>>asdjackさん
まだWrong Answerになります…
と思ったらジャッジデータが不正だったようです!すみません!
[追記]ジャッジデータを修正したら大丈夫(AC)なようです。