poj 3040

[ciiii]

pojの3040番です。wrong answerになってしまうのですが、なぜだかわかりません。どなたか教えてください。サンプルインプットは正しくアウトプットできました。


#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
//#include <map>
using namespace std;

typedef pair<int,int> P;//x y

int main(){
P money[20];
int count = 0;
int N,c;
cin >> N >> c;
for(int i=0;i<N;i++){
cin >> money.first >> money.second;
count += money.first*money.second;
}

sort(money,money+N);//金額の小さい順にソート

int now = N-1;
int ans = 0;
while(money[now].first>= c){
count -= money[now].first*money[now].second;
ans += money[now].second;
now --;

if(now == -1){break;}
}
if(now==-1){cout << ans << endl;return 0;}
int n = now;

//ここの時点で、money[now].firstはcよりも小さい
//つまり、金額がcよりも小さいのはmoney[n]から。また、nから下のループを始める。
while(count>=c){
now = n;

int nokori = c;
int flag = 0;//余りを埋める時の小さい硬貨がないと1になる
while(nokori>0){
flag = 0;
while(money[now].first<=nokori){
if(money[now].second==0){//もしもこの金額の硬貨がもう0なら
//if(ans == 1){cout<< "here" << endl;}
if(now==0){
flag = 1;}
else{//nowが0でない
flag = 2;}
}
if(flag == 1){break;}//もしもう0まで見たら出る
if(flag == 0){
count -= money[now].first;
nokori -= money[now].first;
money[now].second --;}
if(flag==2){break;}
}
if(flag == 1){
break;}//もしもう0まで見たら出る

now--;
}
if(flag==0){//無事にぴったりcがうまった。
ans ++;
continue;
}
//nowが0まで行ってしまった。now=0の時はだめだった

now++;

while(now<=n){
if(money[now].second>0){
ans ++;
count -= money[now].first;
money[now].second --;
break;
}
now ++;
}
}
cout << ans << endl;
}

[Tangeθ]

私の環境では、問題なくソースをコンパイルできました。
プロジェクトの設定を「コンソールアプリケーション」と「空のプロジェクト」で作成してあるかどうかだけ確認してみてください。

[ciii]

コンパイルは自分の環境でもできました。
ただ、pojのオンラインジャッジで間違いだと言われるので、
どこかアルゴリズムが間違っていると思うのですが、どこなのでしょうか。

[みけCAT]

コードはcodeタグで囲んでいただけるとありがたいです。

countがオーバーフローしています。

コード:

2 100000000
50000000 1000000
100000000 1000000

で撃墜できると思います。

[ciiii]

指摘された通り、オーバーフローしていました。ありがとうございます。
オーバーフローはおそらく解決できたのですが、まだwrong answerです。なぜなのでしょうか・・・

コード:

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
//#include <map>
using namespace std;

typedef pair<long,long> P;//x y

int main(){
P money[20];
long count = 0;
int N;
 long c;
cin >> N >> c;
for(int i=0;i<N;i++){
cin >> money[i].first >> money[i].second; 
count += money[i].first*money[i].second;
}

sort(money,money+N);//金額の小さい順にソート

long now = N-1;
long ans = 0;
while(money[now].first>= c){
count -= money[now].first*money[now].second;
ans += money[now].second;
now --;

if(now == -1){break;}
}
if(now==-1){cout << ans << endl;return 0;}
long n = now;

//ここの時点で、money[now].firstはcよりも小さい
//つまり、金額がcよりも小さいのはmoney[n]から。また、nから下のループを始める。
while(count>=c){
now = n;

long nokori = c;
int flag = 0;//余りを埋める時の小さい硬貨がないと1になる
while(nokori>0){
flag = 0;
while(money[now].first<=nokori){
if(money[now].second==0){//もしもこの金額の硬貨がもう0なら
if(now==0){
flag = 1;}
else{//nowが0でない
flag = 2;}
}
if(flag == 1){break;}//もしもう0まで見たら出る
if(flag == 0){
count -= money[now].first;
nokori -= money[now].first;
money[now].second --;}
if(flag==2){break;}
}
if(flag == 1){
break;}//もしもう0まで見たら出る

now--;
}
if(flag==0){//無事にぴったりcがうまった。
ans ++;
continue;
}
//nowが0まで行ってしまった。now=0の時はだめだった

now++;

while(now<=n){
if(money[now].second>0){
ans ++;
count -= money[now].first;
money[now].second --;
break;
}
now ++;
}
}

cout << ans << endl;
}

[みけCAT]

きちんとインデントしてもらえないと、codeタグの効果が半減どころか9割くらい減ってしまうのですが…

C++でlongを使っているようですが、本当にこれでオーバーフローしないですか？