LIOJ 1006 問題

[rdcvgt]

前面幾題答得很順，但這題卡了兩天，看到大家好像都沒問過這題，所以想詢問一下

遇到的困難

我原本想以題目中兩排式座位的方法去解題，但發現會遇到很多限制，可能會遇到中間座位可以有三種座位組合，邊緣座位兩種組合、被佔走的座位相鄰而重疊計算...等問題，窮舉條件的狀況下又會變成沒辦法套用所有情境

今天又想到如果把座位變成一長排的方式，可以計算出「連續座位」數量來解題，的確使用題目中的測資可以答題成功
但想一想又發現會有 bug （像是 6 個座位 1,4,5 被佔走，得出的答案就會是錯的情況）

所以想上來詢問看看是不是有其他我沒有想過的方法

function solve(lines) {

	//輸入被佔走的座位 taken
	n = Number(lines[0])
	taken = []
	for(let i =2; i<lines.length;i++){
		taken.push(Number(lines[i]))
	}

	// 將座位 1~8 歸零
	arr = []
	for(let i =1; i<=n; i++){
		arr[i] = 0
	}


	//將被佔走的座位加一
	for (let j =0; j<taken.length; j++){
		q = taken[j]
		arr[q]++
	}

	//輸出連續座位的數值，加入seats陣列
	let sum = 0
	let seats = []
	for (let i =1; i<=arr.length; i++){
		if (arr[i] === 0){
			sum ++
			//如果碰到下一數字是1 或是沒有下一個數字，則將 sum 加入陣列， sum 歸零
			if (arr[i+1] === 1 || i=== arr.length-1){
				seats.push(sum)
				sum = 0
			}
		}
	}

	//將所有座位-1 加總
	ways = 0
	for(let i =0; i<seats.length; i++){
		ways += seats[i] -1
	}

	console.log(ways)
}

[cwc329]

我有點不懂為何你會覺得變成一排座位可以解決這個問題，
感覺和題目的要求就不一樣了。

另外，如果可以窮舉的話，可以試著想看看要怎麼從所有組合中刪除不可能的組合，應該就能得出答案。

[rdcvgt]

感謝提點。終於 AC 了！

我原本是先計算所有排法，再來扣除不能相鄰入座的方式，但發現這樣有太多條件需要窮舉。

後來改用加法的方式進行，先將偶數、奇數數列分開算連續空座位的排法，再來計算兩個陣列同一列位置都沒人坐的排法。

function solve(lines) {

	//輸入被佔走的座位 taken
	n = Number(lines[0])
	taken = []
	for(let i =2; i<lines.length;i++){
		taken.push(Number(lines[i]))
	}

	// 將座位 1~8 歸0
	arr = []
	for(let i =1; i<=n; i++){
		arr[i] = 0
	}


	//將被佔走的座位加一
	for (let j =0; j<taken.length; j++){
		q = taken[j]
		arr[q]++
	}

	//把 arr 拆開為偶、奇數陣列（如題目的圖）
	arrEven = []
	arrOdd = []

	for (let i=1; i<arr.length; i++){
		if (i%2 === 0){
			arrEven.push(arr[i])
		}else{
			arrOdd.push(arr[i])
		}
	}

	let ColEven = findColSeats(arrEven)
	let ColOdd = findColSeats(arrOdd)
	let RowAll = findRowSeats(arrEven, arrOdd)

	console.log(ColEven+ColOdd+RowAll)
	
}

//計算同一排若有連續座位的有多少排法
function findColSeats(arr){
	//輸出連續座位的數值，加入seats陣列
	let sum = 0
	let seats = []
	for (let i =0; i<arr.length; i++){
		if (arr[i] === 0){
			sum ++
			//如果碰到下一數字是1 或是沒有下一個數字，則將 sum 加入陣列， sum 歸零
			if (arr[i+1] === 1 || i=== arr.length-1){
				seats.push(sum)
				sum = 0
			}
		}
	}

	//將所有座位-1 加總
	ways = 0
	for(let i =0; i<seats.length; i++){
		ways += seats[i] -1
	}

	return ways
}

//若兩個陣列的第 i 值都為0，則排法+1
function findRowSeats(arrEven, arrOdd){
	let ways =0
	for (let i =0; i<arrOdd.length; i++){
		if (arrEven[i]=== 0 && arrOdd[i]===0){
			ways++
		}
	}

	return ways
}

[PT-HUANG]

之前一直卡在這題
終於通過了，跟大家分享一下解題思路
如果有更好的建議也可以交流分享XDD

function solve(lines){

  let n = lines[0]

  let seat = []

  let taken = []

  let result = 0

  for (let i=1; i<=n-1; i+=2){

    seat.push([i, i+1])
    //將橫排相鄰的座位以陣列的形式填入seat陣列

  }

  for (let i=1; i<=n-2; i+=2){

    seat.push([i, i+2])
    //將直排相鄰，奇數編號的座位以陣列的形式填入seat陣列
  }

  for (let i=2; i<=n-2; i+=2){

    seat.push([i, i+2])
    //將直排相鄰，偶數編號的座位以陣列的形式填入seat陣列

  }

  for (let i=2; i<lines.length; i++){

    taken.push(Number(lines[i]))
    //被佔走的座位編號

  }

  for (let i=0; i<seat.length; i++){

    let count = 0

    for (let j=0; j<taken.length; j++){

      if (taken[j] !== seat[i][0] && taken[j] !== seat[i][1]){

        count ++
      //如果該組合不符合被佔走座位編號，count ++

      }

    }

    if (count === taken.length){
    //如果count跟taken陣列長度一樣，代表該組合都沒有被佔走，result ++

      result ++
    }    

  }

console.log(result)
 
}

[aszx87410]

我之前似乎是這樣寫的：

function solve(lines) {
  let n = Number(lines[0])
  let m = Number(lines[1])
  let ans = 0
  let occupied = []
  for(let i=2;i<lines.length; i++){
    let p = Number(lines[i])
    occupied[p] = true
  }

  for(let i=1; i<n; i+=2) {
    if (!occupied[i] && !occupied[i+1]) ans++
  }

  for(let i=1; i<n-2; i+=2) {
    if (!occupied[i] && !occupied[i+2]) ans++
  }
  
  for(let i=2; i<=n-2; i+=2) {
    if (!occupied[i] && !occupied[i+2]) ans++
  }
  console.log(ans)
}