プログラマ専用SNS ミクプラ

すいません。今度は
http://www.ioi-jp.org/joi/2009/2010-yo- ... yo-t3.html
この問題なのですが、

このようなプログラムを組んだのですが、入力1に対しては正しい答えを導いたのですが、他の入力に対して見当違いな答えを返します。何故でしょうか。
お願いします

このままだと先程のやりとりの繰り返しになってしまいますので、自分でできることはやってみませんか？
先程も指摘されていましたが、作りっぱなしで基本的なデバッグさえされているように見受けられません。
(1)ちゃんとデータが入力されていることを確認すること。
(2)最初のループで目的のデータが抽出されているか確認すること。
(3)同様に途中のループでも確認。

途中にブレイクポイントを仕掛けて変数の中身を覗いたり、
途中にprintf（変数）というような感じで変数の中身を覗いたりして
値の推移を見ながらコーディングするとはかどりますよ

最初のforはnまででなくmまでですね。すいません

そうすると、入力1に対しては正しい結果が入力2～5に対しては+1の結果が得られます。どうしてでしょう

> そうすると、入力1に対しては正しい結果が入力2～5に対しては+1の結果が得られます。
> どうしてでしょう

あなたがそのように作ったからです。
結果が気に入らなければデバッグしましょう。

どこが違うんでしょうか…自分でも結構考えてみたのですが全然分かりません…

あとintやcharを文中に入れるとコンパイルに失敗し、それを文頭に移動したら、うまくいくのは何故でしょう

>あとintやcharを文中に入れるとコンパイルに失敗し、それを文頭に移動したら、うまくいくのは何故でしょう

それがCの規則だからです。
一応、C99からはOKになったはずですが。

C++で作った結果。答え合わせ用。
っていうか間違っているかもしれないので、要答え合わせ。

input1.txt : 7
input2.txt : 39
input3.txt : 72
input4.txt : 83
input5.txt : 475

ponさんのプログラムは、どのような手順で書かれているのですか?
順番に説明してください。

>C++で作った結果。答え合わせ用。
>っていうか間違っているかもしれないので、要答え合わせ。

私はこうなりました。
入力1 : 6
入力2 : 25
入力3 : 50
入力4 : 57
入力5 : 336

少なくとも入力1と入力2については検算もしてみたので正しいはず...

fatensさんありがとうございます。

入力１については、簡単に検証できますね。

10
10
4 10
7 10
3 7
6 8
1 7
1 6
1 5
1 9
2 4
3 8

友達 : 5, 6, 7, 9
友達の友達 : 3, 8, 10

もしかして3が抜けているのではないですか?

正しい答えは、こちらにあります。
http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/
input1.txt : 7
input2.txt : 39
input3.txt : 72
input4.txt : 83
input5.txt : 475
たいちろうさんのが正解ですね。

>たいちうさん
>softyaさん
>もしかして3が抜けているのではないですか?

その通りです。
問題の解釈の間違いに気づき修正していたところでした。
失礼しました。

頭の体操な感じですね。
皆さんの解法が気になります(^-^)
とりあえず、見苦しいですが私のソースを…
もう少し綺麗にまとめられそうにも思うのですが、ベタで分かり易い書き方でやってみました。


#include <stdio.h>
#include <string.h>

#define N    500

int main(void)
{
    int i = 0, j = 0;            /* 汎用変数 */
    int number = 0;                /* 生徒人数 */
    int count = 0;                /* データリスト数 */
    int pair1 = 0;                /* ペア情報一時保持用バッファ */
    int pair2 = 0;                /* ペア情報一時保持用バッファ */
    int check[N][N];            /* 友人関係保持用配列 */
    int friend1[N];                /* 招待客情報用配列 */
    int friend2[N];                /* 友人の友人情報用配列 */
    int result = 0;                /* 招待客の人数 */
    FILE* file = NULL;            /* ファイルポインタ */

    /* ファイルのオープン処理 */
    if ((file = fopen("input1.txt", "r")) == NULL)
    {
        /* ファイルのオープンに失敗 */
        return -1;
    }

    /* 人数とデータ数を取得 */
    fscanf(file, "%d", &number);
    fscanf(file, "%d", &count);

    /* 配列の初期化 */
    memset(check, 0, sizeof(int) * N * N);
    memset(friend1, 0, sizeof(int) * N);
    memset(friend2, 0, sizeof(int) * N);

    /* ペア情報の取得をしながら１の招待客を検出 */
    for (i = 0; i < count; ++i)
    {
        fscanf(file, "%d%d", &pair1, &pair2);
        check[pair1 - 1][pair2 - 1] = 1;
        check[pair2 - 1][pair1 - 1] = 1;

        /* １の招待客の情報を保持する */
        if (pair1 == 1)
        {
            friend1[pair2 - 1] = 1;
        }
        else if (pair2 == 1)
        {
            friend1[pair1 - 1] = 1;
        }
    }

    /* ファイルをクローズする */
    fclose(file);

    /* 友達の友達を検出 */
    for (i = 0; i < number; ++i)
    {
        /* １の招待客かどうか？ */
        if (friend1 == 1)
        {
            for (j = 0; j < number; ++j)
            {
                /* １の招待客の友達で、なおかつ１の招待客ではない場合に友達の友達とする */
                if (check[j] == 1 && friend1[j] == 0)
                {
                    friend2[j] = 1;
                }
            }
        }
    }

    /* 最終カウント */
    for (i = 1; i < number; ++i)
    {
        /* １の招待客、１の招待客の友達か？ */
        if (friend1 == 1 || friend2 == 1)
        {
            /* 人数をインクリメント */
            ++result;
        }
    }

    /* 人数を表示 */
    printf("%d\n", result);

    return 0;
}

