首页 > 专题系列 > Java解POJ > POJ 1978 Hanafuda Shuffle [解题报告] Java
2013
11-10

POJ 1978 Hanafuda Shuffle [解题报告] Java

Hanafuda Shuffle

问题描述 :

There are a number of ways to shuffle a deck of cards. Hanafuda shuffling for Japanese card game ‘Hanafuda’ is one such example. The following is how to perform Hanafuda shuffling.

There is a deck of n cards. Starting from the p-th card from the top of the deck, c cards are pulled out and put on the top of the deck, as shown in Figure 1. This operation, called a cutting operation, is repeated.

Write a program that simulates Hanafuda shuffling and answers which card will be finally placed on the top of the deck.



Figure 1: Cutting operation

输入:

The input consists of multiple data sets. Each data set starts with a line containing two positive integers n (1 <= n <= 50) and r (1 <= r <= 50); n and r are the number of cards in the deck and the number of cutting operations, respectively.

There are r more lines in the data set, each of which represents a cutting operation. These cutting operations are performed in the listed order. Each line contains two positive integers p and c (p + c <= n + 1). Starting from the p-th card from the top of the deck, c cards should be pulled out and put on the top.

The end of the input is indicated by a line which contains two zeros.

Each input line contains exactly two integers separated by a space character. There are no other characters in the line.

输出:

For each data set in the input, your program should write the number of the top card after the shuffle. Assume that at the beginning the cards are numbered from 1 to n, from the bottom to the top. Each number should be written in a separate line without any superfluous characters such as leading or following spaces.

样例输入:

5 2
3 1
3 1
10 3
1 10
10 1
8 3
0 0

样例输出:

4
4

解题代码:

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in)); 

  
        while (scan.hasNext()) {   
            int m = scan.nextInt();   
            int n = scan.nextInt();   
            if (m == 0 && n == 0) {   
                break;   
            }   
            LinkedList cards = new LinkedList();   
            for (int i = 1; i <= m; i++) {   
                cards.addFirst(i);   
            }   
            for (int i = 0; i < n; i++) {   
                int p = scan.nextInt();   
                int c = scan.nextInt();   
                LinkedList lk = new LinkedList();   
                for (int j = 0; j < c; j++) {   
                    int a = cards.remove(p - 1);   
                    lk.addLast(a);   
                }   
                for (int j = 0; j < c; j++) {   
                    int a = lk.removeLast();   
                    cards.addFirst(a);   
                }   
            }   
            System.out.println(cards.getFirst());   
        }   
    }   
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。