Problem - E - Codeforces りんごさんの提出見て回答。題意： 有 N 個人，編號 1 到 N 要投票。投票可以使得當前的票數 +1 / +0 / -1 其中一個。每個人心目中都有一個期望票數，輪到他的時候他會依據當前的票數，操作使得接近他的期望票數。求對於所有 x，編…

Problem - D - Codeforces題意： 有 N 個城市，每對城市之間存在一個雙向路徑，每一條邊有一個死亡值 P。 一個路徑的死亡值是整條路徑上的邊的死亡值中的最小值。 對於每個城市 x，問一種方法，使得每個點對外都只留下一個有向邊，使得所有城市都會到達城市 …

Problem - C - Codeforces題意： 考慮一種整數的拆分方式，將一個數 x 拆分為 x = 1 + 2 + 4 + .. + 2^( k - 1 ) + r, 1 ≤ k and 0 ≤ r ≤ 2^k。原本有若干個數，進行這樣的拆分後，排序好，現在給你。問所有可能的原序列長度。制約： The first line contain…

Problem - B - Codeforces題意： 有 N 個人參加比賽，有五題，每個人的參數是五題的答對時間，沒有答對則以 -1 表示。一個人在一個題目的得分是這樣計算的： 考慮一個題，令 p 為答對人數，q 為參賽人數，則 p / q 對應到表格中的該題的最大分數。 對於一個…

Problem - A - Codeforces題意： 你現在寫了 y 個題目，答對了 x 個。你想知道你最少要再寫幾題才能有答對比率 p / q。若無解輸出 -1。制約： The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Each of the next t l…

https://oj.icpc.tw/contest/5/problem/DProblem Description: Define f( x ) as sum of digits of x, g( x ) as product of digits greater than 0 of x. Let D[ 1 ] = 8. D[ i ] = sum( f( D[ j ] ) + g( D[ j ] ) + 10 for j in range( 1, i ) ). Print D…

ICPC Blog Online JudgeProblem Description: Given A, B, print number of positive factors of all values between integer in [ A, B ].Constraints: 1 ≤ A ≤ B ≤ 1e14Solution: Consider calculating result of [ 1, B ] - [ 1, A - 1 ]. It uses simila…

https://oj.icpc.tw/contest/5/problem/BProblem Description: Define operator @ with following property: To calculate a @ b, first we transform them into base 3, then apply addition without carry. For example, 7 @ 8 = 21_3 @ 22_3 = 10_3 = 3. …

Problem - 622F - Codeforces題意： 令 f( k, x ) = sum( pow( i, k ) for i in range( 1, x + 1 ) ) % ( 1e9 + 7 )。 問 f( K, N ) 是多少。制約： 1 ≤ N ≤ 1e9 0 ≤ K ≤ 1e6解法： 很神奇，還沒看到這題的時候我就有想過手算一樣的問題了，還蠻顯然是用拉格…

Problem - 622D - Codeforces題意： 要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列，使得以下 s 最小。 d[ i ] 為 i 處於的兩個位置形成的距離。制約： 1 ≤ N ≤ 5e5解法： 看解說，覺得非常神祕，遇到類似題應該還是不會。 主要想法是這樣，猜測可以直接…

Problem - 609F - Codeforces題意： 有 N 隻青蛙在一維數線上，用位置和舌頭長度描述。現在依序有 M 隻蚊子出現，用位置和營養值描述。一個在位置 x，舌頭長度 t 的青蛙可以吃位於位置 y 的蚊子若且唯若 x ≤ y ≤ x + t，而且這隻青蛙是所有能吃到這隻蚊子的…

Problem - 609E - Codeforces題意： 給一張圖，分別問每一條邊必須被選擇時的最小生成樹花費是多少。制約： N, M ≤ 2e5解法： 找出原圖的最小生成樹後，做倍增 LCA，同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹，直接輸出當前最小花費，否則…

Problem - 598C - Codeforces題意： 給 N 個非零向量，求任意一對夾角最小的向量對。資料規模： N ≤ 1e5解法： 極角排序。 atan2( y, x ) 回傳的範圍在 [ -pi, pi ] 之間，只有 atan2( 0, 0 ) 是未定義的。時間 / 空間複雜度： O( N lg N ) #include <bits/stdc++.h> using </bits/stdc++.h>…

https://www.hackerrank.com/contests/capture-the-flag/challenges/infinite-links簡単な Web Crawler を書くだけ。 import urllib.request from queue import Queue def retrieve_msg_links( link ): line = list( urllib.request.urlopen( link ).read().…

https://www.hackerrank.com/contests/capture-the-flag/challenges/secret-key与えられたリンクに入る。 ソース読む。 secret.js を呼ぶ事に気づく。 それを読んで、key.json を dict としてパスコード承認の動作をしているとわかる。 url の末尾を key.jso…

