insight_codig_quiz_event_week_1

w1.go

/*
 * Copyright (C) 2012 Homin Lee <[email protected]>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package main

import (
	"fmt"
)

type Dataset struct {
	array []int
	s     int // left-most index of rotating
	t     int // right-most index of rotating
	k     int // rotate step
}

func ParseDataIn(d *Dataset) {
	var l int
	fmt.Scan(&l)
	d.array = make([]int, l)

	fmt.Scan(&d.s, &d.t, &d.k)
	for i := 0; i < l; i++ {
		fmt.Scan(&d.array[i])
	}
}

type Problem struct {
	idx  int
	data Dataset
}

func rotate(a []int, s, t, k int) {
	// resliced window for rotating area
	w := a[s : t+1]
	n := len(w)

	// in case 0 > k or k > rl
	k = k % n
	if 0 > k {
		k += n
	}

	if k == 0 {
		return
	}

	// left rotate is simpler then right
	k = n - k

	var i, c int
	for ; c < n; i++ {
		iTo := i
		iFrom := (iTo + k) % n
		tmp := w[iTo]
		for iFrom != i {
			w[iTo] = w[iFrom]
			c += 1
			iTo = iFrom
			iFrom = (iTo + k) % n
		}
		w[iTo] = tmp
		c += 1
	}
}

func Solve(p *Problem) {
	d := &p.data
	rotate(d.array, d.s, d.t, d.k)

	// Print out
	fmt.Printf("Case #%d:", p.idx)
	for i := 0; i < len(d.array); i++ {
		fmt.Printf(" %d", p.data.array[i])
	}
	fmt.Printf("\n")
}

func main() {
	var t int
	fmt.Scanln(&t)

	var p Problem
	for i := 0; i < t; i++ {
		p.idx = i + 1

		// Read dataset
		ParseDataIn(&p.data)

		// Solve it
		Solve(&p)
	}
}