トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
ABC-046-B AtCoDeerくんとボール色塗り
■■■問題■■■
シカのAtCoDeerくんは一列に並んだN個のボールを
それぞれK色のペンキの色のうちのどれかで塗ろうとしています。
見栄えが悪くならないように、隣り合ったボールは別の色で塗ることにします。
ボールの塗り方としてあり得るものの個数を求めてください。
■■■入力■■■
N K
●1 <= N <= 1000
●2 <= K <= 1000
●答えは (2の31乗)-1 以下
■■■出力■■■
ボールの塗り方としてあり得るものの個数を出力せよ。
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("2 2");
//2
//色を0,1で表すと、
//左のボールを0で塗り、右のボールを1で塗るという方法と、
//左のボールを1で塗り、右のボールを0で塗るという方法の2通りがあります。
}
else if (InputPattern == "Input2") {
WillReturn.Add("1 10");
//10
//ボールは一つしか無いため,
//10色のうちどれを使っても良いので答えは10通りです。
}
else if (InputPattern == "Input3") {
WillReturn.Add("10 8");
//322828856
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();
long N = wkArr[0];
long K = wkArr[1];
long Answer = K;
for (long I = 2; I <= N; I++) {
Answer *= K - 1;
}
Console.WriteLine(Answer);
}
}
解説
1個目のボールを塗る色は、K通り
2個目以降のボールを塗る色は、(K-1)通り
ですので、積の法則を使ってます。