無題

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
pon

無題

#1

投稿記事 by pon » 15年前

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

pon

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

#2

投稿記事 by pon » 15年前

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

softya

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

#3

投稿記事 by softya » 15年前

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

mnkr

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

#4

投稿記事 by mnkr » 15年前

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

pon

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

#5

投稿記事 by pon » 15年前

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

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

たいちう

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

#6

投稿記事 by たいちう » 15年前

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

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

pon

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

#7

投稿記事 by pon » 15年前

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

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

fatens

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

#8

投稿記事 by fatens » 15年前

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

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

たいちう

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

#9

投稿記事 by たいちう » 15年前

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

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

たいちう

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

#10

投稿記事 by たいちう » 15年前

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

fatens

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

#11

投稿記事 by fatens » 15年前

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

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

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

たいちう

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

#12

投稿記事 by たいちう » 15年前

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

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

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が抜けているのではないですか?

softya

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

#13

投稿記事 by softya » 15年前

正しい答えは、こちらにあります。
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
たいちろうさんのが正解ですね。

fatens

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

#14

投稿記事 by fatens » 15年前

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

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

バグ

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

#15

投稿記事 by バグ » 15年前

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

#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);

    /* ペア情報の取得をしながら1の招待客を検出 */
    for (i = 0; i < count; ++i)
    {
        fscanf(file, "%d%d", &pair1, &pair2);
        check[pair1 - 1][pair2 - 1] = 1;
        check[pair2 - 1][pair1 - 1] = 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)
    {
        /* 1の招待客かどうか? */
        if (friend1 == 1)
        {
            for (j = 0; j < number; ++j)
            {
                /* 1の招待客の友達で、なおかつ1の招待客ではない場合に友達の友達とする */
                if (check[j] == 1 && friend1[j] == 0)
                {
                    friend2[j] = 1;
                }
            }
        }
    }

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

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

    return 0;
}

たいちう

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

#16

投稿記事 by たいちう » 15年前

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

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;
}

softya

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

#17

投稿記事 by softya » 15年前

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


#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);
}

フリオ

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

#18

投稿記事 by フリオ » 15年前

 
 考えてみました

#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;
}

画像

閉鎖

“C言語何でも質問掲示板” へ戻る