XOR queries | Segment Trees & Data Structures Practice Problems | HackerEarth題意： 給一個數列 A。要求在線處理 Q 筆詢問： 第一種： __將 A[ i ] 改為 x 第二種： __問 A[ l, r ] 排序後，其中 [ i, j ] 間的 xor 值為何。制約： N, Q ≤ 5e4 1 ≤ A[ i…

Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth題意： 給一棵節點帶權的樹。每次詢問一條路徑，問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。制約： 1 ≤ N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法…

https://www.hackerearth.com/challenge/competitive/april-circuits-17/algorithm/numbers-summation/題意： 給 N，求 S 對 1e9 + 7 取模。制約： 1 ≤ N ≤ 1e15解法： 無恥怒查 OEIS。 如果想認真解起來，要領應該跟這個是一樣的。時間 / 空間複雜度： O( N…

Filler Game | Dynamic Programming and Bit Masking & Algorithms Practice Problems | HackerEarth題意： 一個 N * M 的棋盤，一開始也許會有障礙物。輪流操作放置一個障礙物，一個格子可以放障礙物若且唯若它是空的，而且它有一個相鄰的格子是空的。問先…

Fredo and Maths | Totient Function & Math Practice Problems | HackerEarth題意： T 筆詢問。問 x^x^x^x^x^x... % M，其中有 K 個 x，為多少。制約： 1 ≤ T ≤ 1e5 1 ≤ M ≤ 1e7 1 ≤ K ≤ 1e18 M 解法： 利用尤拉定理可以知道，x^phi( M ) % M == 1，利用這…

Help Fredo | Binary Search & Algorithms Practice Problems | HackerEarth題意： 給 N 個元素，問最小的 x ，使得 A[ 0 ] * A[ 1 ] * A[ 2 ] .. A[ N - 1 ] 制約： 1 ≤ N ≤ 1e5 1 ≤ A[ i ] ≤ 1e10解法： 經典題，開 log 比較，二分搜 x。時間 / 空間複雜度…

Problem - F - Codeforces題意： 給 N 個元素的數列 A。問有幾種不同的非空子序列，其最大公因數不為 1。輸出方案數對 1e9 + 7 取模。制約： The first line contains one integer number n (1 ≤ n ≤ 100000). The second line contains n integer numbers a…

F: Many Moves - AtCoder Regular Contest 073 | AtCoder題意： 在一個一維的棋盤上，你有兩顆棋，一顆在 A 位置，另一顆在 B 位置。有 Q 次操作，第 i 次操作後你必須移動棋子使得至少其中一個佔據 X[ i ]。棋子移動的花費是移動的距離。問 Q 次操作後，可…

E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder題意： 有 N 個箱子，裡面有兩個球，球有各自的重量。對於每個箱子，都需要將其中一顆球放到袋子 A，另一顆放到袋子 B。一個袋子的價值是其中最大的重量和最小的重量的差。求最小的價值乘積。制約…

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder題意： 有 N 個物品要做 01 背包問題。背包容量 W，要求價值最大。注意有個特殊限制：所有物品的容量和第一個物品的容量的差不超過 3。制約： 1≦N≦100 1≦W≦1e9 1≦wi≦1e9 すべての i=2,3,…,N につ…

Problem - G - Codeforces題意： 給一個長度為 n 的 B 數列。現在將 B 數列黏貼 k 次變成一個新的數列。有 Q 筆詢問： op = 1: __將 [ l, r ] 中的元素全部更改為 x op = 2: __詢問 [ l, r ] 中的最小值制約： The first line contains two integers n and k…

Problem - E - Codeforces題意： 你在玩遊戲，一場有三種結果，勝/平/敗。你知道當你的勝利的場數和敗北的場數的絕對差在 K 以上時，會立刻退出遊戲。現在你有一個序列描述 N 場遊戲，而你知道你打完這 N 場後退出。有些紀錄被塗成 '?'，要你復原出一個合理…

Problem - D - Codeforces題意： 要求在 K 行以內，用最小的寬度排版文字。輸出最小合理的寬度。一行的末尾必須是空白或是 '-' 符號。保證字不會由 '-' 開頭，也不會有連續的 '-' 或是連續的空白。制約： The first line contains number k (1 ≤ k ≤ 1e5). T…

Problem - C - Codeforces題意： 給 n, k，要求構造一個數列，數列長度必須是 k，元素總和必須是 n，而且要是嚴格遞增的。在此前提下，數列的 gcd 要最大。若不存在解則輸出 -1。制約： The first line consists of two numbers n and k (1 ≤ n, k ≤ 1e10).…

Problem - B - Codeforces題意： 給一個數列，其中至少有一個元素為 0。對每一個位置輸出離它最近的 0 的距離。制約： The first line contains integer n (1 ≤ n ≤ 2e5) — length of the array a. The second line contains integer elements of the array …