Codeforces 344A Magnets 磁鐵

難易度 : 800

英文原文如下

Mad scientist Mike entertains himself by arranging rows of dominoes. He doesn’t need dominoes, though: he uses rectangular magnets instead. Each magnet has two poles, positive (a “plus”) and negative (a “minus”). If two magnets are put together at a close distance, then the like poles will repel each other and the opposite poles will attract each other.

Mike starts by laying one magnet horizontally on the table. During each following step Mike adds one more magnet horizontally to the right end of the row. Depending on how Mike puts the magnet on the table, it is either attracted to the previous one (forming a group of multiple magnets linked together) or repelled by it (then Mike lays this magnet at some distance to the right from the previous one). We assume that a sole magnet not linked to others forms a group of its own.

Mike arranged multiple magnets in a row. Determine the number of groups that the magnets formed.

中文翻譯

瘋狂科學家 Mike 排列多米諾骨牌以娛樂自己，不過他沒有使用骨牌，而是使用了磁鐵。每一個磁鐵有兩個極性 (正極與負極)。如果兩個磁鐵放在靠近的位置，那麼相同極性將會互相排斥，而不同急性則為互相吸引。

Mike 首先會先將一個磁鐵水平的放在桌子上，接下來的每一步中，他都會在目前的最右邊水平的加入一個磁鐵。然後有可能會跟上一個互相吸引 (形成一個多個磁鐵組合而成的群組) 或互相排斥 (Mike 就會將他放在更旁邊一點的位置)。假設有一個磁鐵沒有連結其他的磁鐵，也被視為一組。

(像是上圖就有3組磁鐵群組)

Mike 排列了多個磁鐵在同一行上，確認這些磁鐵會形成多少組

輸入

The first line of the input contains an integer n (1 ≤ n ≤ 100000) — the number of magnets. Then n lines follow. The i-th line (1 ≤ i ≤ n) contains either characters “01”, if Mike put the i-th magnet in the “plus-minus” position, or characters “10”, if Mike put the magnet in the “minus-plus” position.

第一行包含了一個整數 n (1 ≤ n ≤ 100000) — 磁鐵的總數。接下來的 n 行，第 i (1 ≤ i ≤ n) 行可能是 “01”，也就是Mike將磁鐵放為 “正(極)負(極)” ，或是 “10”，也就是 “負(極)正(極)” 。

輸出

On the single line of the output print the number of groups of magnets.

印出一個整數 — 磁鐵總共可以分為幾組。

範例

分群後會像這樣 : 101010, 01 , 1010 故回傳3

解題思路

在我們的解法中，我們會判斷每一行最後一個元素與下一行的最後一個元素(相當於其極性)

要是其極性相等，就代表他們可以被分為同一群，像是 (+-+-) 或是 (-+-+)

C#解決方案

方案1

int n = int.Parse(Console.ReadLine());  //number of magnets 

int cnt = 1;
char curr = Console.ReadLine()[1];

for(int i = 1; i<n ; i++)
{
    char compare = Console.ReadLine()[1]; 
    if(curr != compare){
        cnt+=1;
        curr = compare;
    }
}

Console.WriteLine(cnt);

Java解決方案

方案1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine()); //number of magnets 
        int cnt = 1;
        
        char curr = scanner.nextLine().charAt(1);

        for(int i = 1; i<n ; i++)
        {
            char compare = scanner.nextLine().charAt(1); 
            if(curr != compare){
                cnt+=1;
                curr = compare;
            }
        }
        System.out.println(cnt);
    }
}

結論

這一題應該算是沒甚麼難度的，就像之前codeforces題目中說過的，他們會盡可能使第一題 (尾號為A的) 簡單

小時候有一個磁鐵就能玩上一整天呢，還可以跟同學一起玩哈哈哈

🧡如果文章有幫上你的忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Problem – 344A – Codeforces

一些其他的Codeforces文章