a391: GT's Sort Problem
標籤 : 二篩實作題
通過比率 : 21人/22人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-08-11 19:30

內容

即將升上高二的 GT,

由於課業實在太爛,

眼看著高二即將來臨,

所以不得以,

只好減少打 code 的時間,

來準備好好讀書。

讀書讀著,

又覺得好無聊阿,

突然,

他對於 $a^b$ 的排序很有趣,

給他很多組數 $a, b$,

他都能依照 $a^b$ 的大小排序。

但是他的腦袋很小,

最多只能記得住 $10$ 組數字,

超過的話,

他就會很懊惱,

連這種消遣都可以讓他生氣。

為了成為名副其實的排序王(?),

所以他就打算寫程式來幫助他排序。

 

輸入說明

單筆測資。

第一行有一個數 $T$,

接下來有 $T$ 行,

每行包含兩個正整數 $a, \ b$。

輸出說明

依照 $a^b$ 的大小,

輸出排序(由小到大)好的 $a, \ b$。

範例輸入
10
9 4
8 2
3 6
2 2
4 8
4 2
6 6
6 3
4 5
8 2
範例輸出
2 2
4 2
8 2
8 2
6 3
3 6
4 5
9 4
6 6
4 8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1M
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <10M
提示 :

若 $a^b$ 值有相等,則先依照 $a$ 再依照 $b$ 排序。如:$4^2$ 和 $2^4$ 大小相等,請優先排 $(2, \ 4)$,再排 $(4, \ 2)$。

 

提示:

$1.$ 可以使用 $pair$ 存。

$2.$ 使用對數,對$a^b$ 取 $log$,$log(a^b) \ = \ b \ * \ log(a)$,記得 $log$ 要以 $10$ 為底數。

$3.$ $algorithm$ 有內建 $sort$ 可以使用。

$4.$ 由於精準度的問題,請不要使用 $float$,請使用 $double$。

 

$20\%$ 的測資,$1 \le a, \ b, \le, 10$,$T \ = \ 100$。

$60\%$ 的測資,$50 \le a \le 100$,$1000 \le b \le 2000$,$T \le 20000$。

$100\%$ 的測資,$1000 \le a \le 2000$,$2000 \le b \le 30000$,$T \le 200000$。

標籤:
二篩實作題
出處:
[管理者:
fdhs109_GT (9th 進階助教)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」