f993: 叫我神射手
Tags : 二分搜 貪心
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-26 14:00

Content

 

小吉是個神射手,就算是幾公里外的東西她都射得到。今天她做出了一個量子飛彈,想要射射看,於是她對準了幾公里外的一處窗戶,看能不能射到。小艾和小琳為了不讓她打破別人家的窗戶,於是在中途設了一些障礙物。

窗戶的座標是 $\color{black}{R}\ $,小吉可以選擇在 $\color{black}{[\ 0,\ R\ ]}\ $ 間發射她的飛彈,但是她想讓飛彈飛得越遠越好,也就是如果她在 $\color{black}{x_0}\ $ 發射,$\color{black}{R - x_0}\ $ 要越大越好。飛彈有一個初始動能 $\color{black}{K_0}\ $,如果要打破窗戶,那麼到達窗戶時的動能要大於 $\color{black}{0}\ $ 才行。因為量子的性質,$\color{black}{K}\ $ 永遠會是一個整數。如果 $\color{black}{K}\ $ 在中途小於等於 $\color{black}{0}\ $,那飛彈就會停下來,代表到不了 $\color{black}{R}\ $。

 

障礙物有四種:

一、玻璃

玻璃是一種叫作玻璃的材質,特別易碎,窗戶就是用玻璃製成的。如果飛彈碰到玻璃,假設當時的動能是 $\color{black}{K}\ $,則 $\color{black}{K}\ $ 會變成 $\color{black}{\lfloor K - (a + b\times dis) \ \rfloor}\ $,$\color{black}{dis}\ $ 代表目前飛彈飛的距離,也就是如果當前座標是 $\color{black}{x}\ $,則 $\color{black}{dis = x - x_0}\ $。$\color{black}{(0≤a≤1000,0≤b≤10)}\ $

二、毒氣

小吉住的地方常常會有毒氣,像是工廠或是礦坑就會排出很多,還會有一些瘋狂科學家會亂製造出一些有毒的物質,如果普通人碰到就會馬上中毒,而且沒有方法可以解毒,因為:「我的毒,沒有解藥 ~
如果飛彈碰到毒氣的話,$\color{black}{K}\ $ 會變小,因為毒氣的密度比正常空氣大很多,如果飛彈碰到毒氣,那麼 $\color{black}{K}\ $ 會變成 $\color{black}{\lfloor K\ /\ (a + b\times dis)\ \rfloor}\ $。$\color{black}{(1≤a≤50,0≤b≤3)}\ $

三、石頭

石頭屬於石頭的一種,如果飛彈碰到石頭,那麼 $\color{black}{K}\ $ 會變成 $\color{black}{\lfloor K^{\ 1/(a+b\times dis)}\ \rfloor}\ $,也就是 $\color{black}{K}\ $ 開 $\color{black}{a+b\times dis}\ $ 次方根。$\color{black}{(1<a≤10,0≤b≤1)}\ $

四、水晶

水晶是一種神秘的物質,可以製造魔法,但是極不穩定,如果受到太大的擾動,就會爆炸,小吉小時候就不小心弄爆過。所以如果飛彈碰到水晶,水晶爆炸的威力會使 $\color{black}{K}\ $ 變成 $\color{black}{\lfloor log_{a+b\times dis}\ K\ \rfloor}\ $,也就是讓 $\color{black}{K}\ $ 變成以 $\color{black}{a+b\times dis}\ $ 為底取對數。$\color{black}{(2≤a≤10,0≤b≤1)}\ $

 

 

 

小吉知道小艾和小琳會設障礙物,所以她準備了 $\color{black}{M}\ $ 個「小爆彈」,小爆彈有一個威力值 $\color{black}{p}\ $,如果原本飛彈的動能為 $\color{black}{K}\ $,那加了 $\color{black}{m}\ $ 個小爆彈,飛彈動能就會變 $\color{black}{K+m\times p,m}\ $ 可以為任意正整數,並且小爆彈可以分成很多次用,只要總共不要用超過 $\color{black}{M}\ $ 個就好。假設飛彈現在位置在 $\color{black}{x}\ $,且 $\color{black}{x}\ $ 有一個障礙物,那飛彈會碰到這個障礙物,且改變 $\color{black}{K}\ $ 值,如果飛彈碰到這個障礙物後 $\color{black}{K}\ $ 會小於等於 $\color{black}{0}\ $,那就可以考慮先加一些小爆彈,讓 $\color{black}{K}\ $ 值先變大,使它變大之後再穿過障礙物後還能繼續飛;如果飛彈原本穿過障礙物就能繼續飛,也是可以先加小爆彈,讓 $\color{black}{K}\ $ 值變很大。這邊要注意到,一旦 $\color{black}{K}\ $ 小於等於 $\color{black}{0}\ $,就會馬上停止,就算加了小爆彈,還是不能讓它繼續動。