> 皆さんの解法が気になります(^- ^)

C++でよければどうぞ。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <set>

using namespace std;

typedef vector<pair<int, int> > vp;
typedef vp::iterator vpit;

void check(const string &fileName) {
fstream ifs(fileName.c_str());
int n, len;
ifs >> n;
ifs >> len;
vp data;
for (int i = 0; i < len; i++) {
int a, b;
ifs >> a >> b;
data.push_back(pair<int, int>(a, b));
}

set<int> f;
f.insert(1);

for (int i = 0; i < 2; i++) {
set<int> temp;
for (vpit it = data.begin(); it != data.end(); it++) {
if (f.find(it->first) != f.end())
temp.insert(it->second);
else if (f.find(it->second) != f.end())
temp.insert(it->first);
}
f.insert(temp.begin(), temp.end());
}

cout << fileName << " : " << static_cast<int>(f.size()) - 1 << endl;
}

int main() {
check("input1.txt");
return 0;
}

ざざざっと書いたのでバグっているかも。
※　最初友達の友達の友達がＮＧだと言う事に気付かなかった。

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

#define MAX_FRI 500+1
typedef struct {
int count;
int friend_no[MAX_FRI];
int mark;
} t_friend;

t_friend fri_table[MAX_FRI] = { {0,0,0} };

void friend_mark(int n,int nest)
{
int l;
if( nest < 3 ) {
for( l=0 ; l<fri_table[n].count ; l++ ) {
// printf( "%d->%d\n", n, fri_table[n].friend_no[[/url] );
friend_mark( fri_table[n].friend_no[[/url],nest+1 );
}
}
fri_table[n].mark = 1;
}

int main()
{
int n;
int m;
int a;
int answer = 0;
scanf("%d",&n);
scanf("%d",&m);
for(a=0;a<m;a++)
{
int studentA,studentB;
scanf("%d%d",&studentA,&studentB);
fri_table[studentA].friend_no[fri_table[studentA].count] = studentB;
fri_table[studentA].count++;
fri_table[studentB].friend_no[fri_table[studentB].count] = studentA;
fri_table[studentB].count++;
}
friend_mark(1,1);
for(a=2;a<=n;a++) {
if( fri_table[a].mark == 1 ) {
answer++;
// printf("[%d] %d\n",a, answer);
}
}
printf("%d",answer);
}

　
　考えてみました


#include <stdio.h>

void make_table(int table[/url][500])
{
    int m;
    
    scanf("%d", &m);
    while(m --){
        int a, b;
        
        scanf("%d %d", &a, &b);
        table[a - 1] = table[a - 1] = 1;
    }
}

int count_guest(int table[/url][500], int n)
{
    int list[500] = {0}, sum = 0, i;
    
    for(i = 1; i < n; ++ i){
        if(table[0]){
            int j;
            
            if(!list){
                ++ sum;
                list = 1;
            }
            for(j = 1; j < n; ++ j){
                if(table[j] && !list[j]){
                    ++ sum;
                    list[j] = 1;
                }
            }
        }
    }
    return sum;
}

int main(void)
{
    int table[500][500] = {0}, n;
    
    scanf("%d", &n);
    make_table(table);
    printf("%d\n", count_guest(table, n));
    return 0;
}

プログラマ専用SNS ミクプラ

無題

無題

さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。

Re:さっきの投稿の続きです。