Home » 国际竞赛 » Details

USACO 2020 February Contest, Bronze Problem 3. Swapity Swap

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午12:10

USACO 2020 February Contest, Bronze Problem 3. Swapity Swap

Farmer John's? $N$ ?cows ( $1 \leq N \leq 100$ ) are standing in a line. The? $i$ th cow from the left has label? $i$ , for each? $1 \leq i \leq N$ .

Farmer John has come up with a new morning exercise routine for the cows. He tells them to repeat the following two-step process exactly? $K$ ?( $1 \leq K \leq 10^{9}$ ) times:

The sequence of cows currently in positions? $A_{1} \dots A_{2}$ ?from the left reverse their order ( $1 \leq A_{1} < A_{2} \leq N$ ).
Then, the sequence of cows currently in positions? $B_{1} \dots B_{2}$ ?from the left reverse their order ( $1 \leq B_{1} < B_{2} \leq N$ ).

After the cows have repeated this process exactly? $K$ ?times, please output the label of the? $i$ th cow from the left for each? $1 \leq i \leq N$ .

SCORING:

Test cases 2-3 satisfy? $K \leq 100$ .
Test cases 4-13 satisfy no additional constraints.

INPUT FORMAT (file swap.in):

The first line of input contains? $N$ ?and? $K$ . The second line contains? $A_{1}$ ?and? $A_{2}$ , and the third contains? $B_{1}$ ?and? $B_{2}$ .

OUTPUT FORMAT (file swap.out):

On the? $i$ th line of output, print the label of the? $i$ th cow from the left at the end of the exercise routine.

SAMPLE INPUT:

7 2
2 5
3 7

SAMPLE OUTPUT:

Initially, the order of the cows is? $[1, 2, 3, 4, 5, 6, 7]$ ?from left to right. After the first step of the process, the order is? $[1, 5, 4, 3, 2, 6, 7] .$ ?After the second step of the process, the order is? $[1, 5, 7, 6, 2, 3, 4]$ . Repeating both steps a second time yields the output of the sample.

Problem credits: Brian Dean

?USACO 2020 February Contest, Bronze Problem 3. Swapity Swap 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

For full credit, we need to do better than just simulating the? $K$ ?processes individually.

For each? $i$ ?compute the minimum positive integer? $X$ ?such that after? $X$ ?repetitions of the process, the cow with label? $i$ ?is again the cow that is? $i$ -th from the left. Then, for that cow, we can consider the remainder when? $K$ ?is divided by? $X$ ?rather than? $K$ ?itself. As the remainder is always less than? $N$ , this runs in? $O (N^{2})$ . See the silver analysis for how to do it in? $O (N)$ .

#include "bits/stdc++.h"
 
using namespace std;
 
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
 
int N,K,A1,A2,B1,B2,res[101];
 
int nex(int x) {
	if (A1 <= x && x <= A2) x = A1+A2-x;
	if (B1 <= x && x <= B2) x = B1+B2-x;
	return x;
}
 
int main() {
	setIO("swap");
	cin >> N >> K >> A1 >> A2 >> B1 >> B2;
	for (int i = 1; i <= N; ++i) {
		int p = 1, cur = nex(i);
		while (cur != i) {
			p ++;
			cur = nex(cur);
		}
		int k = K%p;
		for (int j = 0; j < k; ++j) cur = nex(cur);
		res[cur] = i; // position of cow i after k steps is cur
	}
	for (int i = 1; i <= N; ++i) cout << res[i] << "\n";
}

Alternatively, we can just hope that the permutation returns to its original state quickly. If it repeats after? $S$ ?steps, then it suffices to simulate only? $K (\mod S)$ ?steps. It can be verified (by exhaustive search) that the maximum possible value of? $S$ ?for? $N \leq 100$ ?is? $29640$ ?for? $A = (1, 94)$ ?and? $B = (2, 98)$ . Thus, the bounds were small enough to allow a solution that runs in? $O (N S)$ ?time to run in time.

Nick Wu's code:

import java.io.*;
import java.util.*;
public class Solution {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("swap.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("swap.out")));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());
    int a1 = Integer.parseInt(st.nextToken())-1;
    int a2 = Integer.parseInt(st.nextToken())-1;
    st = new StringTokenizer(br.readLine());
    int b1 = Integer.parseInt(st.nextToken())-1;
    int b2 = Integer.parseInt(st.nextToken())-1;
    int cycleSize = 0;
    int[] l = new int[n];
    for(int i = 0; i < n; i++) l[i] = i;
    boolean sorted = true;
    do {
      cycleSize++;
      reverse(l, a1, a2);
      reverse(l, b1, b2);
      sorted = true;
      for(int i = 0; sorted && i < n; i++) sorted = l[i] == i;
    }
    while(!sorted);
    k %= cycleSize;
    for(int i = 0; i < n; i++) l[i] = i+1;
    for(int i = 0; i < k; i++) {
      reverse(l, a1, a2);
      reverse(l, b1, b2);
    }
    for(int val: l) pw.println(val);
    pw.close();
  }
  private static void reverse(int[] l, int a, int b) {
    while(a < b) {
      int t = l[a];
      l[a] = l[b];
      l[b] = t;
      a++;
      b--;
    }
  }
}