ZeroJudge - c695: 藍燄番外篇——敗者之路（其一）　解題心得

(function(w,d,s,l,i);w[l].push('gtm.start':
new Date().getTime(),event:'gtm.js');var f=d.getElementsByTagName(s)[0],
j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src=
'//www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);
)(window,document,'script','dataLayer','GTM-KDKMGT');

(function(d, s, id) var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/zh_TW/all.js#xfbml=1&appId=668497826514848"; fjs.parentNode.insertBefore(js, fjs); (document, 'script', 'facebook-jssdk'));

if(BAHAID)
BAHAID = BAHAID.replace(/&/g, "&")
.replace(/, "<")
.replace(/>/g, ">")
.replace(/"/g, """)
.replace(/'/g, "'");

BAHAIDlow = BAHAID.toLowerCase();

document.write('

');
document.write('

');
document.write('');
document.write('

');

document.write('

');
document.write('');
document.write('');
document.write('');
document.write('

');

//document.write('

');
document.write('

');

else
document.write('

');
document.write('

我要登入

註冊

');
document.write('

');

document.write('

');

(function()
var cx = 'partner-pub-9012069346306566:kd3hd85io9c';
var gcse = document.createElement('script');
gcse.type = 'text/javascript';
gcse.async = true;
gcse.src = 'https://cse.google.com/cse.js?cx=' + cx;
var s = document.getElementsByTagName('script')[0];
s.parentNode.insertBefore(gcse, s);
)();

service = new rsearch('rsearch');

if( BAHAID )
NOTIFY_getnum();
run30 = setInterval("NOTIFY_getnum()",60000);

function insideSecondaryfunc(frm, evt){
if( 0

breadCrumbs(122, '', 'homeuid=inversion')

breadCrumbs_listMenu(122, 0, 'homeuid=inversion')

此小屋創作
所有創作

創作內容

0 GP

ZeroJudge - c695: 藍燄番外篇——敗者之路（其一）　解題心得

作者：Not In My Back Yard│2018-09-16 11:42:12│贊助：0│人氣：10

題目連結：

c695: 藍燄番外篇——敗者之路（其一）

註：這題是由本人出題

題目大意：

有一數列按以下的模式生成：

在數線上從０開始，做一系列的『跳躍』。第一次跳躍跳一個單位，會落到１；第二次跳躍跳兩個單位，落到３；第三次跳三格到６；第四次則因為２尚未到過，所以優先跳回去２。

也就是：每次跳躍的距離為上一次＋１。而如果『往回跳』的點曾未到過，則往回跳；不然，往前跳（以數線來講，『往回跳』即是往數線的左側，『往前』則是往數線的右端）。因此同一個點是有可能會跳到兩次以上的。

而對於每一次的跳躍，以起跳點與落地點為兩端點，兩點的距離為半徑，做半圓。每奇數次的跳躍，做下半圓；反之，做上半圓。
如此這般，會畫出以下圖形（附圖非完整圖形）：

現在給你此圖形上的一些點之座標（Ｘ和Ｙ，皆小於５００００００，但 ≧ ０），求這個點是位於第幾次跳躍的時候，所畫出的半圓之上。（若有多種可能，請給出次數最小的那一次，且保證答案小於１００００００）。

若Ｘ＝Ｙ＝０，則停止程式（不對此行測資做任何輸出）。

解題思維：

作為本題的始作俑者（？。我只能說除了題目敘述是小說、稍長以外，這題實際上並沒有什麼了不起的演算法。

首先，就是硬Ａ出上面數列（這數列目前沒有所謂的數學公式），照著上面的方式即可。每一次跳躍的距離是上一次的距離＋１，前面（數線的左測）沒有跳過的數字優先跳回去；否則，往後跳。

再來就是判斷給定的Ｘ、Ｙ是在哪次跳躍上畫出的半圓。

用迴圈按照順序跑過剛剛產生出的數列。每一項跟上一項的數字相減取絕對值和平均值。

絕對值即是上一次的跳躍之距離，也就是上次跳躍所畫出的半圓之「直徑」。因為是直徑，而我們等等用圓的方程式是半徑，所以將絕對值除以２，並叫做Ｒ。

而平均值即是「圓心」。因為必定在數線上，所以設座標為（Ｈ, ０）。

讀者不需對「半圓」這件事做任何處理，因為出題者（就是我）已經保證給定的點一定在圖形上，因此要擔心「半圓」的只有我ＸＤ（這題的測試資料莫名難生）

把Ｘ、Ｙ代入平面空間（只有Ｘ、Ｙ軸）的圓方程式：

（Ｘ－Ｈ）^ ２＋Ｙ ^ ２＝Ｒ ^ ２

若等號左右真的成立，即代表Ｘ、Ｙ是在這次跳躍所畫出的半圓上。

註：

這個數列叫做「Recamán」數列，參見ＯＥＩＳ的Ａ００５１３２。關於此數列有一猜想：所有正整數（包含０）皆會出現在此數列裡。

但是即便算到了第１０ ^ ２３０項，仍然不見８５２６５５這個數字的蹤影。

如想看一些關於這個數列的一些趣事，可以看Ｎｕｍｂｅｒｐｈｉｌｅ的這部影片。

此外，大推Ｎｕｍｂｅｒｐｈｉｌｅ這個頻道。裡面有著各式各樣的數學小知識，有的可以跟生活連結，有的則是知道了會很酷（？。總之就是個科普頻道。

本人的程式碼（放在CodePile）

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

喜歡0
收藏
0
引用
0
留言
推上首頁

檢舉

引用網址：https://home.gamer.com.tw/TrackBack.php?sn=4131674

All rights reserved. 版權所有，保留一切權利

相關創作

同標籤作品搜尋：程式題目解題心得

ZeroJudge - c198: 保持穩定供電　解題心得

c468: 4th CPSC Problem 4－上色新也　解題心得

ZeroJudge - d017: AB Circle　解題心得

ZeroJudge - c504: 旅行者_九國遊歷記<9> 小黑去鷺國　解題心得

ZeroJudge - d587: 參貳壹真好吃　解題心得

留言共 0 篇留言

Util.ChangeText('replys', Util.ChangeText.FLAG_LAZYLOAD|Util.ChangeText.FLAG_MAX_SIZE|Util.ChangeText.FLAG_BALA_PLAYER);

我要留言提醒：您尚未登入，請先登入再留言

0喜歡★inversion 可決定是否刪除您的留言，請勿發表違反站規文字。

前一篇：ZeroJudge - ...

後一篇：ZeroJudge - ...

egg('.MSG-list8C img').each(function(elem)
elem.className = elem.className + ' lazyload';
);

egg('.gallery-image').imageGallery();

function deleteCreation(vCode)
var content = egg('.MSG-list8C').html();
var pattern = /]*?>/i;
var html = '

確定要刪除嗎？';
var width = '200px';
if(content.match(pattern))
html += '
若文中有我上傳至巴哈的圖片也一併刪除';
width = '350px';

html += '

';

var boxConfig =
'closeButton': false,
'css':
'width': width

;

egg.mutbox(html, '訊息',
'確定': function()
if(egg('#chkDelTruthImage:checked').size())
egg('[name=delTruthImage]').val('yes');

egg.cookie.del('ckHOME_CREATION','home.gamer.com.tw','/');
egg.cookie.set('ckHOME_CREATION',vCode,'home.gamer.com.tw','/');
document.getElementById('frmDel').submit();
egg.lightbox.close();
,
'取消': function()
egg.lightbox.close();

,boxConfig);

var buttonOk = egg('.BH-popbtns :button:eq(0)');
if(buttonOk.size())
buttonOk.get(0).focus();

resizeImage(627);

egg('.btnGp').click(function()
$.mutbox('請先登入才能進行此動作', '訊息', '確定':function()location.href='https://user.gamer.com.tw/login.php';);
);

訂閱私訊

作品資料夾

ZeroJudge (63)

未分類 (0)

enchnater000 給 ALL：
厭倦一成不變的遊戲了嗎？一起來做屬於你的遊戲吧！http:///www.chimakier.com看更多我要大聲說昨天20:53

googletag.cmd.push(function() googletag.display('div-gpt-ad-1489070677458-0'); );

(function(window, $)
var $window = $(window);
var $document = $(document);
var $BH_slave = $("#BH-slave");
var $BH_master = $("#BH-master");
var $flySalve = $("#flySalve");
var posY = $flySalve.position().top;
var fad_style = document.getElementById("flySalve").style;
var BH_wrapper_width = $('#BH-wrapper').width();
var BH_topBar_height = $('.TOP-bh').height();
$(window).on("scroll", function()
posY = $BH_slave.height() - (fad_style.position === 'fixed' ? 0 : $flySalve.height());

if ($document.scrollTop() > (posY + $BH_slave.offset().top - BH_topBar_height) && $BH_slave.height() < $BH_master.height())
fad_style.position = 'fixed';
fad_style.top = BH_topBar_height + 'px';
if ($(window).width() < BH_wrapper_width)
fad_style.left = (BH_wrapper_width - $BH_slave.width() - $document.scrollLeft())+'px';

else
fad_style.position = '';

).on("resize", function()
fad_style.left = null;
);
)(window, jQuery);

我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營，請將 gamer.com.tw 加入廣告阻擋工具的白名單中，謝謝 !【教學】

黑色沙漠手遊公會缺人名稱是GO歡迎大家查詢到後加入

This page is only for reference, If you need detailed information, please check here
The name of the picture

搜尋此網誌

Dyjtyuk