2017年度「アルゴリズムとデータ構造」のページ

練習問題

2017年10月26日出題
  1. 標準入力から整数を次々に入力し、以下の条件で一部を削除して標準出力に出力するプログラムを、それぞれ、書け。

    入力値はlong longにおさまると仮定してかまわない。入力の個数は事前にはわからないものとする。

    1. 最初の入力値よりも小さな値を削除する。(最初の入力値は出力されることに注意)

    2. 最初の入力値以下の値を削除する。(最初の入力値は出力されないことに注意)

    3. 入力値がそれ以前の入力値の最大値より小さければ削除する。(出力値は広義単調増加になることに注意)

    4. 入力値がそれ以前の入力値の最大値以下ならば削除する。(出力値は狭義単調増加になることに注意)

    5. 同じ値が連続して出現したとき、一つだけを残して他を削除する。

    6. 同じ値が三つ以上連続して出現したとき、二つだけを残して他を削除する。

  2. ユークリッド平面上に三角形 \(ABC\) を固定する。平面上の点 \(X\) が実数の三つ組 \(\lambda,\mu,\nu\) を使って位置ベクトルに関して \((\lambda+\mu+\nu)X = \lambda A + \mu B + \nu C\) と表せるとき、\(X=\lambda:\mu:\nu\) と書く。

    成分で書き下すと、 \[ A=(x_A,y_A),\qquad B=(x_B,y_B),\qquad C=(x_C,y_C),\qquad X=\lambda:\mu:\nu \] のとき \[ X= \left( \frac{\lambda x_A + \mu x_B + \nu x_C}{\lambda + \mu + \nu}, \frac{\lambda y_A + \mu y_B + \nu y_C}{\lambda + \mu + \nu} \right) \] である。

    三角形の中点三角形反中点三角形内心三角形傍心三角形ジェルゴンヌ三角形ナーゲル三角形は、以下のように定義される。

    元の三角形を\(ABC\)とし、作られる三角形を\(A'B'C'\)とする。 辺\(BC\), \(CA\), \(AB\) の長さを、それぞれ、\(a\), \(b\), \(c\) と書く。

    中点三角形
    元の三角形の辺の中点を結ぶ三角形 \[ \begin{aligned} A' &= 0:1:1 \\ B' &= 1:0:1 \\ C' &= 1:1:0 \end{aligned} \]
    中点三角形
    反中点三角形
    元の三角形の頂点を通り対辺に平行な直線から構成される三角形 \[ \begin{aligned} A' &= -1:1:1 \\ B' &= 1:-1:1 \\ C' &= 1:1:-1 \end{aligned} \]
    反中点三角形
    内心三角形
    元の三角形の角の二等分線と対辺の交点を結ぶ三角形 \[ \begin{aligned} A' &= 0:b:c \\ B' &= a:0:c \\ C' &= a:b:0 \end{aligned} \]
    内心三角形
    傍心三角形
    元の三角形の傍心を結ぶ三角形 \[ \begin{aligned} A' &= -a:b:c \\ B' &= a:-b:c \\ C' &= a:b:-c \end{aligned} \]
    傍心三角形
    ジェルゴンヌ三角形
    元の三角形の内接円と辺の接点を結ぶ三角形 \[ \begin{aligned} A' &= 0:(a+b-c):(a-b+c) \\ B' &= (a+b-c):0:(-a+b+c) \\ C' &= (a-b+c):(-a+b+c):0 \end{aligned} \]
    ジェルゴンヌ三角形
    ナーゲル三角形
    元の三角形の傍接円と対応する辺の接点を結ぶ三角形 \[ \begin{aligned} A' &= 0:(a-b+c):(a+b-c) \\ B' &= (-a+b+c):0:(a+b-c) \\ C' &= (-a+b+c):(a-b+c):0 \end{aligned} \]
    ナーゲル三角形
    1. 三角形の各頂点の座標と文字列strを入力し、以下の手順で求まる三角形の各頂点の座標をすべて出力するプログラムを書け。

      • 文字列の各文字は下記の表で指定された三角形を求めることに対応する。 文字列の左側から適用する。 たとえば、文字列が MGII ならば、中点三角形のジェルゴンヌ三角形の内心三角形の内心三角形を求める。
        M 中点三角形
        A 反中点三角形
        I 内心三角形
        E 傍心三角形
        G ジェルゴンヌ三角形
        N ナーゲル三角形

      文字列strは100文字以下であると仮定してよい。入出力の書式は各自で決め、書式を記載した取扱説明書を添付すること。

参考データ

\(A=(0,0)\), \(B=(1+\sqrt{3},0)\), \(C=(1,1)\) の場合
\(A'\) \(B'\) \(C'\)
\(x\)座標 \(y\)座標 \(x\)座標 \(y\)座標 \(x\)座標 \(y\)座標
0.000000000000 0.000000000000 2.732050807569 0.000000000000 1.000000000000 1.000000000000
AGEANA -2.051037724576 -1.497065982650 5.799954667105 -1.166646671274 1.219830326285 2.550470227998
GMEAIA 0.271626902787 0.143220928007 1.819874723199 0.272113586150 0.930318781909 1.465508171349
IANGMM 1.085745512871 0.172379059313 1.144307641358 0.176981811070 1.107601877960 0.267141822034
GGNIEE 0.881643239826 0.484205174581 1.212174704928 0.511133742635 1.024291649690 0.769395074104
IIIAAA 0.282066637112 -0.155099753537 1.995831407284 -0.019437055643 1.025155273159 1.351872232324
NMMMNE 1.323985888196 0.132998125823 1.593806037468 0.124326579082 4.094611671295 80.890747706668
AGAGEE -0.939960690591 -1.664925769891 4.543712359307 -1.215290194659 1.383256075611 3.046091799305
ENIAII 1.400051850101 -1.989876723747 1.841678468651 -1.931089674842 1.574480182665 -1.573789090896
NMNGAI 1.659355922766 0.099402525645 1.659366866959 0.099402173900 1.659361752022 0.099413293775
IEIIGA 0.881469887251 0.378339579486 1.322591804769 0.413241101978 1.071981884612 0.775848283278
EEIEIN 0.516052925942 -2.032013824424 2.880390093565 -1.822263094671 1.518473719053 0.161671546715
GEANME 0.339847538563 0.116271571269 1.722790697050 0.261574976327 0.917516659075 1.860326766778
MEIEII 0.910233083079 0.424304235620 1.456905442395 0.472386733847 1.141573478730 0.920394919396
EIAMMI 1.163723968773 -0.447428183396 1.701951333948 -0.397260940635 1.392883247401 0.054194580009
IMENIA 0.916093535401 0.118768674367 1.326295224180 0.150850101858 1.090383531704 0.521486149829
MMIMAG 1.165129578791 0.302908369594 1.257856312359 0.310177974965 1.203687531158 0.404506226266
GMMNEG 0.992734845927 0.484039889280 1.088494719469 0.498664286425 1.032029077774 0.595800113577
IGNENI 1.050881612899 0.281066209820 1.165826294753 0.290193824346 1.101820950406 0.368324323504
EMGIAI 1.271780172694 -1.130515924787 1.794656447609 -1.085333180278 1.493878075670 -0.662601736041
IAENGN 0.891776003128 -0.346307874322 1.417863818604 -0.303627708720 1.134264006098 -0.052407452885
GEEAEN -2.121505896725 -1.215023391408 4.454443714337 -0.725561245635 0.660102315357 3.966486477188
ENEAEG -4.383528073404 -5.246629200495 8.338675227530 -4.044214736817 0.637798850535 5.246089473868
NEMNGN 1.300555609596 0.592252294364 1.376567251521 0.587373212201 1.325839564056 0.605094605516
NIGEIN 1.623042936718 0.111691094746 1.682021715129 0.110898997021 1.653181138413 0.149083037386
ENMMGN 1.494911920913 -1.420455173195 1.646708331965 -1.423935832673 1.546474374505 -1.376821918186
GEMNIA 0.870738756078 0.326768868361 1.274146948391 0.358595301733 1.047708639762 0.628236147946
IEANNG 0.880157234709 0.804572417935 1.256636787987 0.835216097127 1.052108167402 1.044524539176
IIAIAG 0.902956770454 0.233376530690 1.321462708399 0.266477915342 1.083076757711 0.618055430733
IGMGNI 1.090541414818 0.355162254860 1.116612748383 0.357228532543 1.101912970467 0.377272165152
EENAEG -2.974437825587 -6.268184125439 7.903299632884 -5.468618480227 1.681647829658 2.259612217244
GNNGNN 1.033584195496 0.687430586198 1.054126983537 0.685043765654 1.034472802915 0.687347490152
MAIANA -0.156095556086 -0.105198945505 2.413956730778 0.104760782186 1.063448316402 0.904909838133
EAIIEE -2.617748604371 -4.187675694576 6.067246618235 -3.409001480743 1.064517074737 3.764657614865
MEIGAA 0.093451889084 -0.043424824357 2.316039359479 0.134094384108 1.025475047373 1.884802505254
NIIGGG 1.645001125019 0.090313625620 1.657573213622 0.090218198253 1.651399364461 0.102637214639
MMEENM 1.038457094607 -0.372103594633 1.819027427565 -0.339252268453 1.363657073941 0.030315173592
IEMNIN 1.049421099759 0.448231377468 1.145529068409 0.455622643511 1.089188178019 0.554670744699
GNGMNN 1.049915856572 0.315863552473 1.090688498589 0.313852107362 1.063218987851 0.317241457885
IGEIMI 1.052210516921 0.347676175956 1.155974720054 0.355885381152 1.097031160238 0.441080379634
AEEGIN -0.489779956070 2.242340500309 1.786921068616 2.459675769616 0.479546224728 4.461989934895
IMNEGI 1.038244598135 0.389911489367 1.163978896050 0.399935735193 1.093043679642 0.496368283463
GGNGEA 0.883645165667 0.511183930540 1.207911978925 0.535019089713 1.022443703823 0.765398683811
AMGNMI 1.023369577999 0.453086891507 1.088140153443 0.466984325448 1.052402814095 0.525894708817
GMMNIG 1.037716547863 0.478629877746 1.055729252890 0.480126971772 1.044231447476 0.493740111049
MIIEMI 1.264257258275 0.283446286785 1.369440237582 0.291765091419 1.309537030810 0.379992139232
MMINEG 1.142821133077 0.305384079660 1.279969806177 0.316375887078 1.204001141211 0.404532162345
INENEG 0.837276466632 -0.064060276559 1.436491737039 -0.017385046443 1.084415481873 0.618168709242
AIGEAN 0.630851257503 -0.214596880570 2.485938449415 -0.066380192523 1.458917720276 1.133570150068
NGEEAM 1.366478012742 -0.019617295933 1.940294092788 -0.014041240583 1.652498518411 0.631351070001
IAIIIM 1.047090609920 0.418239007652 1.152973248223 0.426617185771 1.092835126086 0.513405303393
GIMMMA 0.997224948859 0.556071187478 1.078919149851 0.564704761276 1.032425719507 0.638043096348
EMAMNI 1.205366641307 -0.232599498520 1.617507065797 -0.144168999261 1.390107477200 0.230682547791
GGEEII 0.885685014064 0.454033300890 1.219339033078 0.483118037030 1.027235243464 0.756451578648
MNMEAM 0.835197752074 0.388511696779 1.394495743603 0.401757027128 1.127909029728 3.296087188797
AANAEI -4.619411054682 -14.385352539696 10.395479047910 -14.097288203082 2.934515785990 0.708243356247
AAINNM 0.139811274547 0.606719946184 1.190588904032 0.693288803000 0.662157750436 0.732723287118
NIMGMG 1.619974415671 0.094942101334 1.629120757407 0.094849591061 1.624672651538 0.100387640390
GNIAMI 1.026826167392 0.320807373872 1.095167121193 0.331192523118 1.054689695804 0.387776422905
GMIIAE 0.882635555562 0.388181049840 1.226676550197 0.417806006220 1.027878652980 0.697684386009
IAGIIN 1.043361520895 0.506793113814 1.144137965911 0.514749595811 1.086653881491 0.600332974520
IIMINE 1.052148910582 0.351248162541 1.155696918457 0.359434945562 1.096535818088 0.448650420565
EGMAIG 1.115355524950 -0.191468053763 1.625033437807 -0.145887103088 1.331259489591 0.287372013613
NNEIMA 0.193231170639 -1.910897542284 2.344604793929 -1.980042482702 1.339127144130 0.205866139960
GGNGAA 0.923153268498 0.481688786762 1.170955875007 0.507724970742 1.026662883398 0.794197237084
NAIAAI -0.006315356515 -0.123981514513 1.891949438226 -0.151775613684 0.933845492919 0.538831342295
MEGGGI 1.139218218788 0.421089336788 1.267855420579 0.432177865948 1.193790198987 0.536401578274
IAMMMA 0.854501383389 0.288675134595 1.361211386382 0.329459311299 1.084060272183 0.618134445894
GMMMMM 1.034541090834 0.520050081535 1.051308781224 0.522257589854 1.041486495603 0.545970685013
AIEAAI -1.753535599108 -2.123661521599 5.138411301392 -1.580025318564 1.198472270695 4.377571091090
MMAMIE 1.016642602374 0.234376561761 1.416282429189 0.265707589177 1.182822223000 0.672249743345
IMMNNG 1.099158064191 0.407082527740 1.100744878020 0.407211513997 1.099118569851 0.417324306512
AAENNG 1.868852955471 0.399298571835 2.502330574761 0.395994050325 1.918891164953 0.577775459621
MEIGAI 0.888599744540 0.474200783638 1.434858516792 0.521406607372 1.119398659160 0.965411153163
EEGMIE 0.473890013055 -1.927920172480 2.846653859448 -1.723977888463 1.479694912598 0.201257703790
MIIAII 1.264497615194 0.275696931865 1.370380253496 0.284075109984 1.310242131359 0.370863227607
GIIEAA 0.386010879072 0.129144990181 1.762174857614 0.247644815699 0.966983268744 1.367158334857
NIMEIN 1.579155201889 0.187204115156 1.701021314623 0.183471699899 1.640803502554 0.330006527136
NMANNI 1.295963472475 0.203686714518 1.958324728933 0.181740776356 1.659975408104 0.191625960721
AIEEMN 0.605905344526 -0.879425144155 2.604699801038 -0.719726615849 1.498119286075 0.573179778696
AMNANA -2.016491082045 0.122391282510 6.617425542528 -0.163675254209 1.017028962764 0.035043272945
EGGNNE 1.066503060983 -0.168389555254 1.716900465478 -0.136571761809 1.324860327072 0.272049493268
NGMNNM 1.659075372276 0.055565155808 1.659086704865 0.055826053223 1.659515630678 0.098651635297
EGMIEE 0.393088413487 -0.777402951127 2.487629486584 -0.596560359408 1.282545278822 1.097895405388
IINMME 1.054433451739 0.347547155804 1.154005598976 0.355403347681 1.096206378719 0.452498014042
ENEEME -5.321953745689 -3.739456024634 7.780288405058 -2.501122923361 -0.150629273088 7.066702125745
IENMMG 1.026021546513 0.639905926426 1.139945077494 0.649022220762 1.076717473305 0.725047650582
GNIIEI 1.025231557142 0.322846544094 1.095293349426 0.331491483540 1.052439813724 0.387520327802
IGGMMM 1.092196938151 0.329868907269 1.118726258814 0.331976478607 1.103812335800 0.351876034449
GIMAMG 0.993444169831 0.562034955631 1.080767725637 0.569009533106 1.030062560495 0.637793353925
NGEMNA 1.528644133319 0.090817903706 1.788077737635 0.087952755800 1.654046998176 0.158971765333
AAIGMA -0.018180777187 -0.153466086498 1.465446959895 -0.037152400555 0.598746460679 1.472099620256
IIMEIA 0.900148143559 0.255880200045 1.320880060786 0.289155418583 1.081267233698 0.642063609835
EINNIE 1.196623434569 -0.507071438781 1.735094046069 -0.468801056847 1.409970716057 -0.047106224449
EGGGGG 1.269159463022 0.036062759331 1.397648763081 0.047127596286 1.323654753637 0.151283370660
IEMGAN 0.848863232377 0.489074131645 1.338127034223 0.528165049100 1.067258867646 0.844641961454
EANMNE 0.346615246638 -0.626590425018 11.241977429918 -0.683425832615 1.207236677784 2.443084453081
AINNEA 1.022770894512 -6.692764849462 3.150214700895 -6.519832770591 0.969820770277 7.038404122316
AMEGEE -2.651858050396 -3.191096541705 6.071406036166 -2.475829633963 1.043846124068 4.303050173204
MAIGNM 1.065452167221 0.335247672086 1.144788351704 0.341356597479 1.096106481356 0.450414876712
MNAAEM 0.199461669523 -10.908959329096 2.436653635639 -10.855978007700 1.370306780137 0.721342638976

戻る