← 返回题目列表

AtCoder · joisc2012_copypaste

copypaste. 复制和粘贴

中文机器翻译题面 查看原题

以下是来自日本的官方日本新闻原版PDF,已完整保留并按原样染色。

コピー&ペースト - 原题 PDF 第 1 页
原题PDF第4页
コピー&ペースト - 原题 PDF 第 2 页
原题PDF第5页
コピー&ペースト - 原题 PDF 第 3 页
原题PDF第6页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                   Contest Day 4 – Copy and Paste

            コピー&ペースト(Copy and Paste)



 テキストエディタの最も重要な機能の1 つとして,コピー&ペースト(複写・貼付) がある.JOI 社は,コ
ピー&ペーストを非常に高速に処理するテキストエディタの開発を開始した.JOI 社に所属する優秀なプ
ログラマであるあなたは,核となるコピー&ペーストの処理の実装の担当となった.JOI 社の命運が懸かっ
ているので,何としても正確かつ高速なプログラムを作成したい.
 具体的な仕様は次のとおりである.初め,ファイルの内容は文字列S である.引き続いて,コピー&ペー
ストの操作がN 回行われる.i 回目の操作は,位置Ai から位置Bi までの文字列を複写し,複写された文字
列を元の文字列の位置Ci に挿入貼付する,というものである.ここで,位置x とは,文字列の先頭からx
個の文字をたどった直後の箇所を表す(位置0 は文字列の先頭である).ただし,操作後に文字列の長さが
M を超えた場合,長さがM になるまで文字列の右端から順に文字が削除される.N 回の操作後に得られる
文字列を求めたい.


課題

 文字列の長さの上限M,初めの文字列S ,操作の回数N およびN 回のコピー&ペーストの操作の指示が
与えられたとき,操作後の文字列を出力するプログラムを作成せよ.


制限

   1 ≦M ≦1 000 000 文字列の長さの上限
   1 ≦N ≦1 000 000 操作の回数


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には整数M が書かれており,文字列の長さの上限を表す.
   • 2 行目には文字列S が書かれており,初めの文字列を表す.S はアルファベットの小文字からなり,
   長さは1 以上M 以下である.

   • 3 行目には整数N が書かれており,操作の回数を表す.
   • 3 + i 行目(1 ≦i ≦N) には整数Ai, Bi, Ci が空白を区切りとして書かれており,i 回目の操作は位置Ai
   から位置Bi までの文字列を複写し位置Ci に挿入貼付する,というものであることを表す.i 回目の
   操作の直前の文字列の長さをLi とすると,0 ≦Ai < Bi ≦Li および0 ≦Ci ≦Li を満たす.





                   コピー&ペースト– 1 / 3

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                   Contest Day 4 – Copy and Paste


出力

 標準出力に,N 回の操作後の文字列を1 行で出力せよ.


採点基準

 採点用データのうち,配点の10%分については,M ≦100 000,N ≦100 000 を満たす.


入出力例

  入力例1        出力例1
   18                   acyppypastoopyppyp
   copypaste
   4
   3 6 8
   1 5 2
   4 12 1
   17 18 0

 この例では,N = 4 回のコピー&ペーストの操作は以下のように行われる.

   • 初めの文字列はcopypaste である.
   • 1 回目の操作では,位置3 から位置6 までの文字列ypa が複写され,位置8 に挿入貼付されることで,
    文字列copypastypae を得る.

   • 2 回目の操作では,位置1 から位置5 までの文字列opyp が複写され,位置2 に挿入貼付されること
    で,文字列coopyppypastypae を得る.

   • 3 回目の操作では,位置4 から位置12 までの文字列yppypast が複写され,位置1 に挿入貼付され
    ることで,文字列cyppypastoopyppypastypae を得るが,長さがM = 18 を超えているため,右端
   から文字が削除され,文字列cyppypastoopyppypa を得る.

   • 4 回目の操作では,位置17 から位置18 までの文字列a が複写され,位置0 に挿入貼付されることで,
    文字列acyppypastoopyppypa を得るが,長さがM = 18 を超えているため,右端から文字が削除さ
    れ,文字列acyppypastoopyppyp を得る.





                   コピー&ペースト– 2 / 3

Japanese Olympiad in Informatics 2011/2012
                                                        Spring Training Camp/Qualifying Trial
                                            March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                Contest Day 4 – Copy and Paste


入力例2        出力例2
100                  jjooii
joi
3
0 1 0
3 4 3
2 3 3





                  コピー&ペースト– 3 / 3