トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

No.83 最大マッチング

■■■問題■■■

あなたは「最大マッチング問題」という有名問題に取り組んでいる。
これは、何本かのマッチ棒が与えられたとき、それらを並べて表記できる最大の数を求める問題である。

数の表記は、0から9までの数字を横に並べることによって行う。
数字の表記法は下図の通りである。

     

マッチ棒は折ってはいけないが、すべて使い切る必要はない。
さて、N本のマッチ棒が与えられたとき、それらを並べて表記できる最大の数を求めよ。

■■■入力■■■

N

マッチ棒の本数 N(2 <= N <= 10万)が与えられる。

■■■出力■■■

マッチ棒を並べて表記できる最大の数を出力せよ。
最後に改行してください。


C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            //7
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            //11
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        //偶数の場合
        if (N % 2 == 0) {
            Console.WriteLine(new string('1', N / 2));
        }
        else { //奇数の場合
            Console.WriteLine("7" + new string('1', N / 2 - 1));
        }
    }
}


解説

マッチ棒2本で作成できる1と
マッチ棒3本で作成できる7
の2つの数字のみに注目して、
マッチ棒が偶数の場合と奇数の場合に、場合分けしてます。