小吉如果在 $\color{black}{x_0}\ $ 發射飛彈,那麼座標小於 $\color{black}{x_0}\ $ 的障礙物都會被忽略,且如果在 $\color{black}{x_0}\ $ 有一個障礙物,那飛彈會先碰到障礙物才繼續飛。因為窗戶是用玻璃做的,所以在 $\color{black}{R}\ $ 處一定會有第一種類型的障礙物。為了讓飛彈一定可以打破玻璃,所以在 $\color{black}{R}\ $ 處的 $\color{black}{a, b}\ $ 值皆為 $\color{black}{0}\ $,也就是小吉只要在 $\color{black}{R}\ $ 發射的話,一定能成功。

Input

第一行有三個整數 $\color{black}{n,R,q}\ $,代表有幾個障礙物、窗戶的位置和詢問的筆數。

  • $\color{black}{1≤n≤2\times 10^5}\ $
  • $\color{black}{0≤n-1≤R≤10^{12}}\ $
  • $\color{black}{1≤q≤10}\ $

接下來 $\color{black}{n}\ $ 行,第 $\color{black}{i}\ $ 行有兩個整數和兩個小數 $\color{black}{t_i,\ x_i,\ a_i,\ b_i}\ $,代表障礙物的類型、座標和障礙物的 $\color{black}{a,b}\ $ 值,且 $\color{black}{a,b}\ $ 為 $\color{black}{5}\ $ 位小數。

  • $\color{black}{1≤t_i≤4}\ $
  • $\color{black}{0≤x_i<x_{i+1}≤R}\ $
  • $\color{black}{t_n=1,\ x_n = R,\ a_n=b_n=0}\ $

接下來 $\color{black}{q}\ $ 行,每行有三個整數 $\color{black}{K_0,\ p,M}\ $,代表飛彈初始動能、小爆彈的威力值和有多少個小爆彈。

  • $\color{black}{1≤K_0,\ p≤10^9}\ $
  • $\color{black}{1≤M≤2\times 10^5}\ $
Output

輸出總共有 $\color{black}{q}\ $ 行,每行輸出 $\color{black}{dis_{max}}\ $ 和 $\color{black}{m_{min}}\ $,代表對於每筆詢問,飛彈最遠可以飛多少,和在這個距離下,最少要用幾顆小爆彈。

Sample Input #1
18 194 10
4 1 4.17635 0.44384
1 29 213.99653 0.84779
2 64 20.32314 2.36395
4 70 6.32467 0.55315
2 78 25.76264 2.96039
1 84 721.50553 0.60699
2 86 30.58764 1.91082
1 90 429.39652 9.24201
2 91 35.09033 0.68141
1 110 747.57178 2.14392
4 121 4.99901 0.66584
1 134 641.14808 3.60261
4 148 2.01973 0.56302
1 162 986.00955 3.18186
1 175 252.83401 3.17466
3 180 6.64146 0.91087
1 185 172.88449 0.69012
1 194 0.00000 0.00000
52 10 1
43 56 129
68 31 198
8 31 2
32 54 115
33 9 176
73 21 89
52 75 136
84 71 105
6 69 146
Sample Output #1
8 0
165 128
144 198
8 0
144 115
47 176
59 80
194 111
176 105
194 119
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 3.0s , <10M
公開 測資點#1 (5%): 3.0s , <10M
公開 測資點#2 (5%): 3.0s , <10M
公開 測資點#3 (5%): 3.0s , <10M
公開 測資點#4 (10%): 3.0s , <1K
公開 測資點#5 (20%): 3.0s , <10M
公開 測資點#6 (25%): 3.0s , <10M
公開 測資點#7 (25%): 3.0s , <10M
Hint :

我只會出水題不要打我...

---------------------------------------

$\color{black}{5\%:t_i=1}\ $

$\color{black}{5\%:t_i=2,除了\ t_n}\ $

$\color{black}{5\%:t_i=3,除了\ t_n}\ $

$\color{black}{5\%:t_i=4,除了\ t_n}\ $

$\color{black}{10\%:R≤1000}\ $

$\color{black}{70\%:無特別限制}\ $

Tags:
二分搜 貪心
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」